Prime Number Logic
Solve one Java logic problem at a time, then flip for the complete explanation and program.
0/150
Known
filtered set
Solve one Java logic problem at a time, then flip for the complete explanation and program.
Java Logic Development · Chapter 04 Companion Article
Fourteen prime-number techniques — checking, ranges, factorization, twin and co-prime pairs, the 6k ± 1 optimization, and the Sieve of Eratosthenes — plus seven interview-style extension problems, all built on the same square-root divisibility idea.
Prime number problems are common in Java interviews because they test loops, divisibility, mathematical optimization, arrays, preprocessing, and problem-solving ability.
A prime number has exactly two positive divisors: 1 and the number itself. Examples: 2, 3, 5, 7, 11, 13 are prime; 4, 6, 8, 9, 10 are composite; 0 and 1 are neither prime nor composite.
A basic prime check tests divisors, while advanced problems reduce unnecessary checks or preprocess many values using the Sieve of Eratosthenes.
A number greater than 1 is prime when it is divisible only by 1 and itself. Examples: 2 → Prime, 7 → Prime, 9 → Not prime because 9 = 3 × 3, 1 → Not prime.
For a number n: reject values less than 2, check divisibility from 2 to n - 1, and if any number divides n exactly it is not prime, otherwise it is prime. The condition n % i == 0 means i is a divisor of n.
public class PrimeNumberCheck {
public static void main(String[] args) {
int number = 29;
boolean isPrime = true;
if (number < 2) {
isPrime = false;
} else {
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");
}
}
}29 is a prime numberFor number = 29:
29 % 2 != 029 % 3 != 0O(n)O(1)Starting with boolean isPrime = true; and forgetting to handle 0, 1, and negative numbers causes incorrect results.
A composite number is a positive integer greater than 1 that has more than two positive divisors. Examples: 4 → divisors are 1, 2, 4; 6 → divisors are 1, 2, 3, 6; 15 → divisors are 1, 3, 5, 15. Prime and composite are opposite classifications only for numbers greater than 1. 1 is neither prime nor composite.
A number is composite when it is greater than 1 and at least one divisor exists between 2 and n - 1.
public class CompositeNumberCheck {
public static void main(String[] args) {
int number = 21;
boolean isComposite = false;
if (number > 1) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
isComposite = true;
break;
}
}
}
if (isComposite) {
System.out.println(number + " is a composite number");
} else if (number > 1) {
System.out.println(number + " is not a composite number");
} else {
System.out.println(number + " is neither prime nor composite");
}
}
}21 is a composite number21 % 3 == 0, so 3 is a divisor other than 1 and 21. That is enough to prove that 21 is composite. There is no need to continue checking remaining divisors.
O(n)O(1)Use break immediately after finding a divisor. Continuing the loop does unnecessary work when the requirement is only to determine whether the number is composite.
This problem finds every prime number between two boundaries. Example: input range 10 to 30 → prime numbers 11, 13, 17, 19, 23, 29.
Use two levels of logic: traverse every number in the range, then check whether the current number is prime. Keeping prime-checking logic in a separate method makes the program easier to reuse.
public class PrimeNumbersInRange {
public static boolean isPrime(int number) {
if (number < 2) {
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 start = 10;
int end = 30;
for (int number = start; number <= end; number++) {
if (isPrime(number)) {
System.out.print(number + " ");
}
}
}
}11 13 17 19 23 29If a number has two factors, a × b = n, at least one factor must be less than or equal to √n. For example, 36 = 6 × 6. If no divisor exists up to √n, a larger divisor cannot exist without having a corresponding smaller divisor.
For a range containing roughly R numbers:
O(R√n)O(1)where n represents the largest number being tested.
If the program needs all primes over a large continuous range, checking each number independently becomes expensive. A sieve is usually a better choice.
Instead of printing primes, this variation counts how many primes exist between two values. Example: range 1 to 20, prime numbers 2, 3, 5, 7, 11, 13, 17, 19, count 8.
public class CountPrimeNumbers {
public static boolean isPrime(int number) {
if (number < 2) {
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 start = 1;
int end = 20;
int count = 0;
for (int number = start; number <= end; number++) {
if (isPrime(number)) {
count++;
}
}
System.out.println("Prime count = " + count);
}
}Prime count = 8count increases only when the current value passes the prime test.
O(R√n)O(1)Instead of counting within one range, multiple range queries may be given. Running prime checks repeatedly is inefficient for many queries. A sieve combined with a prefix-count array can answer each query much faster.
This problem adds all prime numbers within a given range. Example: prime numbers from 1 to 10, 2 + 3 + 5 + 7 = 17.
public class SumOfPrimeNumbers {
public static boolean isPrime(int number) {
if (number < 2) {
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 start = 1;
int end = 20;
int sum = 0;
for (int number = start; number <= end; number++) {
if (isPrime(number)) {
sum += number;
}
}
System.out.println("Sum of primes = " + sum);
}
}Sum of primes = 77Primes from 1 to 20: 2, 3, 5, 7, 11, 13, 17, 19. Sum: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = 77.
O(R√n)O(1)For large ranges, use long for the sum because adding many prime numbers may exceed the int limit. Example: long sum = 0;
Here the input represents how many prime numbers are required rather than an upper boundary. Example: for n = 10, result 2 3 5 7 11 13 17 19 23 29.
Maintain two values: number as the current candidate, and count as the number of primes already found. Continue until count == n.
public class FirstNPrimeNumbers {
public static boolean isPrime(int number) {
if (number < 2) {
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 n = 10;
int count = 0;
int number = 2;
while (count < n) {
if (isPrime(number)) {
System.out.print(number + " ");
count++;
}
number++;
}
}
}2 3 5 7 11 13 17 19 23 29The final number that must be checked is unknown. The loop stops according to the number of primes found rather than according to a fixed numeric boundary.
If n <= 0, there are no prime numbers to generate.
After processing 2, even candidates can be skipped because no other even number is prime.
The next prime of a number is the first prime strictly greater than that number. Example: input 14, next prime 17. Even if the input itself is prime, the search begins from the next integer — input 13, next prime 17.
public class NextPrimeNumber {
public static boolean isPrime(int number) {
if (number < 2) {
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 = 14;
int candidate = number + 1;
while (!isPrime(candidate)) {
candidate++;
}
System.out.println("Next prime = " + candidate);
}
}Next prime = 17Start: candidate = 15
Search stops at 17.
The exact number of candidates checked depends on the distance to the next prime. Each candidate requires approximately O(√n) prime-checking work.
Starting from candidate = number would return the same number when the input itself is already prime. Use number + 1 when the requirement says strictly next prime.
The previous prime is the largest prime strictly smaller than the supplied number. Example: input 20, result 19.
public class PreviousPrimeNumber {
public static boolean isPrime(int number) {
if (number < 2) {
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 = 20;
int candidate = number - 1;
while (candidate >= 2 && !isPrime(candidate)) {
candidate--;
}
if (candidate >= 2) {
System.out.println("Previous prime = " + candidate);
} else {
System.out.println("No previous prime exists");
}
}
}Previous prime = 19For input values 2 or smaller, there may be no valid previous positive prime. The condition candidate >= 2 prevents the search from continuing indefinitely toward negative numbers.
Boundary conditions matter more in previous-prime logic than next-prime logic because prime numbers have a lower boundary at 2.
Prime factorization expresses a number as a product of prime numbers. Example: 84 can be written as 2 × 2 × 3 × 7. Therefore, its prime factors including repetition are 2 2 3 7.
Start with the smallest possible divisor. While the current divisor divides the number: print the divisor, divide the number by that divisor, and test the same divisor again. Move to the next divisor only when the current divisor no longer divides the remaining number.
public class PrimeFactors {
public static void main(String[] args) {
int number = 84;
int remaining = number;
for (int factor = 2; factor * factor <= remaining; factor++) {
while (remaining % factor == 0) {
System.out.print(factor + " ");
remaining /= factor;
}
}
if (remaining > 1) {
System.out.print(remaining);
}
}
}2 2 3 7remaining = 84
84 / 2 = 42 (divide by 2)
42 / 2 = 21 (divide by 2 again)
21 not divisible by 2, try 3
21 / 3 = 7 (7 is prime, print it)
Final factors: 2 2 3 7After removing all smaller factors, a remaining value greater than 1 must itself be prime. This prevents unnecessary looping up to the original number.
O(√n)O(1)Distinct prime factors contain each prime divisor only once. Example: 360, prime factorization 360 = 2 × 2 × 2 × 3 × 3 × 5, distinct prime factors 2, 3, 5.
When a factor is found: print it once, remove every occurrence of that factor, and continue searching.
public class DistinctPrimeFactors {
public static void main(String[] args) {
int number = 360;
int remaining = number;
for (int factor = 2; factor * factor <= remaining; factor++) {
if (remaining % factor == 0) {
System.out.print(factor + " ");
while (remaining % factor == 0) {
remaining /= factor;
}
}
}
if (remaining > 1) {
System.out.print(remaining);
}
}
}2 3 5Normal prime factors of 360: 2 2 2 3 3 5. Distinct prime factors: 2 3 5. The inner while loop removes repeated occurrences before moving forward.
O(√n)O(1)A common follow-up is: "Count the number of distinct prime factors." Instead of printing the factor, increment a counter once when each new factor is found.
Twin primes are two prime numbers whose difference is exactly 2. Examples: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31).
For each prime p, check whether p + 2 is also prime.
public class TwinPrimeNumbers {
public static boolean isPrime(int number) {
if (number < 2) {
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 start = 1;
int end = 50;
for (int number = start; number + 2 <= end; number++) {
if (isPrime(number) && isPrime(number + 2)) {
System.out.println("(" + number + ", " + (number + 2) + ")");
}
}
}
}(3, 5)
(5, 7)
(11, 13)
(17, 19)
(29, 31)
(41, 43)Both members of the twin-prime pair must remain inside the requested range. Without this condition, the second number could fall outside the upper boundary.
O(R√n)O(1)Do not confuse twin primes with consecutive prime numbers. 7 and 11 are consecutive primes, but they are not twin primes because their difference is 4.
Two numbers are co-prime when their greatest common divisor is 1. The numbers themselves do not need to be prime. Examples: 8 and 15 are co-prime because GCD(8, 15) = 1, even though both numbers are composite. Another example: 14 and 25 have no common prime factor, so they are co-prime.
Instead of listing factors of both numbers, calculate their GCD using Euclid's algorithm. If GCD(a, b) == 1, the numbers are co-prime.
public class CoPrimeNumbers {
public static int gcd(int a, int b) {
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return Math.abs(a);
}
public static void main(String[] args) {
int first = 14;
int second = 25;
if (gcd(first, second) == 1) {
System.out.println(first + " and " + second + " are co-prime");
} else {
System.out.println(first + " and " + second + " are not co-prime");
}
}
}14 and 25 are co-primeFor 14 and 25:
14 % 25 = 1425 % 14 = 1114 % 11 = 311 % 3 = 23 % 2 = 12 % 1 = 0GCD is 1. Therefore, the numbers are co-prime.
Euclid's algorithm:
O(log(min(a, b)))O(1)Co-prime does not mean both numbers are prime. For example, 8 and 9 are both composite, but GCD(8, 9) = 1, so they are co-prime.
The basic prime check may test too many divisors. Three useful optimizations are: stop at the square root, handle even numbers separately, and test divisors of the form 6k ± 1.
Every integer can be represented as one of 6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5. Numbers represented by 6k, 6k + 2, 6k + 4 are even. 6k + 3 is divisible by 3. Therefore, primes greater than 3 must occur in the forms 6k - 1 or 6k + 1.
This does not mean every 6k ± 1 number is prime. It only reduces the number of candidates that need testing. For example, 25 = 6 × 4 + 1 but 25 is composite.
public class OptimizedPrimeCheck {
public static boolean isPrime(int number) {
if (number <= 1) {
return false;
}
if (number <= 3) {
return true;
}
if (number % 2 == 0 || number % 3 == 0) {
return false;
}
for (int i = 5; i <= number / i; i += 6) {
if (number % i == 0 || number % (i + 2) == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int number = 97;
System.out.println(number + (isPrime(number) ? " is prime" : " is not prime"));
}
}97 is primeA common condition is i * i <= number. For very large int values, i * i can theoretically overflow. Using i <= number / i avoids multiplication overflow while representing the same square-root boundary for positive values.
O(√n)O(1)This approach is suitable when one number must be checked, only a few prime checks are required, and building a sieve would be unnecessary overhead.
The Sieve of Eratosthenes efficiently finds all prime numbers up to a given limit. It is especially useful when many prime-related queries must be answered within the same numeric range.
Assume all numbers from 2 onward are prime initially. Then repeatedly mark multiples of each discovered prime as composite. For example, for numbers up to 20: start with 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20. Using 2, remove 4, 6, 8, 10, 12, 14, 16, 18, 20. Using 3, remove 6, 9, 12, 15, 18. Remaining prime values are 2, 3, 5, 7, 11, 13, 17, 19.
import java.util.Arrays;
public class SieveOfEratosthenes {
public static void main(String[] args) {
int limit = 50;
boolean[] isPrime = new boolean[limit + 1];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
for (int prime = 2; prime <= limit / prime; prime++) {
if (isPrime[prime]) {
for (int multiple = prime * prime; multiple <= limit; multiple += prime) {
isPrime[multiple] = false;
}
}
}
for (int number = 2; number <= limit; number++) {
if (isPrime[number]) {
System.out.print(number + " ");
}
}
}
}2 3 5 7 11 13 17 19 23 29 31 37 41 43 47For prime 5, numbers such as 10, 15, and 20 were already marked while processing 2 or 3. The first new composite that needs attention is 5 × 5 = 25. Starting from prime * prime avoids repeated work.
If a composite number has not already been marked by the time all primes up to √limit are processed, it cannot have a smaller undiscovered factor.
O(n log log n)O(n)Use a sieve when all primes up to n are required, many numbers need prime checks, multiple queries use the same upper limit, or prime counts/sums need repeated queries. Do not automatically use it for checking one small number because it requires an array proportional to the upper limit.
Prime-number interview questions often extend the basic prime check into counting, searching, factorization, or preprocessing problems. The key is to identify whether the problem involves one number, several independent numbers, a continuous range, many repeated queries, prime factors, or relationships between primes.
Example: n = 6, prime sequence 2, 3, 5, 7, 11, 13, answer 13.
public class NthPrimeNumber {
public static boolean isPrime(int number) {
if (number < 2) {
return false;
}
for (int i = 2; i <= number / i; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int n = 6;
int count = 0;
int number = 1;
while (count < n) {
number++;
if (isPrime(number)) {
count++;
}
}
System.out.println(n + "th prime = " + number);
}
}6th prime = 13The stopping condition depends on how many primes have been found, not on a fixed upper limit.
Example: 12 + 17 = 29. Since 29 is prime, the answer is true.
public class PrimeSumCheck {
public static boolean isPrime(int number) {
if (number < 2) {
return false;
}
for (int i = 2; i <= number / i; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int first = 12;
int second = 17;
int sum = first + second;
System.out.println("Sum = " + sum);
System.out.println("Prime = " + isPrime(sum));
}
}Sum = 29
Prime = trueDo not duplicate prime-checking logic inside the addition logic. Calculate the derived value first and pass it to a reusable method.
Example: input 30, answer 29.
public class LargestPrimeBelowN {
public static boolean isPrime(int number) {
if (number < 2) {
return false;
}
for (int i = 2; i <= number / i; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int n = 30;
int number = n - 1;
while (number >= 2 && !isPrime(number)) {
number--;
}
if (number >= 2) {
System.out.println("Largest prime below " + n + " = " + number);
} else {
System.out.println("No prime exists below " + n);
}
}
}Largest prime below 30 = 29For 72, prime factorization is 2 × 2 × 2 × 3 × 3, number of prime factors 5.
public class CountPrimeFactors {
public static void main(String[] args) {
int number = 72;
int remaining = number;
int count = 0;
for (int factor = 2; factor <= remaining / factor; factor++) {
while (remaining % factor == 0) {
count++;
remaining /= factor;
}
}
if (remaining > 1) {
count++;
}
System.out.println("Prime factor count = " + count);
}
}Prime factor count = 5Make sure the requirement is clear: count all prime factors including repetition, or count only distinct prime factors. These are different problems. For 72: repeated factor count = 5, distinct factor count = 2.
Example: 12 = 2² × 3, distinct prime factors 2 and 3. Therefore, 12 has exactly two distinct prime factors.
public class TwoDistinctPrimeFactors {
public static void main(String[] args) {
int number = 12;
int remaining = number;
int count = 0;
for (int factor = 2; factor <= remaining / factor; factor++) {
if (remaining % factor == 0) {
count++;
while (remaining % factor == 0) {
remaining /= factor;
}
}
}
if (remaining > 1) {
count++;
}
System.out.println("Exactly two distinct prime factors = " + (count == 2));
}
}Exactly two distinct prime factors = trueThe input does not always come as a continuous range. Example array {4, 7, 10, 13, 18, 23}, prime elements 7, 13, 23.
public class PrimeNumbersFromArray {
public static boolean isPrime(int number) {
if (number < 2) {
return false;
}
for (int i = 2; i <= number / i; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int[] numbers = {4, 7, 10, 13, 18, 23};
for (int number : numbers) {
if (isPrime(number)) {
System.out.print(number + " ");
}
}
}
}7 13 23A sieve works naturally for continuous numeric limits, while individual prime checks may be simpler when only a small unrelated set of values is provided.
Suppose primes are 2, 3, 5, 7, 11. Differences are 3 - 2 = 1, 5 - 3 = 2, 7 - 5 = 2, 11 - 7 = 4. This concept appears in problems involving prime gaps.
public class PrimeGaps {
public static boolean isPrime(int number) {
if (number < 2) {
return false;
}
for (int i = 2; i <= number / i; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int limit = 20;
int previousPrime = -1;
for (int number = 2; number <= limit; number++) {
if (isPrime(number)) {
if (previousPrime != -1) {
System.out.println(previousPrime + " -> " + number + " : gap = " + (number - previousPrime));
}
previousPrime = number;
}
}
}
}2 -> 3 : gap = 1
3 -> 5 : gap = 2
5 -> 7 : gap = 2
7 -> 11 : gap = 4
11 -> 13 : gap = 2
13 -> 17 : gap = 4
17 -> 19 : gap = 2| Approach | Time Complexity | Space | Suitable For |
|---|---|---|---|
| Check 2 to n - 1 | O(n) | O(1) | Learning basic logic |
| Check 2 to n / 2 | O(n) | O(1) | Slight improvement, still unnecessary |
| Check up to √n | O(√n) | O(1) | Standard individual prime check |
| Skip even divisors | O(√n) | O(1) | Faster individual checks |
| 6k ± 1 check | O(√n) | O(1) | Optimized individual checks |
| Sieve of Eratosthenes | O(n log log n) | O(n) | Finding many primes up to n |
A common beginner implementation uses for (int i = 2; i <= number / 2; i++). This works, but it performs unnecessary checks. For number = 1000000, number / 2 = 500000, while √1000000 = 1000. Checking only up to the square root can reduce hundreds of thousands of unnecessary iterations.
Suppose n = a × b. If both a and b were greater than √n, then a × b > n, which is impossible. Therefore, every composite number must have at least one factor less than or equal to its square root. This mathematical property is the reason the optimized prime check can stop early.
0 is not prime. It has infinitely many integer divisors and does not satisfy the definition of a prime number.
1 is not prime. It has only one positive divisor.
2 is prime. It is the smallest prime and the only even prime number.
Negative integers are not considered prime under the standard definition used in Java programming problems.
For large values: avoid checking every divisor up to n, use square-root-based checking, avoid arithmetic overflow in loop conditions, and consider long when values can exceed the int range.
This condition is common: i * i <= number. For normal small inputs, it works correctly. For large integer values, the multiplication may overflow before comparison. An overflow-safe alternative is i <= number / i. Example:
for (int i = 2; i <= number / i; i++) {
if (number % i == 0) {
return false;
}
}This is useful when writing defensive integer logic.
A clean solution usually keeps prime logic separate from the main problem.
public static boolean isPrime(int number) {
if (number <= 1) {
return false;
}
if (number <= 3) {
return true;
}
if (number % 2 == 0 || number % 3 == 0) {
return false;
}
for (int i = 5; i <= number / i; i += 6) {
if (number % i == 0 || number % (i + 2) == 0) {
return false;
}
}
return true;
}This method can be reused for:
Separating the method avoids rewriting the same divisibility logic throughout a program.
Incorrect: if (number >= 1). Prime numbers begin from 2. Correct boundary: if (number < 2) { return false; }
Using for (int i = 2; i < number; i++) is logically correct but inefficient. Prefer a square-root boundary.
Once a divisor is found, the number is known to be composite. Continuing the loop wastes work.
This still produces correct prime results, but many multiples were already processed by smaller primes. Use prime * prime as the starting point.
When a boolean sieve array is initialized to true, explicitly set isPrime[0] = false; and isPrime[1] = false; when the array size permits those indexes.
Factors of 12: 1, 2, 3, 4, 6, 12. Prime factors of 12: 2, 2, 3. Distinct prime factors: 2, 3. These represent different requirements.
8 and 15 are co-prime even though neither number is prime. Co-prime status depends on their common divisor: GCD(8, 15) = 1.
Use an optimized isPrime() method when checking one number or a relatively small number of independent values. Use the Sieve of Eratosthenes when all primes up to a known upper limit are needed. Use prime factorization when the problem asks about prime divisors, distinct prime divisors, number of prime factors, or factor-based properties. Use Euclid's GCD algorithm for co-prime checks rather than manually generating prime factors.
This distinction is important because the best solution depends on what information the problem actually asks for.
| Concept | Key Rule |
|---|---|
| Prime number | Exactly two positive divisors |
| Composite number | More than two positive divisors |
| 0 | Neither prime nor composite |
| 1 | Neither prime nor composite |
| Smallest prime | 2 |
| Only even prime | 2 |
| Basic prime check | Test possible divisors |
| Optimized boundary | Check only up to √n |
| 6k ± 1 | Reduces candidate divisors |
| Prime factors | Prime divisors including repetition |
| Distinct prime factors | Each prime divisor once |
| Twin primes | Prime pair differing by 2 |
| Co-prime numbers | GCD equals 1 |
| Sieve | Generates many primes efficiently |
| Trial division space | O(1) |
| Sieve space | O(n) |
| Sieve time | O(n log log n) |
After completing these prime-number problems, a Java learner should be able to: