Generating Prime Numbers

How do i generate prime numbers upto a certain large number???
for eg primes upto 500000…
i have tried the sieve of Erastothanes and also the sieve of Atkin, but both are not sufficiently fast…

1 Like

Usually Sieve of Erastothenes with the correct implementation works for such limits.

Check out the first implementation given at the page MAXimal :: algo :: Решето Эратосфена

You might not have been using this kind of code for (int j = i * i; j <= n; j + = i) prime [j] = false; in the inner for loop and instead used for (int j = i+1; j <= n; j++) if(j%i == 0)prime [j] = false; This is an optimization a lot of new coders miss out and hence code an O(N^2) solution.

5 Likes

Sieve method is very efficient one to generate prime numbers. You might be missing a trick or two. Here is the link which tells how to generate prime numbers even more efficiently with bit-fields along with explanation. Look for the sieve method and see how it operates. There is also a segmented-sieve method which generates the prime numbers within a range.

2 Likes

It would be a better thing to store primes lessthen sqrtroot n in an array
and then use them to sieve the all primes less then n;
Or use the sieve of Atkin alogorithm .

3 Likes

@moody
The algorithm completely ignores any numbers divisible by two, three, or five. All numbers with an even modulo-sixty remainder are divisible by two and not prime. All numbers with modulo-sixty remainder divisible by three are also divisible by three and not prime. All numbers with modulo-sixty remainder divisible by five are divisible by five and not prime. All these remainders are ignored.
All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are prime if and only if the number of solutions to 4x2 + y2 = n is odd and the number is squarefree .
All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x2 + y2 = n is odd and the number is squarefree .
All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x2 ? y2 = n is odd and the number is squarefree .
None of the potential primes are divisible by 2, 3, or 5, so they can’t be divisible by their squares. This is why squarefree checks don’t include 22, 32, and 52.

Proof for square free theorem

4 Likes

Start with a list of the integers from 1 to n. From this list, remove all numbers of the form i + j + 2ij where: 1<=i=j<=sqrt(n);
remaining numbers which cannot be written as i+j+2ij gives us primes;
all remaining numbers k are doubled and incremented by 1 to get primes as (2k+1)
and 2k+1 is prime because it cannot be written as (2i+1)(2j+1)=2(2ij+i+j)+1;
This one is sieve of sundharam…!!

3 Likes

we got real problem with this. Taking more time and effort to find such solution. uh…

ปวดหลัง

Provide your code and specifications. Then may be we can help you optimize your code or suggest a better one!!

1 Like

There r sum things i hv omitted in this code due to max limit!
class primes
{
MAIN(String[] args)
{
int n=1000000;
int arr[]=new int[n];
try
{
for(int i=2;ii<n;++i)
{
if(arr[i]==0)
if(i
111i<=n)
for(int j=i
i;j<n;j+=i)
{
arr[j]=1;
}
}
}
catch(Exception ex)
{}

int cases=Integer.parseInt(br.readLine());
StringBuilder out=new StringBuilder(cases);
for(int h=0;h<cases;h++)
{
long sum=0;
int no=Integer.parseInt(br.readLine());
if(no<2)
{
out.append(“0”+"\n");
continue;
}

for(int k=0;k<no;k++)
{
if(arr[k]==0)
{
sum=sum+k;
}
}
out.append(sum+"\n");
}
System.out.printf("%s",out.toString());
}
}

thnx i did the same mistake…but even after correcting it is giving timelimt exceeded…the problem i am trying to solve is :

my solution is posted above!!! Please go through it and see if you can further optimize it…

@moody Since it is an ongoing contest I think it would not be appropriate to discuss any solution to this problem. If you are getting TLE constantly I would suggest that you try this first. Check if the pre-computation of sieve is working in time or not by breaking the execution of program after the sieve. If it TLEs then you need to either improve the sieve or change the approach to the problem, if it gives wrong answer then the (time limit - time for which the ran) is the time you have left to do the remaining tasks. See if you are good enough to do the remaining tasks in that time.

2 Likes

Thnx… Finally Done :slight_smile: !!!

I think the process will take too much time for large n!
I tried the sieve of Atkin but i couldn’t find an explanation as to how it was implemented…If you could please help me out by directing me to a link that explains how the sieve works…Thanks

1 Like

Of course it not a good process for large n.!!

2 Likes

ok that means for say n=73; 73%60=13
13%4=1;

so now i need to find solutions for 4x2+y2=73
now if the number of solutions is odd and is squarefree then 73 is prime…Have i understood it correctly???

2 Likes

i cant understand this one…lets say i=j=1; so i+j+2ij=4…(ok so far)

but for i=1,j=2 i+j+2ij=7 (a prime is removed) !!!

1 Like

@moody yes you do.

2 Likes

@moody Sorry the case (i==1&&j==1) is not considered .

1 Like

we got real problem with this. Taking more time and effort to find such solution. uh…