Definition
- Primality predicate checks if no integer from 2 to sqrt(k) divides k evenly.
- noneMatch short-circuits on the first divisor, so composites are rejected quickly.
- Square root bound is the key optimization: a factor larger than the root pairs with one smaller.
- rangeClosed(2, n) generates all candidate numbers as a primitive IntStream.
- Sieve of Eratosthenes is faster for large n but the predicate approach is clearer for moderate ranges.
Priya at the National Bank of India needs a small list of prime numbers to seed a token hashing scheme. She checks each number from 2 up, and for each one she tries dividing by all numbers up to the square root. If none divide evenly, it is prime.
Understanding the Concepts
What does this question ask?
The interviewer wants you to find primes using IntStream and a predicate. This tests noneMatch, the square root optimization, and stream filtering.
How do you implement the primality predicate?
package com.bank.core;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class PrimeNumbers {
public static boolean isPrime(int k) {
if (k < 2) return false;
return IntStream.rangeClosed(2, (int) Math.sqrt(k))
.noneMatch(d -> k % d == 0);
}
public static void main(String[] args) {
int n = 50;
List<Integer> primes = IntStream.rangeClosed(2, n)
.filter(PrimeNumbers::isPrime)
.boxed()
.collect(Collectors.toList());
System.out.println("Primes up to " + n + ": " + primes);
System.out.println("Count: " + primes.size());
}
}
Primes up to 50: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Count: 15
Why check only up to the square root?
If a number k has a factor d greater than sqrt(k), then k/d is a factor less than sqrt(k). So checking up to the square root catches all factor pairs.
// For k = 36, sqrt = 6
// Factors: 2*18, 3*12, 4*9, 6*6
// Every factor > 6 pairs with one < 6
// So checking 2..6 is sufficient
System.out.println(isPrime(36)); // false (divisible by 2)
System.out.println(isPrime(37)); // true (no divisor in 2..6)
How does noneMatch short-circuit?
public static boolean isPrimeVerbose(int k) {
if (k < 2) return false;
return IntStream.rangeClosed(2, (int) Math.sqrt(k))
.peek(d -> System.out.println(" Testing " + k + " % " + d))
.noneMatch(d -> k % d == 0);
}
// isPrimeVerbose(12): tests 12%2 = 0, stops immediately
// isPrimeVerbose(13): tests 13%2, 13%3 -> both non-zero -> prime
Composites are rejected as soon as their first divisor is found.
How is trial division different from a sieve?
| Approach | Time complexity | Best for |
|---|---|---|
| Trial division per number | O(sqrt(k)) per number | Small n, clarity |
| Sieve of Eratosthenes | O(n log log n) total | Large n, performance |
// Sieve approach for large n
public static List<Integer> sieve(int n) {
boolean[] isComposite = new boolean[n + 1];
for (int i = 2; i * i <= n; i++) {
if (!isComposite[i]) {
for (int j = i * i; j <= n; j += i) {
isComposite[j] = true;
}
}
}
return IntStream.rangeClosed(2, n)
.filter(i -> !isComposite[i])
.boxed()
.collect(Collectors.toList());
}
The sieve eliminates multiples in bulk, which is faster for large n.
What about edge cases?
System.out.println(isPrime(0)); // false (< 2)
System.out.println(isPrime(1)); // false (< 2)
System.out.println(isPrime(2)); // true (smallest prime)
System.out.println(isPrime(3)); // true
System.out.println(isPrime(4)); // false (2*2)
System.out.println(isPrime(-7)); // false (negative)
What are common mistakes?
Mistake: checking divisors up to k instead of sqrt(k).
// WRONG: checks all divisors up to k-1, much slower
boolean wrong = IntStream.range(2, k)
.noneMatch(d -> k % d == 0);
// CORRECT: checks only up to sqrt(k)
boolean correct = IntStream.rangeClosed(2, (int) Math.sqrt(k))
.noneMatch(d -> k % d == 0);
Mistake: starting the range at 0 or 1.
// WRONG: 0 and 1 are not prime
List<Integer> wrong = IntStream.rangeClosed(0, n)
.filter(PrimeNumbers::isPrime).boxed().toList();
// CORRECT: start from 2
List<Integer> correct = IntStream.rangeClosed(2, n)
.filter(PrimeNumbers::isPrime).boxed().toList();
What about using parallel streams for prime checking?
List<Integer> parallelPrimes = IntStream.rangeClosed(2, 100_000)
.parallel()
.filter(PrimeNumbers::isPrime)
.boxed()
.collect(Collectors.toList());
The predicate is stateless and thread-safe, so parallelism works correctly here. Each number is tested independently.
What are common interview follow-up questions?
- "How do you find the Nth prime?" Use iterate or generate with a counter and the isPrime predicate.
- "How do you check if a very large number is prime?" Use probabilistic tests like Miller-Rabin.
- "How do you find twin primes?" Filter pairs where both p and p+2 are prime.
Visual Overview
IntStream.rangeClosed(2, 20)
→ [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
│
│ .filter(isPrime)
▼
isPrime(k) {
rangeClosed(2, sqrt(k)).noneMatch(d -> k % d == 0)
}
2 → sqrt=1 → no divisors → prime
3 → sqrt=1 → no divisors → prime
4 → sqrt=2 → 4%2==0 → NOT prime
5 → sqrt=2 → 5%2!=0 → prime
6 → sqrt=2 → 6%2==0 → NOT prime
7 → sqrt=2 → 7%2!=0 → prime
...
Result: [2, 3, 5, 7, 11, 13, 17, 19]
Key Takeaway
Finding primes up to N uses IntStream.rangeClosed(2, n) filtered by a primality predicate. The predicate checks if no integer from 2 to the square root of k divides k evenly, using noneMatch for early termination on the first divisor found.
The square root bound is the single most important efficiency detail: a factor larger than the root necessarily pairs with one smaller, so there is no need to look beyond the root. noneMatch short-circuits, so composite numbers are discarded as soon as their first divisor is found.
At the National Bank of India, Rajesh used a small prime list to seed a token hashing scheme. For moderate n the predicate approach is perfectly clear and fast. For large n, switch to a sieve of Eratosthenes, which eliminates multiples in bulk and runs in O(n log log n).
Remember one sentence: check divisors only up to the square root with noneMatch for early termination, and switch to a sieve for large ranges.
---