Optimal way to find next prime number (Java)

Question

I was asked to write a program to find next prime number in an optimal way. I wrote this code, but I could not find an optimal answer to it. Any suggestions?

public  static int nextPrime(int input) {

    input++;
    //now find if the number is prime or not

    for(int i=2;i<input;i++) {
        if(input % i ==0  ) {
            input++;
            i=2;
        }
        else{
            continue;
        }
    }
    return input;
}

Answer 1

public int nextPrime(int input){
  int counter;
  input++;
  while(true){
    int l = (int) sqrt(input);
    counter = 0;
    for(int i = 2; i <= l; i ++){
      if(input % i == 0)  counter++;
    }
    if(counter == 0)
      return input;
    else{
      input++;
      continue;
    }
  }
}

There is no need to check up on input number. It is enough to check up to the square root of a number. Sorry, I didn't remember the theorem name. Here we are incrementing the input for next prime.

The time complexity of this solution O(n^(3/2)).

Answer 2

@Ephraim - I've replaced the recursive code with "while" loop. It's running more faster.

int nextPrime(int M) { while(!isPrime(++M)) // no need ++M; as I already added in the isPrime method's parameter. return M; } boolean isPrime(int M) { for(int i = 2; i <= M; i++) if(M % i == 0) return false; return true; }

@Scott Parent- I've tested the the recursive code; "while" loop and steam code (IntStream and LongStream) - the Stream's code is running slowly, very slowly. Example:
Input value: 60000000000
Output: 60000000029
Elapsed time for recursive algorithm = 7 milliseconds
Output: 60000000029
Elapsed time for traversal algorithm = 4 milliseconds
Output: 60000000029
Elapsed time for LongStream.range(2, number).noneMatch(...) algorithm = 615825 milliseconds

If I use IntStream - the elapsed time is about 230 milliseconds for the max Integer number. It's too much slowly.
The "while" loop in nextPrime(int n) is running 1-4 milliseconds for the max integer number, but usage of LongStream for 600000000000 input value - the result I couldnt see in 1 hour.
I'm running now for the 600000000000 long number:
Elapsed time for recursive algorithm = 36 milliseconds
Output: 60000000029
Elapsed time for traversal algorithm = 27 milliseconds
Output: 60000000029
Elapsed time for LongStream.range(2, number).noneMatch(...)
it's still running more than 58 minutes, but it's not finished yet.

Answer 3

long n = 12345;
BigInteger b = new BigInteger(String.valueOf(n)); 
long res = Long.parseLong(b.nextProbablePrime().toString()); 

System.out.println("Next prime no. is "+ res);

Answer 4

Generate all prime numbers up to your limit using sieve of eratosthenes. And then input your number n and search if n> prime[i] , prime[i] is the answer.

Answer 5

You can also do the same using recursions like this:

int nextPrime(int M) {
    if(!isPrime(M)) M = nextPrime(++M);
        return M;
}
boolean isPrime(int M) {
    for(int i = 2; i <= Math.sqrt(M); i++)
        if(M % i == 0) return false;
    return true;
}

Answer 6

Here I add a solution algorithm. First of all, the while loop grabs the next number to be tested within the range of number + 1 to number * 2. Then the number is sent to the isPrime method (which uses Java 8 streams) that iterates the stream to look for numbers that have no other factors.

private static int nextPrime(final int number) {
    int i = number + 1;
    while (!isPrime(i) && i < number * 2)
        i++;
    return i;
}

private static boolean isPrime(final int number) {
    return number > 1 && IntStream.range(2, number).noneMatch(index -> number % index == 0);
}

Answer 7

My son has written his own algorithm - in one method. But it's written on python - you can find it here.

On Java it looks like:

static long nextPrime(long number) {
    boolean prime = false;
    long n = number;
    while (!prime && n < number * 2) {
        n++;
        prime = true;
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                prime = false;
                break;
            }
        }
    }
    return n;
}

Answer 8

Dude check this code. isPrime() in the while loop checks for the next prime number after incrementing the current prime/non-prime number. I did used the long datatype (that's what I got as assignment).

if (isPrime(num)) {
    System.out.println("Current Prime number: " + num);
} else {
    long a = getNextPrime(num);
    System.out.println("Next Prime:" + a);
}

public static long getNextPrime(long num) {
    long nextPrime = 0;
    while (true) {
        num++;
        boolean x = isPrime(num);
        if (x) {
            nextPrime = num;
            break;
        }
    }

    return nextPrime;
}

public static boolean isPrime(long num) {
    if (num == 0 || num == 1) {
        return false;
    }

    for (long i = 2; i <= num / 2; ++i) {
        if (num % i == 0) {
            return false;
        }
    } 

    return true;
}

Answer 9

This is functional way of finding next prime number.

public void printFirstNPrimes(long n) {
        Stream.iterate(2, i->nextPrime(i))
        .limit(n).forEach(System.out::println);
}

public static boolean isPrime(long x) {
    return Stream.iterate(2, i->i+1)
                .limit((long)(Math.sqrt(x)))
                .allMatch(n -> x % n != 0);
}

public static int nextPrime(int x) {
    return isPrime(x+1)? x+1 : nextPrime(x+1);
}

Answer 10

So, I was reading the first answer and saw some potential upgrades. I made them and got a really significant improvement.

The original code could calculate 200000 prime numbers in 22.32s With a little changes I managed to execute the same operation in 11.41s, with the same results.

Notice I executed the code on my laptop @2.50 GHz, running on IntelIJ.

public static int nextPrime(int n) {

    boolean isPrime;
    n++;
    while (true) {
        int sqrt = (int) Math.sqrt(n);
        isprime = true;
        for (int i = 2; i <= sqrt; i++) {
            if (n % i == 0) isPrime = false;
        }
        if (isPrime)
            return n;
        else {
            n++;
        }
    }


}

Hope you like it!

Answer 11

public class ClosestPrimeNumber {

    static boolean isPrime(int n) {
        for (int x = 2; x <= Math.sqrt(n); x++) {
            if (n % x ==0) {
                return false;
            }
        }
        return true;
    }
    static int next_forward = 0;
    static int next_backward = 0;
    static int next = 0;

    static int closestPrimeNumberForward(int n) {
        if (isPrime(n)) {
            next_forward = n;
            return next_forward;
        }else {
            next_forward = n+1;
            closestPrimeNumberForward(next_forward);
        }
        return next_forward;
    }

    static int closestPrimeNumberBackward(int n) {
        if (isPrime(n)) {
            next_backward = n;
            return next_backward;
        }else {
            next_backward = n-1;
            closestPrimeNumberBackward(next_backward);
        }
        return next_backward;
    }

    static int closestCompare(int forward, int backward, int num) {
        return (Math.abs(num-backward) > Math.abs(num-forward) ) ? forward : backward; 
    }

    public static void main(String[] args) {
        int valor = 102;
        System.out.println(closestCompare(closestPrimeNumberForward(valor), closestPrimeNumberBackward(valor), valor));
    }

}

Answer 12

public int nextPrime(int input){
  int counter;
  while(true){
    counter = 0;
    for(int i = 1; i <= input; i ++){
      if(input % i == 0)  counter++;
    }
    if(counter == 2)
      return input;
    else{
      input++;
      continue;
    }
  }
}

This will return the nextPrime but cannot say is most optimal way

• It is simple as it execute an infinite while loop which break when prime number is returned.
• In while is finds whether the number is prime or not
• If it is prime it returns that number, if not it increment input and continue the while loop