Hi,
I am getting WA for PRIME1 problem, I have tried all the inputs given in all forums. My code is working for all the test cases with in the time limit. But I am getting WA in SPOJ site.
Can anyone help me to check what is wrong. If any test case which can crack this code will also be helpful.
Thanks in advance.
Code : ideone.com/Le7Kou
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
int a,b,n,i,j,times,lnp,n1;
n= 31625;
vector<char> prime(n+1,'P');
prime.at(0) = 'N';
prime.at(1) = 'N';
//Creating list of Primes till n prior to the input scan
for(i=2;i<=n;i=i+1)
{
for(j=i+i;j<=n;j=j+i)
{
prime.at(j) = 'N';
}
}
//Reading all inputs
cin >> times ;
while(times)
{
cin >> a;
cin >> b;
if (a>b)
{
times--;
cout << "\n" ;
continue;
}
if ( a <= n && b <= n)
{
for(i=a;i<=b;i++)
{
if (prime.at(i) == 'P')
cout << i << "\n" ;
}
times--;
continue;
}
//Finding primes in between the given numbers
vector<char> checklist((b-a)+1,'P');
n1 = sqrt(b);
for(i=2;i<=n1;i++)
{
if (prime.at(i) == 'P' )
{
lnp = (a/i)*i;
if (lnp == 0 )
lnp = i;
else if(lnp == i)
lnp = lnp + i;
else if(lnp<a)
lnp = lnp + i;
for(j=lnp;j<=b;j=j+i)
{
checklist.at(j-a) = 'N';
}
}
}
for(i=0;i<checklist.size();i++)
{
if(checklist.at(i) == 'P' )
cout << i+a << "\n" ;
}
times--;
cout << "\n" ;
}
return 0;
}