Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
4  
How about en.wikipedia.org/wiki/Sieve_of_Eratosthenes? Could you be more specific about what properties you want the algorithm to have? –  Jonas Meyer Jun 30 '12 at 2:32
    
The intention of the algorithm is: Given a first/seed prime number, generate the next 'n' primes –  ZEE Jul 1 '12 at 22:25
    
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... –  ZEE Jul 1 '12 at 22:28
    
Will you please edit your question to add relevant information about what you are actually looking for? –  Jonas Meyer Jul 1 '12 at 22:29
add comment

7 Answers 7

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

share|improve this answer
add comment

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.

share|improve this answer
    
In this case we have to calculate the gcd... and how to calculate the gcd if we do not know $a_{n+1}$ yet??? –  ZEE Jul 1 '12 at 22:20
1  
The gcd calculation uses $a_{n-1}$ not $a_{n+1}$. –  tomcuchta Jul 1 '12 at 23:07
    
Note that Rowland's method doesn't generate the "next primes". The sequence begins: 1,1,1,5,3,1,1,... –  Douglas S. Stones May 14 '13 at 15:44
add comment

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.

share|improve this answer
    
Interesting... but not what I loof for... Thx, –  ZEE Jul 1 '12 at 22:16
    
@ZEE: Could you please explain why not? –  Jonas Meyer Jul 1 '12 at 22:31
    
@ZEE: This polynomial: pastebin.com/bEmPjqdQ when set equal to zero for x >= 17, gives 50 consecutive prime numbers starting at 17. –  Mats Granvik Jul 2 '12 at 10:46
add comment

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
share|improve this answer
    
what are you trying to ask? –  Lost1 May 14 '13 at 15:25
add comment

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: http://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.

share|improve this answer
    
Nope... my question objective was: given a first prime, generate the 'n' next primes. But thanks for the link ;-) –  ZEE Jul 1 '12 at 22:08
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.