how to generate all the prime numbers upto 1000000000 in 6 seconds using c++
Here the range is very large and U cannot Use Sieve of eratosthenes method for finding the primes instead U can Use rabin miller primality test method
U can find the algorithm in the below link
this is one of my friends solution which was AC on spoj in .21 secs…he used segmented sieve…proved to be quite fast…if u have ne doubt related to the code…ask here…i’ll tell him to explain it to you…also you can refer to this link…
#include<stdio.h>
int main() {
long long int n,m;
int t;
scanf("%d",&t); //no of test cases
while(t--)
{
bool* a=new bool[100001];
scanf("%lld %lld",&m,&n);
if(n>100000)
{
long long int l,u;
u=n; //upper bound of the bool array
l=u-100000; //lower bound of the bool array
for(long long int i=2;i*i<=u;i++)
{
for(long long int j=(l+i-1)/i;j*i<=u;j++) //to find a factor just greater than or equal to l
{
if(!a[i*j-l]&&j!=1)
a[i*j-l]=true; //removing all factors(Segmented Sieve)
}
}
for(long long int i=m-l;i<=100000;i++)
if(!a[i])
printf("%lld\n",i+l);
}
else
{
a[0]=true;
a[1]=true;
for(long long int i=2;i*i<=n;i++)
{
for(long long int j=(m+i-1)/i;j*i<=n;j++)
{
if(!a[i*j]&&j!=1)
a[i*j]=true;
}
}
for(long long int i=m;i<=n;i++)
if(!a[i])
printf("%lld\n",i);
}
}
return 0;
}
The easiest way to to this is to check whether number is prime or not by following property:
A number n is prime if it is not divisible by numbers from 2 to sqrt(n). Remember do not calculate sqrt(n) during loop as it can cause TLE instead calculate sqrt(n) before loop.
But this can’t be used to find all the primes at a time instead helps in finding the primes in particular range(<= 1000001) and Yes if @punsa meant prime generator question in spoj this is perfect
for(long long int j=(l+i-1)/i;j*i<=u;j++) //to find a factor just greater than or equal to l
{
if(!a[i*j-l]&&j!=1)
a[i*j-l]=true; //removing all factors(Segmented Sieve)
}
please explain this part…