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.”

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

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 : CodeChef: Practical coding for everyone

1 Like

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

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