CODEWITHSUNDEEP
javaprimes
ccc
ccc

Reputation: 370

Prime numbers calculator takes too much time (JAVA)

When I run this code to find sum of prime numbers below 20 it works fine, but when try to find sum below 2500000 it takes too much time. It's been at least 20 minutes and it's still running. It seems like it's not working. How do I fix it?

class PrimeSummation {
    public static void main(String[] args) {
        int sum = 0;
        for(int i = 1; i < 2500000; i++) {
            int count = 0;
            for(int j = 1; j < i + 1; j++) {
                if((i%j) == 0) {
                    count++;
                }
            }
            if(count == 2) {
                sum += i;
            }
        }
        System.out.println(sum);
    }
}

Upvotes: 0

Views: 183

Answers (3)

WillShackleford
WillShackleford

Reputation: 7018

Keeping track of previously found primes seems to help:

    BigInteger sum = BigInteger.ZERO;
    List<Integer> primes = new ArrayList<>();
    for(int i = 2; i < 2500000; i++) {
        boolean isPrime = true;
        for(int j = 0; j < primes.size() && primes.get(j)<= Math.sqrt(i); j++) {
            int p = primes.get(j);
            if((i%p) == 0) {
                isPrime=false;
                break;
            }
        }
        if(isPrime) {
            sum = sum.add(BigInteger.valueOf(i));
            primes.add(i);
        }
    }
    System.out.println(sum);

Came up with answer:

219697708195

Upvotes: 3

Sakib Ahammed
Sakib Ahammed

Reputation: 2480

If you want better performance for generating a large number prime number, you should use Sieve formula.

You can Learn Sieve_of_Eratosthenes formula for prime number generation.

According to Sieve_of_Eratosthenes:

import java.util.*;

public class Sieve
{
    private BitSet sieve;

    private Sieve() {}

    private Sieve(int size) {
        sieve = new BitSet((size+1)/2);
    }

    private boolean is_composite(int k)
    {
        assert k >= 3 && (k % 2) == 1;
        return sieve.get((k-3)/2);
    }

    private void set_composite(int k)
    {
        assert k >= 3 && (k % 2) == 1;
        sieve.set((k-3)/2);
    }

    public static List<Integer> sieve_of_eratosthenes(int max)
    {
        Sieve sieve = new Sieve(max + 1); // +1 to include max itself
        for (int i = 3; i*i <= max; i += 2) {
            if (sieve.is_composite(i))
                continue;

            // We increment by 2*i to skip even multiples of i
            for (int multiple_i = i*i; multiple_i <= max; multiple_i += 2*i)
                sieve.set_composite(multiple_i);

        }
        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        for (int i = 3; i <= max; i += 2)
            if (!sieve.is_composite(i))
                primes.add(i);

        return primes;
    }
}

Performance:

enter image description here

Upvotes: 1

Paul Boddington
Paul Boddington

Reputation: 37665

sum cannot be an int because the answer is 219697708195 whereas Integer.MAX_VALUE is only 2147483647. You must use a long or a BigInteger instead.

Your algorithm is very slow, because for every one of the 2500000 numbers you are starting from scratch to decide whether it is prime or not, and your approach for testing whether a number is prime (try every possible factor) is not very efficient.

The following code produces the answer in about a tenth of a second on my machine.

int num = 2500000;
long sum = 0;
boolean[] arr = new boolean[num];
for (int p = 2; p < num; p++) {
    if (!arr[p]) {
        sum += p;
        for (int k = p * 2; k < num; k += p)
            arr[k] = true;
    }
}
System.out.println(sum);

Upvotes: 3

Related Questions