Page 6 of 13

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

Posted: 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!!

Posted: 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.

### I still have an error

Posted: 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

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

Posted: 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.

Posted: Tue May 23, 2006 8:37 pm
Hi Abhi you can try these input set.

Code: Select all

``````41 67
334 0
169 24
478 58
962 64
705 45
281 27
961 91
995 42
827 36
391 4
902 53
292 82
421 16
718 95
447 26
771 38
869 12
667 99
35 94
703 11
322 33
673 64
141 11
253 68
547 44
662 57
37 59
723 41
529 78
``````
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.

### Thank u ... I got it

Posted: 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.

### 406 prime cuts WA

Posted: 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.

Posted: 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

Posted: Tue Jul 18, 2006 3:05 pm
Just print double new line and get accepted.

Code: Select all

``````printf("\n\n");
``````
Hope understand. GL.

### 406 WA

Posted: 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;
}
}

### 406 WA... why.. ??

Posted: 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;

}

``````

Posted: Thu Sep 14, 2006 5:13 pm

### 406 TLE Prime Cuts

Posted: 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;
}
``````

Posted: 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

Posted: 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...