Find first prime >= n
Medium
Java
Control Flow
22 views
Problem Statement
Task: return the first prime number that is >= n.
Input Format
An integer n.
Output Format
An integer: the first prime number greater than or equal to n.
Example
10
11
Constraints
• n ≥ 1
• Use basic loops and conditions
• Use basic loops and conditions
Concept Explanation
We start checking numbers from n onwards.
The first number that is prime is returned.
A prime number:
• Greater than 1
• Divisible only by 1 and itself
The first number that is prime is returned.
A prime number:
• Greater than 1
• Divisible only by 1 and itself
Step-by-Step Explanation
1.Read integer n.
2.If n < 2, set n = 2.
3.Repeat forever:
• Assume current number is prime.
• Check divisibility from 2 to sqrt(n).
• If divisible by any number:
• Not prime → increase n by 1.
• If not divisible by any number:
• This is the first prime ≥ original n.
• Return n.
2.If n < 2, set n = 2.
3.Repeat forever:
• Assume current number is prime.
• Check divisibility from 2 to sqrt(n).
• If divisible by any number:
• Not prime → increase n by 1.
• If not divisible by any number:
• This is the first prime ≥ original n.
• Return n.
Concept Explanation
We start checking numbers from n onwards.
The first number that is prime is returned.
A prime number:
• Greater than 1
• Divisible only by 1 and itself
The first number that is prime is returned.
A prime number:
• Greater than 1
• Divisible only by 1 and itself
Step-by-Step Explanation
1.Read integer n.
2.If n < 2, set n = 2.
3.Repeat forever:
• Assume current number is prime.
• Check divisibility from 2 to sqrt(n).
• If divisible by any number:
• Not prime → increase n by 1.
• If not divisible by any number:
• This is the first prime ≥ original n.
• Return n.
2.If n < 2, set n = 2.
3.Repeat forever:
• Assume current number is prime.
• Check divisibility from 2 to sqrt(n).
• If divisible by any number:
• Not prime → increase n by 1.
• If not divisible by any number:
• This is the first prime ≥ original n.
• Return n.
Input / Output Format
Input Format
An integer n.
Output Format
An integer: the first prime number greater than or equal to n.
Constraints
• n ≥ 1
• Use basic loops and conditions
• Use basic loops and conditions
Examples
Input:
10
Output:
11
Example Solution (Public)
static int nextPrime(int n){int x=n<2?2:n;while(true){if(isPrime(x)) return x;x++;}}static boolean isPrime(int x){if(x<2) return false; if(x%2==0) return x==2; for(int i=3;i*i<=x;i+=2) if(x%i==0) return false; return true;}
Official Solution Code
static int nextPrime(int n){int x=n<2?2:n;while(true){if(isPrime(x)) return x;x++;}}static boolean isPrime(int x){if(x<2) return false; if(x%2==0) return x==2; for(int i=3;i*i<=x;i+=2) if(x%i==0) return false; return true;}
Please login to submit solutions.