Page 9 of 13

Posted: Sat Aug 16, 2008 8:38 pm
rhsumon ,
3 1
3 1: 2 -858993460
my AC output::
3 1
3 1: 2
cheek it carefully

Rajib, sust

### Re: 406 - Prime Cuts

Posted: Sat Aug 16, 2008 9:02 pm
Thanks Ragib
Silly Mistake.
Anyway r u in CSE if then which Semester
Mail Me
rhsumon@gmail.com
Thanks Again

### Re: 406 - Prime Cuts

Posted: Fri Nov 14, 2008 12:46 pm
Can anyone tell me why I awalays get Time limit exceeded
Thanks

Code: Select all

``````#include <stdio.h>
int main()
{
int prime[200]={1},n,c,i,j,num=1,x;
while(scanf("%d %d",&n,&c)!=EOF)
{

for(i=2;i<=n;i++)
{
for(j=2;j<=i;j++)
if(i%j==0 && j!=i)
{
break;
}
else if(i%j==0 && j==i)
{
prime[num]=i;
num++;
}
}
printf("%d %d:",n,c);
if(2*c>n)
{
for(x=0;x<num;x++)
printf(" %d",prime[x]);
}
else if(2*c<n && (num)%2==1)
{
{
for(x=((num/2)-(c/2-1)-1);x<(num/2+c+1)-1;x++)
printf(" %d",prime[x]);
}

}
else if(2*c<n && num%2==0)
{
{
for(x=((num/2)-c);x<(num/2+c);x++)
printf(" %d",prime[x]);
}
}
printf("\n\n");
num=1;

}

return 0;
}``````

### Re: 406 - Prime Cuts

Posted: Fri Nov 14, 2008 12:52 pm
To peterwen1990

for loop upto n.
It is a slow process.
You can check upto sqrt(n).

Code: Select all

``````for(i=2;i<=n;i++)
{
for(j=2;j<=sqrt(i);j++)
if(i%j==0 && j!=i)
{
break;
}
else if(i%j==0 && j==i)
{
prime[num]=i;
num++;
}
}

``````
May be this is the reason.
Precalcution for prime number with seive method will be faster.

### Re: 406 - Prime Cuts

Posted: Mon Nov 17, 2008 9:49 am
lnr wrote:To peterwen1990

Thank you.That is my program problem.

### Re: 406 - Prime Cuts

Posted: Mon Jan 05, 2009 10:04 pm

Code: Select all

``````#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int main()
{
int m,n,sz;
int p;

vector<bool> v;
vector<int> vi;

while(cin>>m>>n)
{
vi.clear();
v.resize(m+1,0);
p=sqrt(m);

v[0]=0;
v[1]=0;

for(int i=2;i<=p;i++)
if(!v[i])
for(int j=i*i;j<=m;j+=i)
v[j]=1;

cout<<m<<" "<<n<<":";

int sum=0;

for(int i=1;i<v.size();i++)
{
if(!v[i])
{
vi.push_back(i);
}
}

sz=vi.size();

if(vi.size()%2==0)
{
if(sz/2-n/2>=0)
{
for(int i=(sz/2)-n;i<(n+sz/2);i++)
{
if(i==vi.size())
break;

cout<<" "<<vi[i];
}
}
else
{
for(int i=0;i<vi.size();i++)
cout<<" "<<vi[i];
}
}
else
{
if((sz/2)-(2*n-2)/2>=0)
{
for(int i=(sz/2)-(2*n-2)/2;i<=((2*n-2)/2+sz/2);i++)
{
if(i==vi.size())
break;

cout<<" "<<vi[i];
}
}
else
{
for(int i=0;i<vi.size();i++)
cout<<" "<<vi[i];
}
}

cout<<endl<<endl;
}
}

``````

### prime cuts- 406 getting presentation error

Posted: Thu Mar 19, 2009 12:15 am

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

int main(void)
{
int a[1001];
int i,j,n,k,c,m,q,r;
while(scanf("%d%d",&n,&c)==2)
{
k=0;
a[0]=0;
a[1]=1;
for(i=2;i<=n;i++)
{
a=1;
}
for(i=2;i<=sqrt(n);i++)
{
if(a==0)
{
continue;
}
for(j=2;i*j<(n+1);j++)
{
a[i*j]=0;
}
}
for(i=0;i<=n;i++)
{
if(a==1)
{
k++;
}
}
if(k%2==0)
{
r=2*c;
}
else
{
r=2*c-1;
}
if(r>k)
{
printf(" %d %d: ",n,c);
for(i=1;i<=n;i++)
{
if(a==1)
{
printf("%d ",i);
}
}
printf("\n\n");
}
else
{
q=(k-r)/2;
m=0;
for(i=1;m<q;i++)
{
if(a==0)
{
continue;
}
else
{
a=0;
m++;
}
}
m=0;
for(i=n;m<q;i--)
{
if(a==0)
{
continue;
}
else
{
a=0;
m++;
}
}
printf(" %d %d: ",n,c);
for(i=1;i<=n;i++)
{
if(a==1)
{
printf("%d ",i);
}
}
printf("\n\n");
}
}
return 0;
}

