## 406 - Prime Cuts

Moderator: Board moderators

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 406 - Prime Cuts

I can't understand the problem 406(Prime Cuts).Can anybody tell me what to do?Plz help me.
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am

As I Remember The Problem Description Is Very Simple.
The Input Will n & c.You Have To Print c*2 (IF The Prime List is EVEN) or (c*2 -1) (IF The Prime List is ODD) prime from the center odf the list of prime number of (1 to n).
For Example If The n=21 & c = 2.
Then The Prime From 1 to 21 Are : 1,2,3,5,7,11,13,17,19 Total 9 Prime Number So The List Is ODD.(1 Is Prime For This Problem)
So You Need to Print (2*c-1 = 3), 3 Prime Number From The Center Of The List.
So The Output Will 5,7,11.

I THINK IT WILL CLEAR TO YOU NOW.

GOOD LUCK
ROCKY
asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### Thaks for help

Hello thank u for ur help.Yes I've now implement my code and got AC.Thanks again for ur help.
sfwejfish
New poster
Posts: 2
Joined: Wed Aug 10, 2005 7:19 am
Contact:

### 406...WA??WHY??All sample inputs are cerrect...

#include<iostream>
using namespace std;
int main(){
int prime[170]={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};
int in1,in2,x,min,max;
while(cin){
cin>>in1>>in2;
cout<<in1<<" "<<in2<<":";
for(x=1;;x++)
if(prime[x]>in1)
break;
x-=1;
min=(x/2)-in2+1;
if(x%2==1)
min+=1;
if(min<1)
min=1;
max=x+1-min;
for(x=min;x<=max;x++)
cout<<" "<<prime[x];
cout<<endl<<endl;
}
return 0;
}

I have tested all sample inputs,and the outputs are all cerrect.
Why WA?
chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Your code fails for the following input:

Input:

Code: Select all

``````21 2
18 2
523 40
18 18
100 7
1000 25
1000 12
523 40
12 10
21 3
99 25
100 100
723 12
``````
Correct output:

Code: Select all

``````21 2 : 5 7 11

18 2 : 3 5 7 11

523 40 : 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

18 18 : 1 2 3 5 7 11 13 17

100 7 : 13 17 19 23 29 31 37 41 43 47 53 59 61 67

1000 25 : 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

1000 12 : 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499

523 40 : 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

12 10 : 1 2 3 5 7 11

21 3 : 3 5 7 11 13

99 25 : 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

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

723 12 : 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379
``````

Code: Select all

``````21 2 : 5 7 11

18 2 : 3 5 7 11

523 40 : 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

18 18 : 1 2 3 5 7 11 13 17

100 7 : 13 17 19 23 29 31 37 41 43 47 53 59 61 67

1000 25 : 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

1000 12 : 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509
523 40 : 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

12 10 : 1 2 3 5 7 11

21 3 : 3 5 7 11 13

99 25 : 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

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

723 12 : 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379

