# prime generator using sieve algorithm

Question->http://www.codechef.com/problems/PRIME1
My code is giving correct answer for all the test cases i have tried .Also for the extreme case i.e
when m=999900000 and n=1000000000 it running absolutely fine.I m not able to find the bug .Plz help

``````#include <iostream>
#include<vector>
#include<cmath>
using namespace std;

int main()
{
long long int i,n,k,t,m;
cin>>t;
if(t<=10){
while(t--)
{
cin>>m>>n;
vector<bool> v1;
for(i=0;i<=n-m;i++)
{
v1.push_back(0);  //corresponding to each value assigning 0 value
}
for(i=2;i<=sqrt(n);i++)
{
if (m/i-i>=0){k=(m/i)-i;}//this if else condition help k to reach nearthe "m" value
else{k=m/i;}           //so that we can skip the terms before m
while(i*i+k*i<m){k++;}

while(i*i+k*i<=n)
{
v1[i*i+k*i-m]=1; //making all composite no's 1
k++;
}

}

if(m==1){v1[0]=1;}// condition to eliminate 1 as a prime

for(i=0;i<=n-m;i++)
{
if(!v1[i]){cout<<i+m<<"\n";}// all the no's which are still set to 0 are prime
}
cout<<"\n";
}
}
return 0;
}``````

Hai, for this case:

1

2 10

2

3

4

5

7

‘4’ should not be there in the output as ‘4’ is not prime.

2 Likes

thanks @achait for finding the bug.

//