Optimal way to find next prime number (Java)

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;
}


input

7 Answers
7

public int nextPrime(int input){
int counter;
input++;
while(true){
counter = 0;
for(int i = 2; i <= sqrt(input); 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)).

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

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

while

while

copy/paste

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.

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;
}


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;
}


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.

number + 1

number * 2

isPrime

streams

stream

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);
}


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.