#Not a sieve#

You claimed that you were using a Sieve of Eratosthenes algorithm but your program actually uses a trial division algorithm. This trial division is fast enough for primes up to 1000000, but it becomes slower and slower as you try to find higher primes.

For instance, I modified your program to add up all the primes up to 50000000. I compared it my own program that did the same thing using a sieve algorithm. The trial division program took 13.4 seconds versus only 0.42 seconds for the sieve program, which is a 32x speed difference.

#Example of sieve#

Here is the sieve function I used to add up all the primes to 50000000:

public static long addPrimes(int n)
{
 boolean [] isComposite = new boolean[n+1];
 int sqrtn = (int) Math.sqrt(n);
 // This is the sieve. It computes whether each number is prime.
 for (int i = 3; i < sqrtn; i += 2) {
 if (!isComposite[i]) {
 int increment = i+i;
 for (int j = i*i; j <= n; j += increment) {
 isComposite[j] = true;
 }
 }
 }
 // Now add up all the primes.
 long total = 0;
 // Start with 2 as the first prime.
 if (n >= 2)
 total = 2;
 // Add each prime from the sieve.
 for (int i = 3; i < n; i += 2) {
 if (!isComposite[i]) {
 total += i;
 }
 }
 return total;
}

Not a sieve

You claimed that you were using a Sieve of Eratosthenes algorithm but your program actually uses a trial division algorithm. This trial division is fast enough for primes up to 1000000, but it becomes slower and slower as you try to find higher primes.

For instance, I modified your program to add up all the primes up to 50000000. I compared it my own program that did the same thing using a sieve algorithm. The trial division program took 13.4 seconds versus only 0.42 seconds for the sieve program, which is a 32x speed difference.

Example of sieve

Here is the sieve function I used to add up all the primes to 50000000:

public static long addPrimes(int n)
{
 boolean [] isComposite = new boolean[n+1];
 int sqrtn = (int) Math.sqrt(n);
 // This is the sieve. It computes whether each number is prime.
 for (int i = 3; i < sqrtn; i += 2) {
 if (!isComposite[i]) {
 int increment = i+i;
 for (int j = i*i; j <= n; j += increment) {
 isComposite[j] = true;
 }
 }
 }
 // Now add up all the primes.
 long total = 0;
 // Start with 2 as the first prime.
 if (n >= 2)
 total = 2;
 // Add each prime from the sieve.
 for (int i = 3; i < n; i += 2) {
 if (!isComposite[i]) {
 total += i;
 }
 }
 return total;
}