Fast method Prime number generation

I am trying to write the code for PRIME1 problem here http://www.spoj.pl/problems/PRIME1
But I am getting a time limit exceeded error. I have employed the most basic algorithm for generating prime numbers. What is the faster methods? Any references?

Please, share your code if you want some help or describe better your approach.

What does “the most basic algorithm for generating prime numbers” mean? You are asking for each i if it is prime? What is complexity of such algorithm? O(sqrt(maxp)*(n-m)), that’s 10^10 operations you want to perform in 6 seconds… I guess you can assume that you can perform at most 10^6 operations in second (depends on HW, Pyramid is really slow).

You can read this article, but this is only for inspiration, maxn is too big for this.

1 Like

I have got AC on this code. Read it. It may help you.

2 Likes

This question can be done by Sieve of Eratosthenes.
(Given that you sieve only the numbers between M and N)

//