Count Prime Numbers in a Range in Java
Problem
Counting primes in a range means checking every number between two bounds and tallying how many are prime, without needing to list them out.
Given a lower and upper bound, count how many prime numbers fall between them.
Java Program
public class CountPrimesInRange {
static boolean isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false; // found a divisor, not prime
}
return true;
}
public static void main(String[] args) {
int low = 10, high = 50;
int count = 0;
for (int i = low; i <= high; i++) {
if (isPrime(i)) count++; // one more prime found
}
System.out.println("Prime count: " + count);
}
}Output
Core Logic
Testing every number in the range for primality, and incrementing a counter for each one that passes, tallies the total without needing to store the primes themselves.
- 1
isPrime(n)is a helper method testing divisors only up to√n. - 2The loop tries every
ifromlowtohigh, inclusive. - 3
isPrime(i)checks whether the current number qualifies, incrementingcountwhen it does. - 4After the full scan,
countholds the total number of primes found in the range.
10 to 50, the scan finds 11 primes: 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47.Key Point: This is the same scan used to list primes in a range, but tallying a count instead of building a result string — no reason to hold onto the primes themselves if only the total is needed.
Why: Each of the n numbers in the range triggers its own O(√n) primality check, but only a single running counter is kept regardless of how many primes are found.
Key Concepts
Approach 2: Java 8
import java.util.stream.IntStream;
public class CountPrimesInRangeStream {
static boolean isPrime(int n) {
if (n < 2) return false;
return IntStream.rangeClosed(2, (int) Math.sqrt(n)).noneMatch(i -> n % i == 0);
}
public static void main(String[] args) {
int low = 10, high = 50;
// filter() keeps only primes; count() reduces to a single total
long count = IntStream.rangeClosed(low, high).filter(CountPrimesInRangeStream::isPrime).count();
System.out.println("Prime count: " + count);
}
}
Output
Core Logic
The same primality check can filter a stream of the range's numbers, then count() reduces the survivors straight down to a total.
- 1
IntStream.rangeClosed(low, high)generates every number in the range. - 2
.filter(...)keeps only the numbers that pass the primality check. - 3
.count()reduces the filtered stream down to a singlelongtotal.
count() reports 11.Key Point: count() never has to collect the primes into a list — it just tallies as it filters, the stream equivalent of the loop version's running counter.
Why: The stream still runs the same O(√n) primality check per number, and count() reduces straight down to a single long without collecting anything.