A prime number is an integer greater than 1 whose only divisors are 1 and the number itself, and the fastest simple way to find all prime numbers from 2 to N in Java is the Sieve of Eratosthenes, which crosses out the multiples of every prime in a boolean array. For a single number, we use trial division up to its square root instead.
We need prime numbers in coding exercises and interviews, in hashing schemes that use a prime number of buckets, and in cryptography, where RSA keys are built from two very large primes.
The following example finds all primes up to 30 with a sieve method.
static List<Integer> primesUpTo(int n) {
if (n < 2) {
return List.of();
}
boolean[] composite = new boolean[n + 1];
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (!composite[i]) {
primes.add(i);
for (long multiple = (long) i * i; multiple <= n; multiple += i) {
composite[(int) multiple] = true;
}
}
}
return primes;
}List<Integer> primes = primesUpTo(30); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
List<Integer> none = primesUpTo(1); // []We can see that the method never divides a number, it only marks multiples. We start with the trial division check for one number, use it to list the primes from 2 to N, explain the sieve step by step, find the first N primes, and test very large numbers with BigInteger.
1. Checking One Number With Trial Division
Trial division tries every possible divisor and stops at the first one that divides the number. We only need to try divisors up to the square root of n, because if n = a * b and both factors were larger than the square root, their product would be larger than n. For 97, the square root is about 9.8, so we try the divisors from 2 to 9 instead of every number up to 96.
The number 2 is the only even prime, so after one check for even numbers, the loop can skip all other even divisors.
static boolean isPrime(int n) {
if (n < 2) {
return false; // 0, 1 and negative numbers
}
if (n % 2 == 0) {
return n == 2;
}
for (int d = 3; d <= n / d; d += 2) {
if (n % d == 0) {
return false;
}
}
return true;
}boolean two = isPrime(2); // true
boolean one = isPrime(1); // false
boolean ninetySeven = isPrime(97); // true
boolean ninetyOne = isPrime(91); // false, 7 * 13
boolean maxInt = isPrime(Integer.MAX_VALUE); // trueThe condition d <= n / d means the same as d * d <= n, but it cannot overflow. With d * d, a value of d above 46,340 makes the product larger than Integer.MAX_VALUE, and the loop condition gives a wrong answer near the top of the int range.
1.1. Skipping Multiples of 2 and 3 With 6k +/- 1
Every prime greater than 3 has the form 6k – 1 or 6k + 1, because the other four numbers in each group of six are divisible by 2 or 3. After checking 2 and 3, the loop tests only the pairs 5 and 7, 11 and 13, 17 and 19, and so on, which is two thirds of the divisors that the odd-only loop tests.
static boolean isPrime6k(long n) {
if (n < 4) {
return n >= 2; // 2 and 3
}
if (n % 2 == 0 || n % 3 == 0) {
return false;
}
for (long d = 5; d <= n / d; d += 6) {
if (n % d == 0 || n % (d + 2) == 0) {
return false;
}
}
return true;
}boolean billionAndSeven = isPrime6k(1_000_000_007L); // true
boolean composite = isPrime6k(600_851_475_143L); // falseTrial division stays practical for long values up to about 1012, where the loop needs a few hundred thousand steps. For larger numbers, we use BigInteger as shown in section 5.
2. Finding All Prime Numbers From 2 to N With a Stream
The direct way to list the primes from 2 to N is to test each number with isPrime(). An IntStream generates the range, and filter() keeps the primes.
List<Integer> upTo50 = IntStream.rangeClosed(2, 50)
.filter(n -> isPrime(n))
.boxed()
.toList();
String result = upTo50.toString(); // "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]"Each number is tested on its own, so the total work grows a little faster than N times the square root of N. That is fine for N up to a few hundred thousand. For larger ranges, the sieve does far less work, because it never repeats the same divisions for different numbers.
When N comes from the user, we validate it before we start. A negative or huge value either returns an empty list or runs out of memory, so a console program reads N with Scanner.hasNextInt() and checks the range first.
3. Sieve of Eratosthenes in Java
The Sieve of Eratosthenes starts with all numbers from 2 to N marked as candidates. It takes the smallest number that is still unmarked, which must be a prime, and marks all of its multiples as composite. It repeats that step with the next unmarked number until the end of the range.
Two details make the method in the intro fast. The inner loop starts at i * i, because smaller multiples of i have a smaller prime factor and were marked already. For the same reason, no prime above the square root of N marks anything new, so the method only adds those primes to the list.
int below1000 = primesUpTo(1000).size(); // 168
int belowMillion = primesUpTo(1_000_000).size(); // 78498
int largest = primesUpTo(1_000_000).getLast(); // 999983The sieve runs in O(N log log N) time, which grows almost linearly with N, but it needs memory for every number up to N. A boolean[] takes one byte per element in HotSpot, so N = 100 million needs about 100 MB. A BitSet stores one bit per number and cuts that to about 12.5 MB.
static BitSet sieve(int n) {
BitSet primes = new BitSet(n + 1);
primes.set(2, n + 1); // every number is a candidate
for (int i = 2; (long) i * i <= n; i = primes.nextSetBit(i + 1)) {
for (int multiple = i * i; multiple <= n && multiple > 0; multiple += i) {
primes.clear(multiple);
}
}
return primes;
}int count = sieve(1_000_000).cardinality(); // 78498
String small = sieve(30).toString(); // "{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}"The check multiple > 0 stops the loop if multiple += i overflows past Integer.MAX_VALUE for a very large N.
4. Finding the First N Prime Numbers
A different task asks for a fixed number of primes, for example, the first 10, instead of all primes below a limit. A stream handles that with an open range and limit(), which stops the stream after the requested number of matches.
List<Integer> firstTen = IntStream.iterate(2, i -> i + 1)
.filter(i -> isPrime(i))
.limit(10)
.boxed()
.toList();
String ten = firstTen.toString(); // "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]"A sieve needs an upper limit before it starts, so we estimate how large the Nth prime can be. For N of 6 or more, the Nth prime is smaller than N (ln N + ln ln N), a bound proven by J. Barkley Rosser, so a sieve up to that limit always contains enough primes.
static List<Integer> firstPrimes(int count) {
if (count < 6) {
return primesUpTo(11).subList(0, count);
}
double ln = Math.log(count);
int limit = (int) (count * (ln + Math.log(ln))) + 1;
return primesUpTo(limit).subList(0, count);
}List<Integer> firstFive = firstPrimes(5); // [2, 3, 5, 7, 11]
int thousandth = firstPrimes(1000).getLast(); // 7919
int tenThousandth = firstPrimes(10_000).getLast(); // 104729For the 10,000th prime, the limit is about 114,307, so the sieve marks a little more than 114,000 numbers once. The stream version runs isPrime() on all 104,729 candidates, each with its own loop of divisions.
5. Testing Large Numbers With BigInteger
Numbers beyond the long range need a different test, because trial division would take longer than anyone can wait. The method BigInteger.isProbablePrime(certainty) runs a probabilistic test. It returns false only for numbers that are certainly composite, and when it returns true, the chance that the number is not prime is below 1 in 2certainty.
BigInteger mersenne = BigInteger.TWO.pow(61).subtract(BigInteger.ONE); // 2305843009213693951
boolean isPrime = mersenne.isProbablePrime(50); // true
BigInteger next = BigInteger.valueOf(1_000_000).nextProbablePrime(); // 1000003The JDK uses the same class for cryptography. The method BigInteger.probablePrime(bits, random) creates a random prime of the requested size, and RSA key generation needs two such primes.
BigInteger keyPrime = BigInteger.probablePrime(1024, new SecureRandom());
int bits = keyPrime.bitLength(); // 1024We never write our own RSA code. The KeyPairGenerator class in java.security creates keys with the right primes and the right checks, and this snippet only shows where large primes come from.
6. Picking a Prime Table Size for a Hash Table
Some hash table designs, such as open addressing with double hashing, compute the bucket with a modulo and use a prime number of buckets, because keys that share a common step still spread over all buckets. Java’s own HashMap uses powers of two instead, so this need appears in custom data structures and in caches written for other platforms. A helper that returns the first prime at or above the requested capacity uses isPrime() from section 1.
static int nextPrime(int capacity) {
int candidate = Math.max(capacity, 2);
while (!isPrime(candidate)) {
candidate++;
}
return candidate;
}int buckets = nextPrime(1000); // 1009
int small = nextPrime(1); // 2The gaps between primes are small in the int range, and the largest gap is 292 numbers, so the loop needs at most a few hundred isPrime() calls and only a few for most capacities.
7. Choosing a Prime Number Method
Each method fits a different question, so we pick by what we know in advance, a single number, a limit or a count.
| Task | Method | Time | Extra memory |
|---|---|---|---|
| Is this int or long prime? | Trial division to the square root, or 6k +/- 1 | O(sqrt n) | None |
| All primes from 2 to N | Sieve of Eratosthenes | O(N log log N) | N bytes, or N bits with BitSet |
| All primes from 2 to N, small N | Stream with filter(isPrime) | About O(N sqrt N) | Only the result |
| First N primes | Sieve up to N (ln N + ln ln N), or a stream with limit() | Sieve cost of the limit | Sieve array |
| Numbers beyond long | BigInteger.isProbablePrime() | Fast for hundreds of digits | Small |
8. Prime Numbers in Java FAQs
Homework sheets and interview rounds about primes ask about the number 1, the square root limit, built-in methods and the speed of the sieve.
8.1. Is 1 a prime number?
No. A prime has two different divisors, 1 and itself, and 1 has only one. That is why every method in this article starts at 2, and isPrime(1) returns false.
8.2. Why do we check divisors only up to the square root?
Because divisors come in pairs. If d divides n, so does n / d, and one of the two is at most the square root of n. If no divisor is found up to the square root, none exists above it either.
8.3. How do we print the prime numbers from 1 to 100 in Java?
We call the sieve with 100 and print the list. There are 25 primes up to 100.
List<Integer> upTo100 = primesUpTo(100);
int howMany = upTo100.size(); // 25
List<Integer> lastFour = upTo100.subList(21, 25); // [79, 83, 89, 97]8.4. Is there a built-in method to check whether a number is prime in Java?
Only in BigInteger. The JDK has no isPrime() method for int or long, so we either write trial division or convert the value with BigInteger.valueOf(n).isProbablePrime(50). Guava has a deterministic LongMath.isPrime() if the project already depends on it.
8.5. What is the time complexity of the Sieve of Eratosthenes?
O(N log log N) time and O(N) space. The log log N factor grows so slowly that, for practical N, the sieve does a small constant amount of work per number.
9. Conclusion
To find all prime numbers from 2 to N in Java, we use the Sieve of Eratosthenes, which marks the multiples of each prime starting at its square, and switch to a BitSet when memory matters. To test one number, trial division up to the square root is enough, and the 6k +/- 1 pattern skips most of the useless divisors.
The first N primes come from a sieve with Rosser’s upper bound or from a stream with limit(), and numbers beyond long go through BigInteger.isProbablePrime(). For more number programs of this kind, see our Java examples.
10. References
- BigInteger (Java SE 25 API)
- BitSet (Java SE 25 API)
- IntStream (Java SE 25 API)
- Sieve of Eratosthenes (Wikipedia)
- Approximations for the nth prime number (Wikipedia)
Happy Learning !!
