406 - Prime Cuts

Backbone · Post by **Backbone** » Sun May 21, 2006 9:19 am

Hi everybody, I've tried a lot of times and I still got a WA in 406, I'm testing all the inputs that I found, but WA!!, here is the code!!..

C++:

#include<iostream>
#include<stdlib.h>
using namespace std;

int primes(int N)
{
int prime=1,numprimes=0,i,isprime=1;
while(prime<=N)
{
for(i=2; i<prime; i++)
if(prime%i==0)
{
isprime=0;
i=prime;
}
if(isprime) numprimes++;
prime++;
isprime=1;
}
return numprimes;
}

int *saveprimes(int nprimes,int N)
{
int *array;
array=(int *)malloc(sizeof(nprimes));

int prime=1,numprimes=0,i,cont=0,isprime=1;
while(prime<=N)
{
for(i=2; i<prime; i++)
if(prime%i==0)
{
isprime=0;
i=prime;
}
if(isprime)
{
*(array+cont)=prime;
cont++;
numprimes++;
}
prime++;
isprime=1;
}
return array;
}

void impcentro(int *array, int C,int nprimes)
{
int centro,i,izq,der;
centro=nprimes/2;
if(nprimes%2!=0)
{
C=(C*2)-1;
izq=centro-(C-1)/2;
der=centro+(C-1)/2;
}
else
{
C=C*2;
izq=centro-C/2;
der=centro+(C-1)/2;
}
if(C>nprimes)
{
izq=0;
der=nprimes-1;
}
for(i=izq; i<=der;i++)
cout<<" "<<*(array+i);
cout<<"\n";
free(array);
}

main()
{
int N,C,nprimes,*primos;
while(cin>>N>>C && N>=1 && C>=1 && C<=N)
{
cout<<N<<" "<<C<<":";
nprimes=primes(N);
primos=saveprimes(nprimes,N);
impcentro(primos,C,nprimes);
}
}

Thnkz for Help me!!

chunyi81 · Post by **chunyi81** » Sun May 21, 2006 3:41 pm

Check the output specifications again:

For each input set, you should print the number N beginning in column 1 followed by a space, then by the number C, then by a colon ( : ), and then by the center numbers from the list of prime numbers as defined above. If the size of the center list exceeds the limits of the list of prime numbers between 1 and N, the list of prime numbers between 1 and N (inclusive) should be printed. Each number from the center of the list should be preceded by exactly one blank. Each line of output should be followed by a blank line. Hence, your output should follow the exact format shown in the sample output.

in particular pay attention to the sentence highlighted in bold.

Backbone · Post by **Backbone** » Sun May 21, 2006 8:14 pm

Hello!, thankz for reply, but I have solved the blank line problem and I still have WA!!, why??, I've tested a lot of inputs and all are correct... thnkz

eyeabhi · Post by **eyeabhi** » Mon May 22, 2006 10:19 pm

Code: Select all

/*
	Prime Cuts
*/

#include <stdio.h>
#include <iostream.h>
#include <math.h>


#define MAX 2000

void sieve(int *p)
{
	int  count;
	int i, j;
	count = (int)sqrt(MAX) + 1;
	for(i = 4; i < MAX; i += 2)
		p[i] = 1;						// means i is not prime
	p[2] = 0;							// means 2 is prime
	for(i = 3; i < MAX; i += 2)
		p[i] = 0;						// i is suspected to be prime
	
	for(i = 3; i <= count; i += 2)
		if(p[i] == 0)
			for(j = 2 * i; j < MAX; j += i)
				p[j] = 1;				// means j is not prime			
}