### Re: 406 - Prime Cuts

Posted: Tue Jun 09, 2009 6:54 am
some test cases

Code: Select all

``````1 1
2 1
3 2
4 3
5 2
6 3
7 2
8 2
9 2
10 9
11 9
12 4
13 4
14 3
15 8
16 13
17 10
18 16
19 14
20 17
21 20
22 8
23 9
24 15
25 2
26 3
27 7
28 1
29 14
30 10
31 10
32 24
33 32
34 15
35 18
36 4
37 11
38 34
39 18
40 27
41 35
42 33
43 32
44 10
45 12
46 43
47 40
48 21
49 22
50 15
``````
output

Code: Select all

``````1 1: 1

2 1: 1 2

3 2: 1 2 3

4 3: 1 2 3

5 2: 1 2 3 5

6 3: 1 2 3 5

7 2: 2 3 5

8 2: 2 3 5

9 2: 2 3 5

10 9: 1 2 3 5 7

11 9: 1 2 3 5 7 11

12 4: 1 2 3 5 7 11

13 4: 1 2 3 5 7 11 13

14 3: 2 3 5 7 11

15 8: 1 2 3 5 7 11 13

16 13: 1 2 3 5 7 11 13

17 10: 1 2 3 5 7 11 13 17

18 16: 1 2 3 5 7 11 13 17

19 14: 1 2 3 5 7 11 13 17 19

20 17: 1 2 3 5 7 11 13 17 19

21 20: 1 2 3 5 7 11 13 17 19

22 8: 1 2 3 5 7 11 13 17 19

23 9: 1 2 3 5 7 11 13 17 19 23

24 15: 1 2 3 5 7 11 13 17 19 23

25 2: 5 7 11 13

26 3: 3 5 7 11 13 17

27 7: 1 2 3 5 7 11 13 17 19 23

28 1: 7 11

29 14: 1 2 3 5 7 11 13 17 19 23 29

30 10: 1 2 3 5 7 11 13 17 19 23 29

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

32 24: 1 2 3 5 7 11 13 17 19 23 29 31

33 32: 1 2 3 5 7 11 13 17 19 23 29 31

34 15: 1 2 3 5 7 11 13 17 19 23 29 31

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

36 4: 3 5 7 11 13 17 19 23

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

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

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

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

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

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

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

44 10: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43

45 12: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43

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

47 40: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

48 21: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

49 22: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

50 15: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

``````

### Re: prime cuts- 406 getting presentation error

Posted: Fri Oct 16, 2009 7:06 am
printf(" %d %d: ",n,c);
printf("%d ",i);
printf(" %d %d: ",n,c);
printf("%d ",i);

you are printing one extra space after the last prime number in each test case..
replace those lines with these...

printf(" %d %d:",n,c);
printf(" %d",i);
printf(" %d %d:",n,c);
printf(" %d",i);

I hope this will help...

### Re: 406 - Prime Cuts

Posted: Sat Apr 17, 2010 3:10 pm
What's the wrong with this code? plz help me..........

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>

using namespace std;

//#define longlong long long
//#define longlong __int64
#define max 1002

bool prime[max];
//longlong pr[max];
long int np[max];

void sieve()
{
long int i,j;

for(i=2;i<max;i++)
{
prime=true;
}

for(i=2;i<max;i++)
{
if(prime)
for(j=i*2;j<max;j+=i)
prime[j]=false;
}
}

int Total(int n)
{
int i, total = 0,j=0;

np[j]=1;
j++;
total++;
for(i = 2; i<=n; i++)
{
if(prime)
{
np[j]=i;
total++;
j++;
}
}
}

