Hi. I am trying to write a program that can find all the prime numbers in interval of the [a, b] like, where a and b are expected to be kind of large.
I didn't have much luck on finding loads of help on the Internet, though, so I am asking you to help. What I look for is not Erathostene's sieve as it can find the primes up to N, let's say, but starting from 2, not a variable M, let's say... and I seem to be unable to modify it the way I need to. I have read something about representing a number N as N = 30.q + r or something of the like. . . however, I am not completely sure I get it, at all? ? ?

I thank you for paying time and attention.

How large will a and b be? Outside the max values stored by typical data types? Do you have any code you're working with?

Sadly, I am not a mathemation and prime number seives are not my focus, but I can provide you with what I know.

Small number primes, I believe you know more than I do.

On large number primes (those greator than 512 bits), there is no method that can determine if a number is prime in a resonable time. I was answering someone elses question which is similar in the prime number area, where it took 3 universities 11 months to factor a special form composite number.

However, if you are dealing with large primes, miller-rabin primarilty test could be used. The input is a number, and a probability that the number reports as prime and is really composite. So using it, you could simply loop on all values between A and B which do not end in 0,2,4,5,6,8 and perform the test on them. (skip all even numbers and skip 5 because any number x5 either ends in 5 or 0).

Anyways, I think this is slightly different from what you were hoping, but sadly this is the only primality test I know of that can handle the larger prime numbers.

http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

If you do decide to use it, you should consider testing against all primes less than 1024 as well. I read somewhere that there are some very large composite numbers which can pass the test, but not be prime. Also testing against those smaller primes, is faster than running the test.

Salindor

Salindor

a is not greater than 10^6 and b - 10^9. Long long would work, I guess?

That's the main problem, actually - I have no clue where to begin from. And this N = 30.q + r lost me totally.

a long long is not outside the range of using a prime crawler.

What is a prime crawler you ask. Well its a program which uses Sieve of Eratosthenes to generate a table of primes less than square root of you maximum number -- then it uses this table to test the larger numbers.

So lets see the sqrt of 10^9 is about 31622 and the 3402'rd prime number is is 31627 .. so a table of 3402 prime numbers will find any prime up to 10^9, the sqrt of 10^10 is 100000 and the 9593'th prime number is 100003 so a table of 9593 primes will get you prime all the way to 10^10.

the "crawler" part of the program is the idea that it adds numbers to the table as it finds them, thus extending its reach. Once you reach the end of your table you can only find primes less then square of the largest prime.

Since you are dealing with relatively small numbers this method should not be too time intensive (if not a little memory intensive). If you find that the program is still too slow you can use Fermat primality test or another heuristic algorithm to speed though most composites, leaving the loop though 9593 known primes for only numbers suspected of being prime.

to give you an idea of how fast this might be, my program (on an older Pentium processor) found the first prime > 100000 in well less then a second. so it found the first 9593 primes in less than a second. it took about 15 seconds to find 252097800623 the 10000000000'th prime. (I wonder how much that Fermat test would cut off of that?)