void main()
{
	int i, j, x, n, d;

	int c[MAX];
	int primes[MAX];
	sieve(c);	
//	bool firsttime = true;
	primes[1] = 1;
	primes[2] = 2;
	primes[3] = 3;

	// creating list of prime numbers
	for(i = 4, x = 4; i < MAX; i++){
		if(c[i] == 0){
			primes[x] = i;
			x++;
		}		
	}
	while(scanf("%d %d", &n, &d) == 2){	
		printf("%d %d:", n, d);
		for(i = 1; primes[i] < n; i++)
			;
		if(primes[i] != n)
			i--;
		if(i % 2 == 0){
			x = 2 * d;			
		}
		else{
			x = 2 * d - 1;
		}
		i = i / 2 - x / 2 + 1;
		
		for(j = 0; j < x && primes[i + j] <= n; j++){
			if(i + j < 1)
				continue;
			printf(" %d", primes[i + j]);
		}
		printf("\n\n");
	}
}

i tested all the i/o i found in 406 threads. they give correct answer. can anyone tell whts wrng?

thanx.

sohel_acm · Post by **sohel_acm** » Tue May 23, 2006 8:37 pm

Hi Abhi you can try these input set.

Code: Select all

The correct output:

Code: Select all

41 67: 1 2 3 5 7 11 13 17 19 23 29 31 37 41

334 0:

169 24: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167

478 58: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467

962 64: 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827

705 45: 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587

281 27: 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263

961 91: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953

995 42: 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691

827 36: 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587

391 4: 149 151 157 163 167 173 179 181

902 53: 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727

292 82: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283

421 16: 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263

718 95: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709

447 26: 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337

771 38: 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571

869 12: 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443

667 99: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661

35 94: 1 2 3 5 7 11 13 17 19 23 29 31

703 11: 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367

322 33: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313

673 64: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673

141 11: 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103

253 68: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251

547 44: 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491

662 57: 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643

37 59: 1 2 3 5 7 11 13 17 19 23 29 31 37

723 41: 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569

529 78: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523

Best Of Luck.

eyeabhi · Post by **eyeabhi** » Fri May 26, 2006 2:45 pm

My program had a bug, i fixed it and got AC. thank u very much for ur input/output.

ayeshapakhi · Post by **ayeshapakhi** » Sun Jul 02, 2006 3:02 pm

i got at least 5 WA. plz help me

Code: Select all

/* !NOT ACCEPTED!!!!!!!!Primes Cut 406*/ //Submit again 


#include <stdio.h>
#include <math.h>

#define L 1
#define U 100001
#define N 50000

long primes[N];
long c=0;
bool all[U];
long count[U];

void seive(void);


void main()
{
	freopen("406.in","r",stdin);
	freopen("out406.txt","w",stdout);
	long num1,num2,i,temp,start,end;
	for(i=0; i<U; i++)
	{
		all[i]=false;
		count[i]=0;
	}

	seive();
	while((scanf("%ld%ld",&num1,&num2))==2)
	{
		for(i=num1;  ; i--)
		{
			if(all[i])
			{
				temp=count[i];
				break;
			}
		}
		if(temp%2==0)
		{
			if(2*num2>=num1)
			{
				start=0;
				end=temp;
			}
			else
			{
				start=temp/2-num2;
				end=temp/2+num2;
			}
		}
		else
		{
			if((2*num2-1)>=num1)
			{
				start=0;
				end=temp;
			}
			else
			{
				start=temp/2-num2+1;
				end=temp/2+num2;
			}
		}
		printf("%ld %ld: ",num1,num2);
	    for(i=start; i<end; i++) printf("%ld ",primes[i]);
		printf("\n\n");
	}
}
void seive(void)
{
	int i,j,d;
	d=U-L+2;
	bool *flag=new bool[d];

	for(i=0; i<d; i++) flag[i]=true;
	for(i=(L%2!=0); i<d; i+=2) flag[i]=false;
	
	for(i=3; i<sqrt(U); i+=2)
	{
		if(i>L && !flag[i-L]) continue;
		j=L/i*i;
		if(j<L) j+=i;
		if(j==i) j+=i;
		
		j-=L;
		for( ; j<d; j+=i) flag[j]=false;

		if(L<=1) flag[1-L]=true;
		if(L<=2) flag[2-L]=true;
	}
    c=0;
	for(i=0; i<d; i++) 
		if(flag[i])
		{
			primes[c++]=L+i; 
			all[L+i]=true;
			count[L+i]=c;
		}
	return;
}