723 12 : 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379
``````
And to read input for this problem, try while(cin >> in1 >> in2) instead of while(cin) so that you do not have a duplicate output for input: 723 12 as shown above.
Last edited by chunyi81 on Sat Mar 11, 2006 5:10 am, edited 1 time in total.
sfwejfish
New poster
Posts: 2
Joined: Wed Aug 10, 2005 7:19 am
Contact:
But I test
while(cin>>in1>>in2)
and
while(cin>>in1){
cin>>in2;
And still get 2 WA= ="
Maybe I have to write a new cade?
Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

### 406 WA.....

I tried many inputs, they are all right, but I still got WA
Can someone help me?

#include <stdio.h>
#include <math.h>
int main()
{
int a[200],b,c,d,e,f;
a[1]=1;
a[2]=2;
a[3]=3;
c=3;
for(b=5;b<=1000;b++)
{
d=(int)(sqrt(b));
for(e=2;e<=d;e++)
{
if(b%e==0)
{
goto cc;
}
}
c++;
a[c]=b;
cc:;
}
while(scanf("%d %d",&b,&c)==2)
{
printf("%d %d:",b,c);
for(d=1;d<=200;d++)
{
if(b<a[d])
{
d--;
break;
}
}
if(d%2==0)
{
e=d/2-c+1;
f=d/2+c;
if(e<=0)
{
e=1;
f=d;
}
}
else
{
e=(d+1)/2-c+1;
f=(d+1)/2+c-1;
if(e<=0)
{
e=1;
f=d;
}
}
for(d=e;d<=f;d++)
{
printf(" %d",a[d]);
}
printf("\n\n");
}
return 0;
}
hinyinlam
New poster
Posts: 1
Joined: Sun Nov 27, 2005 4:30 pm

### Again, It's 406 prime cut Need Help! WA

I don't know why I always get WA, both of them have correct output when using the test case given by the problem set. Thanks for any help!:)
And the output formate is unclear, for example for the input 18 18
Should I output:

Code: Select all

``````18 18: 1 2 3 5 7 11 13 17
(blank line)
// that means should I use cout << answer << endl << endl;
``````
OR

Code: Select all

``````18 18: 1 2 3 5 7 11 13 17 // that means should I use cout << answer << endl;?
``````
??????

Code one: Store all things first then calculate it

Code: Select all

``````#include <iostream>
#define no_prime 10000
#define no_input 500
using namespace std;
int main(){
int temp[no_prime];
int store_n[no_input];
int store_c[no_input];
int count=0;
int n;
int c;
while(cin >> n >>c){
store_n[count]=n;
store_c[count]=c;
count++;
}
for(int k=0;k<count;k++){
int temp_count=0;
int isPrime =1;
cout << store_n[k] << " " << store_c[k] << ": ";
//	cout <<": ";

for(int i=1;i<=store_n[k];i++,isPrime=1){
for(int j=2;j<i;j++){
if((i%j)==0&&i!=j){
isPrime=0;
break;
}
}
if(isPrime==1){
//cout << i << " ";
temp[temp_count]=i;
temp_count++;
}
}
if(store_c[k]<temp_count){
if(temp_count%2==0){//even range= temp_count/2+1 -c to  temp_count/2+1 +c
temp_count=temp_count/2;
for(int i=temp_count-store_c[k];i<temp_count+store_c[k];i++){
cout<< temp[i] << " ";
}
cout << endl;
}else{//odd range =temp_count/2
temp_count=temp_count/2;
for(int i=temp_count-store_c[k]+1;i<temp_count+store_c[k];i++){
cout << temp[i]<< " ";
}
cout << endl;
}
}else{//print out all if c >= temp_count
for(int i=0;i<temp_count;i++){
cout<< temp[i] << " ";
}
cout << endl;
}
cout << endl;
}
return 0;
}
``````
Code two: Calculate when there's input

Code: Select all

``````#include <iostream>
#define no_prime 1000
using namespace std;
int main(){
int temp[no_prime];
int n;
int c;
while(cin){
cin >> n >> c;
int temp_count=0;
int isPrime =1;
cout << n << " " << c << " : ";
//cout << "\b: " ;
for(int i=1;i<=n;i++,isPrime=1){
for(int j=2;j<i;j++){
if((i%j)==0&&i!=j){
isPrime=0;
break;
}
}
if(isPrime==1){
//cout << i << " ";
temp[temp_count]=i;
temp_count++;
}
}
if(c<temp_count){
if(temp_count%2==0){//even range= temp_count/2+1 -c to  temp_count/2+1 +c
temp_count=temp_count/2;
for(int i=temp_count-c;i<temp_count+c;i++){
cout<< temp[i] << " ";
}
cout << endl;
}else{//odd range =temp_count/2
temp_count=temp_count/2;
for(int i=temp_count-c+1;i<temp_count+c;i++){
cout << temp[i]<< " ";
}
cout << endl;
}
}else{//print out all if c >= temp_count
for(int i=0;i<temp_count;i++){
cout<< temp[i] << " ";
}
cout << endl;
}
}
return 0;
}
``````
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Input:

Code: Select all

``997 1``
Output:

Code: Select all

``433``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
You need primes less than 1000 only. Why you are generating primes less than 1000010? So you are getting TLE.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your code has a lot of errors.

Input:

Code: Select all

``900 79``
Output:

Code: Select all

``900 79: 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``
(The output is in one line)

Hope it works.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I used the following method...

Code: Select all

``````18 18: 1 2 3 5 7 11 13 17
(blank line)
// that means should I use cout << answer << endl << endl;  Yes is the answer``````
Change the following lines..

Code: Select all

``````cout << n << " " << c << " : "; //Your code
cout << n << " " << c << ":";  //Should be``````

Code: Select all

``````cout<< temp[i] << " "; //your code
cout<<  " " <<temp[i] ; //should be
``````
And add a new line after each test case.

Hope it works.
Ami ekhono shopno dekhi...
HomePage
kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Contact:

### 406 got TLE,help me!!

i got TLE 4 dis code,and cant get the reason, anybody tell me y n wats de solution.....

[/code]#include<stdio.h>

int isPrime(int num)
{
int k,j;
if(num==1||num==2) return num;
if(num%2==0) return 0;
j=sqrt(num);
for(k=3;k<=j;k+=2)
if(num%k==0)
return 0;
return num;
}

int main()
{
int input1,input2,i;
int ch1[1003],ch2[170];
for(i=0;i<=1003;i++)
ch1[i]=isPrime(i);
while(scanf("%d %d",&input1,&input2)==2)
{
int n,L,m=0,prime=0;
for(n=0;n<=input1;n++)
if(ch1[n]!=0)
{
ch2[m++]=ch1[n];
prime++;
}
printf("%d %d: ",input1,input2);
if(input2<prime)
{
if(prime%2==0)
{
prime=prime/2;

for(L=(prime-input2);L<(prime+input2);L++)
printf("%d ",ch2[L]);
}
else
{
prime=prime/2;
for(L=(prime+1-input2);L<(prime+input2);L++)
printf("%d ",ch2[L]);
}
}
else
for(L=0;L<prime;L++)
printf("%d ",ch2[L]);

printf("\n\n");
}
return 0;
} [quote][/quote]
Sanjana
mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:

### Re: 406 got TLE,help me!!

kolpobilashi wrote:i got TLE 4 dis code,and cant get the reason, anybody tell me y n wats de solution.....
Nice English!!!

Code: Select all

``````for(i=0;i<=1003;i++)
ch1[i]=isPrime(i);``````
Your array size is 1003. So what should be the last index? Is it OK to be i=1003 and trying to index ch1?
kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am