prime generator

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 :slight_smile:

U can find the algorithm in the below link :slight_smile:

Rabin Miller Primality Test

1 Like

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:slight_smile:

#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) :wink: and Yes if @punsa meant prime generator question in spoj this is perfect :slight_smile:

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…