patternjavaMinor
Efficient Sum of Primes
Viewed 0 times
efficientprimessum
Problem
I wrote this simple implementation of the sum of primes for the code eval
Challenge Description:
Write a program which determines the sum of the first 1000 prime numbers.
I would like to know of a better - more efficient - way of implementing the solution.
As for the primality test I only know of these other:
and
Challenge Description:
Write a program which determines the sum of the first 1000 prime numbers.
I would like to know of a better - more efficient - way of implementing the solution.
import java.lang.Math;
public class SumOfPrimes {
public static boolean isPrime(int n) {
if (n < 2) {
return false;
}
if (n == 2) {
return true;
}
if (n % 2 == 0) {
return false;
}
for (int i = 3; i <= Math.sqrt((double) n); i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
long sum = 0;
for (int i = 1, count = 0; count < 1000; i++) {
if (isPrime(i)) {
sum += i;
count++;
}
}
System.out.print(sum);
}
}As for the primality test I only know of these other:
for (int divisor = 2; divisor < n; divisor++) {
if (n % divisor == 0) {
return false;
}
}
return true;and
for (int divisor = 2; divisor <= n/2; divisor++) {
if (n % divisor == 0) {
return false;
}
}
return true;Solution
You've written a very literal and straightforward implementation to solve the challenge: test numbers for primality, and accumulate them until you have 1000 of them.
However, when you want to find many prime numbers, an algorithm such as the sieve-of-eratosthenes is more efficient than repeated trial division. Here is a benchmark that illustrates the difference. Your program follows the same basic outline as @Legato's solution, except that you haven't implemented some optimization hacks. If you just want to sum the first 1000 primes, there isn't much of a difference in execution time, but your program will not scale up as gracefully as a sieve algorithm.
However, when you want to find many prime numbers, an algorithm such as the sieve-of-eratosthenes is more efficient than repeated trial division. Here is a benchmark that illustrates the difference. Your program follows the same basic outline as @Legato's solution, except that you haven't implemented some optimization hacks. If you just want to sum the first 1000 primes, there isn't much of a difference in execution time, but your program will not scale up as gracefully as a sieve algorithm.
Context
StackExchange Code Review Q#93178, answer score: 8
Revisions (0)
No revisions yet.