Prime Number
Java coding interview problem for Basic Number Programs: Prime Number.
Checking whether a number is Prime is one of the most frequently asked Java coding interview questions. It evaluates your understanding of loops, conditional statements, mathematical logic, and optimization techniques.
What is a Prime Number?
A Prime Number is a positive integer greater than 1 that has exactly two factors:
- 1
- The number itself
Examples:
2, 3, 5, 7, 11, 13, 17, 19...
Examples of non-prime numbers:
1, 4, 6, 8, 9, 10, 12...
Prime vs Non-Prime
| Number | Factors | Prime? |
|---|---|---|
| 2 | 1,2 | ✅ Yes |
| 3 | 1,3 | ✅ Yes |
| 4 | 1,2,4 | ❌ No |
| 5 | 1,5 | ✅ Yes |
| 6 | 1,2,3,6 | ❌ No |
| 7 | 1,7 | ✅ Yes |
| 9 | 1,3,9 | ❌ No |
Real Interview Question
Write a Java program to determine whether a given number is a Prime Number.
Example 1
Input
17
Output
17 is a Prime Number
Example 2
Input
20
Output
20 is NOT a Prime Number
Understanding the Logic
A number is prime if no number between 2 and n−1 divides it completely.
Example:
13
Try dividing by
2
3
4
5
6
7
8
9
10
11
12
None divides 13 evenly.
Therefore,
13 is Prime
Brute Force Approach
The simplest solution is:
- Start from 2
- Check every number up to n−1
- If any number divides evenly
- It is NOT prime
- Otherwise it is prime
Algorithm
Step 1
Read the input number.
Step 2
If number ≤ 1
Return
Not Prime
Step 3
Loop
2 to n-1
Step 4
If
number % i == 0
Return
Not Prime
Step 5
If loop completes
Return
Prime
Dry Run
Input
11
| Iteration | Divisor | Remainder | Prime? |
|---|---|---|---|
| 1 | 2 | 1 | Continue |
| 2 | 3 | 2 | Continue |
| 3 | 4 | 3 | Continue |
| 4 | 5 | 1 | Continue |
| 5 | 6 | 5 | Continue |
| 6 | 7 | 4 | Continue |
| 7 | 8 | 3 | Continue |
| 8 | 9 | 2 | Continue |
| 9 | 10 | 1 | Continue |
No divisor found.
Output
11 is Prime
Dry Run (Non-Prime)
Input
18
| Iteration | Divisor | Remainder |
|---|---|---|
| 1 | 2 | 0 |
Since
18 % 2 == 0
Stop immediately.
Output
18 is NOT Prime
Approach 1 — Brute Force Solution
Complete Java Program
public class PrimeNumber {
public static void main(String[] args) {
int number = 17;
if (number <= 1) {
System.out.println(number + " is NOT a Prime Number");
return;
}
boolean isPrime = true;
for (int i = 2; i < number; i++) {
if (number % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
System.out.println(number + " is a Prime Number");
} else {
System.out.println(number + " is NOT a Prime Number");
}
}
}
Output
17 is a Prime Number
Step-by-Step Code Explanation
Step 1
Store the input number.
int number = 17;
Step 2
Handle invalid numbers.
Prime numbers must be greater than 1.
if (number <= 1)
Return
Not Prime
Step 3
Assume the number is prime.
boolean isPrime = true;
Step 4
Check every possible divisor.
for (int i = 2; i < number; i++)
Step 5
Check divisibility.
number % i == 0
If remainder is zero,
The number has another factor.
Therefore,
isPrime = false;
Step 6
Break immediately.
break;
There is no need to continue checking.
Step 7
Print the result.
if (isPrime)
Prime Number
Else
Not Prime
Why Does This Work?
A prime number has only two factors.
If we find even one divisor,
Number is NOT Prime
If no divisor exists,
Number is Prime
Drawbacks of This Approach
Suppose
Number = 999983
The loop checks almost
999981
numbers.
This is inefficient for very large numbers.
we'll optimize the solution by checking divisors only up to √n, reducing the time complexity significantly and covering the approach most interviewers expect.
Approach 2 — Optimized Solution (Using √n)
The brute force approach checks every number from 2 to n−1.
For large numbers, this is inefficient.
A better approach is to check divisibility only up to the square root of the number.
Why Check Only Until √n?
Consider
36
Factor pairs are
1 × 36
2 × 18
3 × 12
4 × 9
6 × 6
After reaching
√36 = 6
the remaining factors repeat in reverse.
For example
2 × 18
18 × 2
Checking after √n is unnecessary.
Therefore,
Instead of checking
2 → 35
we only check
2 → 6
This significantly improves performance.
Algorithm
Step 1
Read the input number.
Step 2
If
number <= 1
Return
Not Prime
Step 3
Loop
i = 2
i * i <= number
Step 4
If
number % i == 0
Return
Not Prime
Step 5
Otherwise
Prime
Dry Run
Input
29
Square root
√29 ≈ 5.38
Check only
2
3
4
5
| Divisor | Remainder |
|---|---|
| 2 | 1 |
| 3 | 2 |
| 4 | 1 |
| 5 | 4 |
No divisor found.
Output
29 is Prime
Optimized Java Solution
public class PrimeNumberOptimized {
public static void main(String[] args) {
int number = 29;
if (number <= 1) {
System.out.println(number + " is NOT a Prime Number");
return;
}
boolean isPrime = true;
for (int i = 2; i * i <= number; i++) {
if (number % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
System.out.println(number + " is a Prime Number");
} else {
System.out.println(number + " is NOT a Prime Number");
}
}
}
Output
29 is a Prime Number
Approach 3 — Using a Method
Instead of writing all logic inside the main() method, create a reusable method.
public class PrimeNumberMethod {
static boolean isPrime(int number) {
if (number <= 1) {
return false;
}
for (int i = 2; i * i <= number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int number = 31;
if (isPrime(number)) {
System.out.println(number + " is a Prime Number");
} else {
System.out.println(number + " is NOT a Prime Number");
}
}
}
Time Complexity
Brute Force
| Operation | Complexity |
|---|---|
| Time | O(n) |
| Space | O(1) |
Optimized
| Operation | Complexity |
|---|---|
| Time | O(√n) |
| Space | O(1) |
Comparison
| Approach | Time | Space | Recommended |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Good for learning |
| Square Root Optimization | O(√n) | O(1) | ✅ Best Choice |
| Method-based Solution | O(√n) | O(1) | Reusable |
Common Mistakes
Mistake 1
Treating
1
as a prime number.
Wrong
1 is Prime
Correct
1 is NOT Prime
Mistake 2
Starting loop from
1
Since every number is divisible by 1,
the program always fails.
Correct
for(int i = 2; ...)
Mistake 3
Forgetting
break;
Once a divisor is found,
there is no need to continue checking.
Mistake 4
Checking until
number - 1
instead of
i * i <= number
This makes the program slower.
Mistake 5
Ignoring numbers less than or equal to 1.
Always validate input first.
Interview Follow-up Questions
Q1. Print all Prime Numbers between 1 and N.
Q2. Find the Nth Prime Number.
Q3. Count Prime Numbers in an array.
Q4. Check whether two numbers are Twin Primes.
Q5. Find Prime Factors of a number.
Q6. Generate Prime Numbers using the Sieve of Eratosthenes.
Q7. Count Prime Numbers in a given range.
Q8. Find the nearest Prime Number.
Q9. Determine whether a very large number is prime.
Q10. Compare O(n) and O(√n) approaches.
Related Coding Problems
- Fibonacci Series
- Factorial
- Armstrong Number
- Perfect Number
- Strong Number
- GCD and LCM
- Power of a Number
- Prime Factors
Key Takeaways
- A Prime Number has exactly two factors: 1 and itself.
- Numbers less than or equal to 1 are not prime.
- The brute force approach checks every divisor from 2 to n−1.
- The optimized solution checks divisors only up to √n, reducing the time complexity from O(n) to O(√n).
- The √n approach is the solution most interviewers expect because it balances simplicity and efficiency.
Interview Tip
If an interviewer asks:
"Write a Java program to check whether a number is prime."
Start with the simple brute force approach to demonstrate your understanding. Then explain why it can be optimized and implement the √n solution. Finally, discuss the time complexity improvement from O(n) to O(√n) and mention advanced techniques like the Sieve of Eratosthenes for generating multiple prime numbers. This progression shows both problem-solving ability and optimization skills.