thanks for any help.

Artikali · Post by **Artikali** » Sun Jul 02, 2006 7:12 pm

460 46: 0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461

460 47: 0 0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463

460 48: 0 0 0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467

460 49: 0 0 0 0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479

460 50: 0 0 0 0 0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487

460 51: 0 0 0 0 0 0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491

460 52: 0 0 0 0 0 0 0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499

460 53: 0 0 0 0 0 0 0 0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503

460 168: -1543218801 2109923008 516352251 1518921630 -1086549673 404915024 1650805582 -1349549059 293442566 -1612829212 80270030 181970653 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097

linux · Post by **linux** » Tue Jul 18, 2006 3:05 pm

Just print double new line and get accepted.

Code: Select all

printf("\n\n");

Hope understand. GL.

unaben · Post by **unaben** » Sun Aug 27, 2006 12:24 am

I am getting WA all the time with my code.

Could someone plz help

Here is my code:

#include<iostream>

using namespace std;

int main()
{
bool *a = new bool[1001];
int n = 1000;
int primes[1000];
primes[0]=1;
int prim=1;
a[0] = 0;
a[1] = 1;
for(int i=2; i<=1000; i++)
a=1;
int p = 2;
while(p*p<=n)
{
int j=p*p;
primes[prim]=p;
prim++;
while(j<=n)
{
a[j]=0;
j +=p;
}
bool ok = true;
for(int k=p+1; ok and k<=n; k++)
{
if(a[k]==1)
{
ok = false;
p++;
}
else
p++;
}
}
for(int h=p+1; h<=n; h++)
{
if(a[h]==1)
{
primes[prim]=h;
prim++;
}
}
int num, c;
while(cin>>num>>c)
{
bool go = true;
int array[500];
int st=0;
for(int z=0; go and z<prim; z++)
{
if(primes[z]<=num)
st++;
else
go = false;
}
int hold, index, zeros;
cout<<num<<" "<<c<<": ";
if(st%2==0)
{
if(c*2<=st)
{
hold = st - (c*2);
index = hold/2;
for(int f=index; f<index+c*2; f++)
cout<<primes[f]<<" ";
cout<<endl;
}
else
{

for(int m=0; m<st; m++)
cout<<primes[m]<<" ";
cout<<endl;
}
}
else
{
if(((c*2)-1)<=st)
{
hold = st - (c*2)-1;
index = hold/2;
for(int f=index+1; f<=(index-1+c*2); f++)
cout<<primes[f]<<" ";
cout<<endl;
}
else
{
for(int m=0; m<st; m++)
cout<<primes[m]<<" ";
cout<<endl;
}
}
cout<<endl;
}
}

Thanx in advance!

alan0101 · Post by **alan0101** » Thu Sep 14, 2006 5:03 pm

Code: Select all


#include <stdlib.h>
#include <stdio.h>
#include "math.h"
int main()
{


	int* p;
	p = new int[2001];
	
	int bigarray[400];
	
	int  c;
	int k, j;
	p[1] = 0;
	c = (int) sqrt(2000.0) + 1;
	for(k = 4; k <  2000; k += 2)
		p[i] = 1;                  
	p[2] = 0;                     /////// it is prime
	for(k = 3; i < 2000; k += 2)
		p[k] = 0;    ///// might be prime

	for(k = 3; k <= c; k += 2)
		if(p[k] == 0)
			for(j = 2 * i; j < 2000; j += k)
				p[j] = 1;            /////// j = !prime   


	

	int length; // select those prime numbas out
	length = 0;
	for (int i = 1; i <= 2000; i++)
	{
		if (p[i] == 0)
		{
			length++;
			bigarray[length] = i;

		}
	}

	delete [] p; // release memory

	int NT, NI;


	
	while ( scanf("%d %d\n", &NT, &NI ) == 2)
	{
	
		int y;
		int up, low;

		//	y = 105;
		up = length;
		low = 1;
		if (NT == 2000)
		{
			y = length;
		}
		else
		{
			while (1) // the  binary search to get the center index
			{
				y = (up + low) /2;
				if (bigarray[y] > NT )
					up = y;
				else
					low = y;
				if (bigarray[y] <= NT && bigarray[y+1] > NT) 
					break;

			}
		}
		printf("%d %d:", NT, NI);

		int k;
		k = ((y) % 2);
		int haha;
		haha = NI;
		if (k == 1) haha = NI - 1; else haha = NI;
		if (k == 1)                         // if the index is odd then k = 1,
		{
		//	printf("haha!");
			for (int i = (y-1)/2- haha+1; i <= (y-1)/2; i++)
			{
				if (i < 1) i = 1;
				if (i > y) break;
				printf(" %d", bigarray[i]);
			}
			printf(" %d", bigarray[(y-1)/2+1]);
			for (int i = (y-1)/2 +2; i <= (y-1)/2 + haha+1; i++)
			{
				if (i < 1) i = 1;
				if (i >  y) break;
				printf(" %d", bigarray[i]);
			}
		}
		else	
		{     // index = even..
			for (int i =y/2 - haha+1; i <= y/2; i++)
			{
				if (i < 1) i = 1;
				if (i > y) break;
				printf(" %d", bigarray[i]);
			}
			for (int i = y/2+1; i <= y/2 + haha; i++)
			{
				if (i < 1) i = 1;
				if (i > y) break;
				printf(" %d", bigarray[i]);
			}
		}
	printf("\n\n");

	}
	

//	system("PAUSE");
	return 0;

}

little joey · Post by **little joey** » Thu Sep 14, 2006 5:13 pm

There are already many threads for this problem. Please use one of these.

wensi · Post by **wensi** » Sat Nov 25, 2006 5:52 pm

I tried all the inputs from the forum and all worked, still getting tle, could anyone help?
also i tried to add braces around the if/else statements but didnt change.

Code: Select all

#include <iostream>
#include <vector>
using namespace std;

bool prime(int n);

int main()
{
	int i,n,c,temp;
	vector<int> v;
	while (cin>>n>>c)
	{
		v.clear();
		for (i=1;i<=n;i++)
			if (prime(i)==true)
				v.push_back(i);
		cout<<n<<" "<<c<<": ";
		temp=c;
		if ((v.size()&1)==0)
			c*=2;
		else
			c=c*2-1;
		if (c>v.size())
			for (i=0;i<v.size();i++)
				cout<<v[i]<<" ";
		else
			if ((v.size()&1)==0)
				for (i=v.size()/2-c/2;i<v.size()/2+c/2;i++)
					cout<<v[i]<<" ";
			else
				for (i=v.size()/2-c/2;i<=v.size()/2+c/2;i++)
					cout<<v[i]<<" ";
		cout<<endl<<endl;
	}
	return 0;
}

bool prime(int n)
{
	int i=1;
	int c=0;
	for (i;i<=n;i++)
		if (n%i==0)
			c++;
	if (c>2)
		return false;
	return true;
}

ayon · Post by **ayon** » Sat Nov 25, 2006 6:39 pm

your prime() function is extremely extremely extremely slower. have a look at
http://www.comp.nus.edu.sg/~stevenha/pr ... atics.html
for some faster methods

wensi · Post by **wensi** » Sun Nov 26, 2006 3:50 am

thx, did everything i can to improve the speed, and finally got AC, and it is solved in 3.9 seconds. in the question it says N<=1000, I still dont understand why would that take so long to finish...

OJ Board

406 - Prime Cuts

P- 406 PRIME CUTS WA!!! Can anybody help me?? plz

I still have an error

WA 406 -- All the input output i found all r correct

Thank u ... I got it

406 prime cuts WA

About P.E.

406 WA

406 WA... why.. ??

406 TLE Prime Cuts