7
$\begingroup$

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!

$\endgroup$
4
  • 4
    $\begingroup$ How about en.wikipedia.org/wiki/Sieve_of_Eratosthenes? Could you be more specific about what properties you want the algorithm to have? $\endgroup$ Jun 30, 2012 at 2:32
  • $\begingroup$ The intention of the algorithm is: Given a first/seed prime number, generate the next 'n' primes $\endgroup$
    – ZEE
    Jul 1, 2012 at 22:25
  • $\begingroup$ I Know the "Sieve of Eratostenes", it was probably one of the first I understood fully. I can use it to this purpose but demands many interactions... I'm looking for a more elegant solution... formula based perhaps... $\endgroup$
    – ZEE
    Jul 1, 2012 at 22:28
  • $\begingroup$ Will you please edit your question to add relevant information about what you are actually looking for? $\endgroup$ Jul 1, 2012 at 22:29

7 Answers 7

5
$\begingroup$

"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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ In this case we have to calculate the gcd... and how to calculate the gcd if we do not know $a_{n+1}$ yet??? $\endgroup$
    – ZEE
    Jul 1, 2012 at 22:20
  • 1
    $\begingroup$ The gcd calculation uses $a_{n-1}$ not $a_{n+1}$. $\endgroup$
    – tomcuchta
    Jul 1, 2012 at 23:07
  • $\begingroup$ Note that Rowland's method doesn't generate the "next primes". The sequence begins: 1,1,1,5,3,1,1,... $\endgroup$ May 14, 2013 at 15:44
4
$\begingroup$

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:

enter image description here

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:

enter image description here

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

$\endgroup$
3
  • $\begingroup$ Interesting... but not what I loof for... Thx, $\endgroup$
    – ZEE
    Jul 1, 2012 at 22:16
  • $\begingroup$ @ZEE: Could you please explain why not? $\endgroup$ Jul 1, 2012 at 22:31
  • $\begingroup$ @ZEE: This polynomial: pastebin.com/bEmPjqdQ when set equal to zero for x >= 17, gives 50 consecutive prime numbers starting at 17. $\endgroup$ Jul 2, 2012 at 10:46
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nope... my question objective was: given a first prime, generate the 'n' next primes. But thanks for the link ;-) $\endgroup$
    – ZEE
    Jul 1, 2012 at 22:08
0
$\begingroup$

Here you go - give any random number as an input, and it will give you the next prime after it. You can feed its output into itself to make a list. It basically uses Fermat's Little Theorem to heuristically check if each number is a prime, and keeps checking successive odd numbers until you get to something that works.

It has a very small chance of failure (eg. nextprime(560) = 561, but 561=3*11*17), but if you go high enough this becomes negligible in practice.

def modexp(b,e,n):
  if e == 0: return 1
  elif e%2 == 0: return modexp(b,e/2,n)**2 % n
  else: return b*modexp(b,e/2,n)**2 % n

def nextprime(inp):
  inp += inp%2 + 1
  while modexp(2,inp,inp) != 2 or modexp(3,inp,inp) != 3: inp += 2
  return inp
$\endgroup$
1
  • $\begingroup$ what are you trying to ask? $\endgroup$
    – Lost1
    May 14, 2013 at 15:25
0
$\begingroup$

Looking at this from a computer science like perspective, I would use the following algorithm to generate my list of primes.

input = (17,50)
    if 17 is prime: 
    counter = 1
    from_seed = seed
      while counter <= 50
        if from_seed is prime
         print from_seed
         counter+1
         from_seed+1
        else
       from_seed+1

To check if the number is prime then I would do the very simple

boolean isPrime (n)
   if n <= 2
     return false
   else
     for i .. sqrt(n)
       if n % i == 0
         return false 
   return true

This will very easily generate what you want. Below I have the working Java code, if you wish to implement it.

public class PrimeGeneration_Seed {

    public static void main(String[] args) {
        prime_Generation(17,50);
    }

    public static void prime_Generation (int seed, int number_of_primes) {
        if(!isPrime(seed)) {
            System.out.println("Seed is not prime"); // simple out statement saying that "seed" is not prime
        }else {
            int primes = 1;
            int from_seed = seed;
            while(primes <= number_of_primes) {
                if(isPrime(from_seed)) {
                    System.out.println(from_seed);
                    primes++;
                    from_seed++;
                }else {
                    from_seed++;
                }
            }
        }

    }

    // simple primality test - can be modified to be more complex and more efficient
    public static boolean isPrime(int n) {
        if(n <= 2){
            return false;
        }else {
            for(int i = 2;i<=Math.sqrt(n);i++) {
                if(n % i == 0) {
                    return false;
                }
            }
        }
        return true;
    }

}

You can access this link to see the program in action.

$\endgroup$
0
$\begingroup$

It is possible to do this using Alpertron. If you input

x=17;x=n(x);i-50;x.

into its Batch factorization tool, it will output

17 is prime
19 is prime

[...snipped the list...]

257 is prime
263 is prime

To make it more interesting, we could try

x=n(10^100);x=n(x);i-50;x.

which finds the first 50 primes after $10^{100}$. It takes a few seconds on my computer, but gives:

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000267 is prime
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000949 is prime

[...snipped the list...]

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000016431 is prime
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000016443 is prime

I believe these are Rabin-Miller pseudoprimes (which would be extremely unlikely to be composite), but if this is not suitable the output can be formally checked using e.g. Primo.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .