3

I understand the prime sieves find primes less than a value, say n. I also know that trial division is woefully inefficient for any sort of large number. Is there any way of efficiently finding primes, without the arbitrary limit that a sieve needs to work? A function to generate primes continuously.

MagikCow
  • 133
  • I know of one made in python, the basic idea remember the primes you already know with those produce as needed all of its multiples, then the next number to be checked is compared against those to determined if its prime or not. Is basically a extension to the Sieve of Eratostenes Here is that code – Copperfield Sep 14 '16 at 19:25
  • 2
    If primes were that easy to locate/generate, there would be no conjecture like RH. Moreover, it is well-known that no polynomial may assume prime values for any integer or positive integer value of its variable. – Jack D'Aurizio Sep 14 '16 at 19:39

1 Answers1

1

There is no exact way to generate primes continuously.

Though there is ways better than others. That's why almost all the big primes we find nowadays are Mersenne primes, which are primes of the form

$$2^p-1$$

where $p$ is also a prime number. We do that because Mersenne numbers have a very efficient criteria to determine whether or not they are prime. It is called Lucas primality test.

For Lucas primality test, you take a Mersenne number, and you have to check that:

$$\forall q\mid p-1,\quad 2^{(p-1)/q}\not\equiv 1 \pmod p.$$

If a number passes the test, then it is a prime number.

E. Joseph
  • 14,843