Prime number generator, how to make

Question

Can anybody point me an algorithm to generate prime numbers, I know of a few ones (Mersenne, Euclides, etc.) but they fail to generate much primes...

The objective is: given a first prime, generate the 'n' next primes. But thanks for the link ;-)

for example : primes( 17, 50 ) -> Generate 50 consecutive primes starting at 17

and do not fail any prime in this 50... no holes!

Answer 1

Here is a paper that contains a prime recurrence defined by

$$a_{n+1} = a_n + gcd(n,a_{n-1}),$$

where $gcd$ is the greatest common divisor function.

A favorite of mine is given by Mills' theorem, but since we cannot compute the number directly (yet...?), it is not feasible to generate primes with it.

Answer 2

The fundamental theorem of arithmetic as a recurrence gives all the primes. But of course, it involves a lot of 1:s which are not primes, and also it is a 2-dimensional matrix.

The recurrence in European dot-comma English Excel to be entered in cell A1, is:

=IF(COLUMN()=1;1;IF(ROW()=COLUMN();ROW()/PRODUCT(INDIRECT(ADDRESS(ROW();1)
&":"&ADDRESS(ROW();COLUMN()-1)));IF(ROW()>COLUMN();INDIRECT(ADDRESS(ROW()
-COLUMN();COLUMN()));"")))

which outputs:

where the sequence in the diagonal is the exponentiated von Mangoldt function.

---

Edit 29.3.2013: A more Riemann zeta function like table can be done with the recurrence:

=IF(ROW()>=COLUMN();IF(AND(ROW()=1;COLUMN()=1);1;IF(COLUMN()=1;
ROW()/PRODUCT(INDIRECT(ADDRESS(ROW();2)&":"&ADDRESS(ROW();ROW())));
IF(MOD(ROW();COLUMN())=0;INDIRECT(ADDRESS(FLOOR(ROW()/COLUMN();1);
1));"")));"")

which outputs:

where again the exponentiated von Mangoldt function is found in the first column. However this second recurrence uses the floor function.

Answer 3

When you mentioned prime numbers, I thought you would like quite large prime numbers. Thinking from applications in computer science, I thought cryptography would give an answer, especially RSA that uses large prime numbers.

Indeed, the crypto.SE had the following question that I believe solves your problem: https://crypto.stackexchange.com/questions/71/how-can-i-generate-large-prime-numbers-for-rsa

Edit:

As you mentioned, you are interested in generating the n smallest primes that are greatest than a certain number. There are some ways to do that, although I cannot judge how efficient they are computationally (some require knowing all primes that are smaller than the one you are looking for). I suggest consulting the excellent article on wikipedia http://en.wikipedia.org/wiki/Formula_for_primes , as well as the related links and references.

Answer 4

"The objective is: given a first prime, generate the $n$ next primes."

This is equivalent to, "given an integer $N$, find the smallest prime exceeding $N$."

People do this all the time, for example, here is a tabulation of the smallest prime exceeding $10^m$ for various values of $m$. But there's no especially clever way to do it. In effect, you look at $N+1,N+2,N+3,\dots$ until you find a prime. You can save some work by sieving, but you already know that. If you want to find, say, the first 50 primes after $10^{100}$, no doubt you'd save a lot of work by doing some sieving, but in the end there would be a lot of numbers that get through the sieve, and you'd have to fall back on the standard primality tests to see which ones are actually prime.

I guess the other thing you can do is use the Prime Number Theorem to estimate how far you have to sieve to have a good chance of catching the next 50 primes. Roughly speaking, one number in every $\log N$ will be prime, so if you go out to $N+100\log N$ you should have an excellent chance of catching the next 50 primes.