Find Sum of Prime Numbers in Java
Problem
A prime number is a number greater than 1 that has exactly two factors: 1 and itself.
Given a range from 2 up to a limit, find the sum of every prime number within it.
Java Program
public class SumOfPrimeNumbers {
static boolean isPrime(int n) {
if (n < 2) return false;
for (int i = 2; (long) i * i <= n; i++) {
if (n % i == 0) return false; // found a divisor, not prime
}
return true;
}
public static void main(String[] args) {
int limit = 20;
int sum = 0;
for (int i = 2; i <= limit; i++) {
if (isPrime(i)) sum += i; // only primes contribute to the running total
}
System.out.println("Sum of primes: " + sum);
}
}Output
Core Logic
Testing every number in the range for primality, and adding the ones that qualify into a running total, combines the prime check with the summing in a single sweep.
- 1
isPrime(n)tests divisibility by every candidate from2up to√n, the same square-root-bound technique used to check a single prime. - 2The main loop tries every number
ifrom2up to the limit. - 3Each number that passes
isPrime(i)is added intosum. - 4After the loop finishes,
sumholds the total of every prime found.
77.Key Point: Reusing the same square-root-bound primality check inside the loop is what keeps this efficient — checking each candidate the naive way (dividing by every number up to itself) would make the whole range far slower to sum.
Why: Checking each of the n numbers for primality costs O(√n), so the total work across the whole range is O(n√n), with only a running sum kept in memory.
Key Concepts
Approach 2: Java 8
import java.util.stream.IntStream;
public class SumOfPrimeNumbersStream {
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 limit = 20;
// Keeps only the primes in the range, then reduces them to a single total
int sum = IntStream.rangeClosed(2, limit).filter(SumOfPrimeNumbersStream::isPrime).sum();
System.out.println("Sum of primes: " + sum);
}
}
Output
Core Logic
The same filter-then-add idea can be expressed as a stream — keep only the primes, then reduce them down to a single total.
- 1
IntStream.rangeClosed(2, limit)generates every candidate number in the range. - 2
.filter(SumOfPrimeNumbersStream::isPrime)keeps only the numbers that pass the same square-root-bound primality check. - 3
.sum()reduces the filtered stream down to a single total.
77 the loop version finds.Key Point: The primality check itself is unchanged — only how the range is walked and summed changes, from an imperative loop to a stream pipeline.
Why: The stream still runs the same O(√n) primality check on each of the n candidates, and sum() reduces to a single total without collecting anything.