# prime 1 wa

what is the problem in the code ???

`````` #include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
#define max 32000
#define ll long long int
bool prime[max];
void seive()
{
prime[0]=prime[1]=false;
for(int i=2;i<max;i++)
{
prime[i]=true;
}
for(int i=2;i<=sqrt(max);i++)
{
if(prime[i])
{
for(int j=2*i;j<max;j=j+i)
{
prime[j]=false;
}
}
}
}
int main()
{

int t;
//freopen("abc.txt","w",stdout);
cin>>t;
seive();
while(t--)
{
ll m,n;
cin>>m>>n;
if(m==1)
m++;
for(ll i=m;i<=n;i++)
{
ll temp=sqrt(i);
int flag=1;
for(ll j=2;j<=temp && prime[j];j++)
{

if(i%j==0)
{
flag=0;
break;
}
}
if(flag==1)
cout<<i<<endl;
}
}
}``````

I saw the output of your program on the sample input given with the problem .
You have ignored the instruction in the problem which says :
“Separate the answers for each test case by an empty line.”

yes it was one of the mistake.Now i have chaged the code but it is still a wrong ans.

In the for loop itself you are checking for prime[j] which will make it exit for loop at j = 4 . Hence
only multiples of 2 and 3 will not go to output , all other numbers will go to output .
This is the output of your program for primes from 1 to 100 :
2
3
5
7
11
13
17
19
23
25
29
31
35
37
41
43
47
49
53
55
59
61
65
67
71
73
77
79
83
85
89
91
95
97

1 Like

http://www.codechef.com/viewplaintext/1650624
i have made the changes. but it shows TLE . how to optimize it.

You are using the Sieve the first time around when calculating primes till 32000 .
You can use the sieve next time also when you have to find primes in a certain range . Just mark all of them as prime . Then using the prime numbers generated in step 1 , change the marks using the sieve method . Then finally output the numbers which are still marked as prime .
You can have a look at my solution , if you have trouble understanding what I have just explained .
My code is in Java though and since you are submitting in C++ you may have trouble understanding that too . Let me know if the idea of using Sieve again the second time is not clear to you . Will try to explain in more detail then . Good Luck !
My solution : http://www.codechef.com/viewsolution/1627177

1 Like
//