int main()
{
//longlong j;
sieve();
long int n,c,i,j,s,t,x;
while(scanf("%d %d",&n,&c)!=EOF)
{
i=Total(n);

if(c*2>i)
{
printf("%ld %ld:",n,c);
for(j=0;j<i;j++)
printf(" %ld",np[j]);
}

else if(i%2==1)
{
j=(c*2)-1;
s=((i/2)-(j/2)+1);
t=((i/2)+(j/2)+1);
printf("%ld %ld:",n,c);

for(x=s;x<=t;x++)
{
printf(" %ld",np[x-1]);
}
}
else
{
j=c*2;
s=((i/2)-(j/2)+1);
t=((i/2)+(j/2));

printf("%ld %ld:",n,c);

for(x=s;x<=t;x++)
{
printf(" %ld",np[x-1]);
}
}
printf("\n\n");

}

return 0;
}

### Re: problem 406

Posted: Wed Jul 21, 2010 7:16 pm
geting wa!!! why wa???

Code: Select all

``````#include <cstdio>
#include <iostream>
#define MAX 1001
#define sq 32
using namespace std;

int arr[MAX];
int v[MAX];
int prime[MAX];
void scive()
{
arr[0]=1;
for(int i=3;i<=sq;i+=2)
{
for(int j=2;i*j<MAX;j++)
arr[i*j]=1;
}
v[0]=0;
v[1]=1;
v[2]=2;
prime[0]=1;prime[1]=2;
int Ind=3;
for(int i=3,in=2;i<MAX;i+=2)
{
if(arr[i]!=1)
{
v[Ind]=v[Ind-1]+1;Ind++;
v[Ind]=v[Ind-1];
prime[in++]=i;
}
else
{
v[Ind]=v[Ind-1];
Ind++;
v[Ind]=v[Ind-1];
}
Ind++;
}
}
int main()
{
int n,c,mid;
scive();
while(scanf("%d%d",&n,&c)==2)
{
int start,end;
if(v[n]%2==0)
{
mid=v[n]/2;
start=v[n]/2-c+1;
end=v[n]/2+c;
}
else
{
mid=(v[n]+1)/2;
start=mid-(c-1);
end=mid+c-1;
}
if(mid<c)start=1,end=v[n];
printf("%d %d:",n,c);
for(int i=start;i<=end;i++)
cout<<" "<<prime[i-1];
cout<<endl;
}
return 0;
}
``````

### Re: problem 406

Posted: Wed Jul 21, 2010 8:34 pm
Have you noticed this --- >
Each line of output should be followed by a blank line.
Else then everything is ok . Just add a newline after each output.

### Re: problem 406

Posted: Sat Jul 24, 2010 9:38 pm
still WA after change blank line. I tried also blank line after every case (cout<<endl<<endl) but both are WA! I am confused

Code: Select all

``````#include <cstdio>
#include <iostream>
#define MAX 1010
#define sq 32
using namespace std;

int arr[MAX];
int v[MAX];
int prime[MAX];
void scive()
{
arr[0]=1;
for(int i=3;i<=sq;i+=2)
{
for(int j=2;i*j<MAX;j++)
arr[i*j]=1;
}
v[0]=0;
v[1]=1;
v[2]=2;
prime[0]=1;prime[1]=2;
int Ind=3;
for(int i=3,in=2;i<MAX;i+=2)
{
if(arr[i]!=1)
{
v[Ind]=v[Ind-1]+1;Ind++;
v[Ind]=v[Ind-1];
prime[in++]=i;
}
else
{
v[Ind]=v[Ind-1];
Ind++;
v[Ind]=v[Ind-1];
}
Ind++;
}
}
int main()
{
int n,c,mid,ca=1;
scive();
while(scanf("%d%d",&n,&c)==2)
{
if(ca>1)cout<<endl; //blank line between testcase
int start,end;
if(v[n]%2==0)
{
mid=v[n]/2;
start=v[n]/2-c+1;
end=v[n]/2+c;
}
else
{
mid=(v[n]+1)/2;
start=mid-(c-1);
end=mid+c-1;
}
if(mid<(c-1))start=1,end=v[n];
printf("%d %d:",n,c);
for(int i=start;i<=end;i++)
cout<<" "<<prime[i-1];
cout<<endl;
//cout<<endl; tried this also. but no luck
ca++;
}
return 0;
}

``````

### Re: problem 406

Posted: Sun Jul 25, 2010 4:07 pm
shantanu18 wrote:still WA after change blank line. I tried also blank line after every case (cout<<endl<<endl) but both are WA! I am confused

if(ca>1)cout<<endl; //blank line between testcase <----- remove this!!

and at the end of each case, try this..

cout<<endl;
cout<<endl;

Remove your code if you get AC

### Re: problem 406

Posted: Tue Jul 27, 2010 4:25 am
It was not only blank line problem also a logical problem. I got ac. Thanks everybody for helping me. (i can't edit my post so can not delete my code)