44

How can I find the least prime number greater than a given number? For example, given 4, I need 5; given 7, I need 11.

I would like to know some ideas on best algorithms to do this. One method that I thought of was generate primes numbers through the Sieve of Eratosthenes, and then find the prime after the given number.

0

8 Answers 8

30

Source: Wikipedia

Bertrand's postulate (actually a theorem) states that if n > 3 is an integer, then there always exists at least one prime number p with n < p < 2n − 2. A weaker but more elegant formulation is: for every n > 1 there is always at least one prime p such that n < p < 2n.

So if I am given a number, say n, than I can check in the range (n, 2*n) [open interval excluding n and 2*n]

int GetNextPrime(int n)
{
    bool isPrime = false;
    for (int i = n; i < 2 * n; ++i)
    {
    // go with your regular prime checking routine
    // as soon as you find a prime, break this for loop
    }
}
3
  • 16
    So, if you're guaranteed to find a prime before the loop ends, then couldn't this just be a while(true) and eliminate all the comparisons?
    – Neil Traft
    Mar 21, 2014 at 6:07
  • @Neil: Great idea! Post it as an answer. Mar 21, 2014 at 16:23
  • too much time complexity Nov 26, 2020 at 4:33
9

Some other methods have been suggested and I think that they are good, but it really depends on how much you want to have to store or compute on the spot. For instance if you are looking for the next prime after a very large number, then using the Sieve of Eratosthenes might not be so great because of the number of bits you would need to store.

Alternatively, you could check all odd integers between (and including) 3 and sqrt(N) on every number odd number N greater than the input number until you find the correct number. Of course you can stop checking when you find it is composite.

If you want a different method, then I would suggest using the Miller-Rabin primality test on all odd numbers above the input number (assuming the input is > 1) until a prime is found. If you follow the list, located at the bottom of the page, of numbers a to check for the given ranges, you can significantly cut down on the number of as you need to check. Of course, you might want to check at least a few of the smaller primes (3,5,7,11 for instance) before checking with Miller-Rabin.

7

I have done this before.

Only addition is Bertrand's Theorem from Rajendra's Answer.

And readymade code from topcoder.

#include<iostream>
using namespace std;

/* This function calculates (ab)%c */
int modulo(int a,int b,int c){
    long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return x%c;
}

/* this function calculates (a*b)%c taking into account that a*b might overflow */
long long mulmod(long long a,long long b,long long c){
    long long x = 0,y=a%c;
    while(b > 0){
        if(b%2 == 1){
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}

/* Miller-Rabin primality test, iteration signifies the accuracy of the test */
bool Miller(long long p,int iteration){
    if(p<2){
        return false;
    }
    if(p!=2 && p%2==0){
        return false;
    }
    long long s=p-1;
    while(s%2==0){
        s/=2;
    }
    for(int i=0;i<iteration;i++){
        long long a=rand()%(p-1)+1,temp=s;
        long long mod=modulo(a,temp,p);
        while(temp!=p-1 && mod!=1 && mod!=p-1){
            mod=mulmod(mod,mod,p);
            temp *= 2;
        }
        if(mod!=p-1 && temp%2==0){
            return false;
        }
    }
    return true;
}

int main(int argc, char* argv[])
{

    int input = 1000;
    int i = 0;

    if(input%2==0)
        i = input+1;
    else i = input;

    for(;i<2*input;i+=2) // from Rajendra's answer
        if(Miller(i,20)) // 18-20 iterations are enough for most of the applications.
            break;
    cout<<i<<endl;

    return 0;
}
2

I generally see two ways to do that.

  • counting up from n and checking every number for it being prime or not
  • generate prime numbers and check against them. (maybe do that beforehand, use an existing primenumber table, so you don't need to calculate stuff everytime (well as long as N is within the range of your pre-calculated table)

maybe this helps too, (simply replace 2 with your given Number and N with infinite :D ) finding all prime numbers between 2 and N

1

I'd have a big lookup table and then search it for the given number and respond with the next in the sequence.

Works well if there is a known (sensible) upper limit on the range of given numbers.

2
  • just think, if i want to find a closest large prime number of N having type unsigned long then lookup table might not have that amount of entry. Nov 26, 2020 at 4:38
  • 1
    Hence my second sentence.
    – Martin
    Nov 30, 2020 at 18:20
1
        int length = number;
        bool flag = true;
        for (int i = number; i <= length; i++)
        {
            for (int k = 2; k < length; k++)
            {
                if (i != k && i % k == 0)
                {
                    flag = false;
                    length = length + 1;
                    break;
                }
            }

            if (flag)
            {
                Console.WriteLine(i);
            }
            flag = true;
        }
1
  • 3
    Please don't post only code as an answer, but also provide an explanation of what your code does and how it solves the problem of the question. Answers with an explanation are usually more helpful and of better quality, and are more likely to attract upvotes. Feb 26, 2021 at 7:02
0

import java.util.Scanner;

public class Practice11 {

public static void main(String[] args) 
{
    int count=0;
    Scanner scan=new Scanner(System.in);
    System.out.println("enter a number:");
    int a=scan.nextInt();
    
   a: for(int i=a+1;i<a+1000;i++)// a+1000 because it will check up to 
                                //that number to find the next prime 
    {
        count=0;
        for(int j=2;j<i;j++)
        {
            if(i%j==0) //this will check if a number is divisible by another 
                       // number
            {
            count++;
            }
            else
            {
            }
           }
        if(count==0)
        {
            System.out.println(i);
            break a;//this line will break the loop so you get only one prime 
                      //number 
        }
    }

}

}

-1
private static int nextPrime(int num) {
        num++;
        for (int i = 2; i <num; i++) {
            if(num%i == 0) {
                num++;
                i=2;
            } else{
                continue;
            }
        }
        return num;
    }
1
  • There is issue of time complexity. Nov 26, 2020 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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