2
\$\begingroup\$
public static long sumOfPrimes(long max){
    long sum = 0;
    long primes[] = new long[((int)max/2)+1];
    int index = 0;
    for(long counter = 2; counter <= max; counter++){
        if(isPrime(counter, primes)){
            sum += counter;
            primes[index++] = counter;
        }
    }
    return sum;
}

public static boolean isPrime(long num, long[] primes){
    if(num == 2 || num == 3){
        return true;
    }

    //System.out.println(Arrays.toString(primes));
    long primesCount = primes.length;
    for(int i = 0; i < primesCount; i++){
        if(primes[i] !=0 && num % primes[i] == 0){
            return false;
        }
    }

    long range = (long) Math.sqrt((double)num);
    if(primesCount > 0 && primes[primes.length-1] < range)
    {
        for(long counter = 2; counter <= range; counter++){
            if(num % counter == 0){
                return false;
            }
        }
    }
    return true;
}

This code works fine for smaller N. For larger N, it throws timeout exception.

How can I improve my code? How do I fix timeout issue?

\$\endgroup\$
6
\$\begingroup\$

Sieve of Eratosthenes

The first possibility would be to implement the Sieve of Eratosthenes. It's one of the more efficient ways to find all primes between 1 and N. But there are other things we can do with your existing algorithm.

Initialize with 2

    long sum = 0;
    long primes[] = new long[((int)max/2)+1];
    int index = 0;

But you know the first prime number (at least I hope you do). So try this

    if (max < 2) {
        return 0;
    }
    long sum = 2;

    long primes[] = new long[((int)max/2)+1];
    primes[0] = 2;
    int index = 1;

This helps a little now, but it helps a lot later since we know that 2 is the only even prime. Since all even numbers are divisible by 2 and all primes are only divisible by themselves and 1, 2 is the only possible even prime.

Check fewer numbers

    for(long counter = 2; counter <= max; counter++){

This checks every number from 2 to max, but we can trivially reduce this to every odd number from 3 to max if we initialize the array with 2.

    for (long counter = 3; counter <= max; counter += 2) {

I also added some additional spaces, as I find they make it easier to read the code.

No evens or divisible by three

And we can actually do even better. Every third odd number is divisible by three. So

    if (max < 2) {
        return 0;
    } else if (max == 2) {
        return 2;
    }
    long sum = 5;

    long primes[] = new long[((int)max/2)+1];
    primes[0] = 2;
    primes[1] = 3;
    int index = 2;

    int increment = 4;
    for (long counter = 5; counter <= max; counter += increment) {
         increment = 6 - increment;

Now the increment varies between 2 and 4. So we have 5, 7, 11 (skipping 9), 13, 17... So we skip every number that is divisible by three. And you can never add an even number to an odd number and get an even number, so we skip all the evens as well.

Don't use a generic isPrime

Your code uses a generic isPrime method that will work regardless of the caller. You don't need to do that.

    if(num == 2 || num == 3){
        return true;
    }

You can skip this, as you never pass 2 or 3 to this method.

    //System.out.println(Arrays.toString(primes));

This is debugging code and shouldn't be sent to review.

    long primesCount = primes.length;
    for(int i = 0; i < primesCount; i++){
        if(primes[i] !=0 && num % primes[i] == 0){
            return false;
        }
    }

You can simplify this to just

    for (long prime : primes) {
        if (prime == 0) {
            return true;
        }

        if (num % prime == 0) {
            return false;
        }
    }

Now it will check that num is not divisible by any number in the primes array. Once it reaches the first 0, that means that it is done processing and can return true immediately.

Note that if primes were a List rather than an array, you wouldn't need to check for 0, as the List would only have prime values in it. Perhaps the performance improvement from not checking for 0 values would outweigh the increased overhead of the List.

    long range = (long) Math.sqrt((double)num);
    if(primesCount > 0 && primes[primes.length-1] < range)
    {
        for(long counter = 2; counter <= range; counter++){
            if(num % counter == 0){
                return false;
            }
        }
    }

You don't need this block of code. You already checked that it's not divisible by any of the primes less than it. You don't need to check it again with both primes and non-primes.

It's possible that you could save some time with the following optimizations:

    long range = (long) Math.sqrt((double)num);
    for (long i = 2; primes[i] <= range; i++) {
        if (num % primes[i] == 0) {
            return false;
        }
    }

    return true;

This relies on there always being at least one prime between range and num in the primes array. You might have to preload 5 into the primes array to make this work, as this skips past 3 which is greater than range. Alternatively you could check that primes[i] is not 0, but that would never happen if you start checking with 7.

Since we don't pass numbers divisible by 2 or 3 to this method, we don't need to attempt to divide by them. So we start with the third prime, primes[2] which is 5.

Note that this makes isPrime dangerously fragile. You may want to make it private rather than public to make it clear that it should only be called under limited circumstances. Unless performance is a big issue, the previous version is more robust. And the previous version may be faster anyway.

\$\endgroup\$
2
  • \$\begingroup\$ I am not able to understand for (long counter = 5; counter <= max; counter += increment) { increment = 6 - increment; . Why do we need to change increment inside loop? Please explain \$\endgroup\$
    – Gibbs
    Apr 13 '16 at 6:36
  • 1
    \$\begingroup\$ Because you want to alternate between adding 2 and adding 4. \$\endgroup\$ Apr 13 '16 at 9:25
0
\$\begingroup\$

Performance

You can use a Sieve of Eratosthenes:

import java.util.BitSet;

public class Primes {
    /**
     * The maximum number of {@link #Primes primes} that will be stored.
     */
    public static final int MAX_NUMBER_OF_PRIMES = 200000;

    /**
     * The maximum number of odd numbers that will be {@link #OddPrimeSieve sieved}.
     */
    public static final int MAX_SIEVE_SIZE       = 1500000;

    /**
     * A list of prime numbers.
     * 
     * This will be populated with values up to {@link #NumPrimes}
     */
    private static final int[] Primes = new int[ MAX_NUMBER_OF_PRIMES ];

    /**
     * A Sieve of Eratosthenes for odd numbers greater than 1.
     */
    private static final BitSet OddPrimeSieve = new BitSet( MAX_SIEVE_SIZE );

    /**
     * The current maximum prime value to have been found in the
     * {@link #OddPrimeSieve sieve}.
     */
    private static int MaxSieved;

    /**
     * The number of prime values which have been found and stored in the
     * {@link #Primes list}.
     */
    private static int NumPrimes = 0;

    static
    {
        Primes[ NumPrimes++ ] = 2;
        Primes[ NumPrimes++ ] = MaxSieved = 3;
        OddPrimeSieve.set(0, OddPrimeSieve.size() - 1, true);
    }

    /**
     * Translate an odd potential-prime (i.e. 3 or greater) number to
     * its sieve index;
     * @param value The odd number to translate to a sieve index.
     * @return The index within the sieve.
     */
    private static int getSieveIndex( final int value )
    {
        return ( value - 3 ) / 2;
    }

    /**
     * Translate a sieve index to its equivalent odd number value.
     * @param sieveIndex The index within the sieve.
     * @return The odd number represented by that sieve index.
     */
    private static int getInverseSieveIndex( final int sieveIndex )
    {
        return sieveIndex * 2 + 3;
    }

    /**
     * Checks if the value is a prime number.
     * @param value The number to check.
     * @return Whether the number is prime.
     */
    public static boolean isPrime( final int value )
    {
        if ( value == 2 ) return true;
        if ( value < 2 || (value % 2) == 0 ) return false;
        if ( value > getInverseSieveIndex( MAX_SIEVE_SIZE ) )
            throw new IndexOutOfBoundsException( "Value outside of sieve limits." );

        // Quick check of the sieve to see if the value is a multiple of an
        // existing prime and can be immediately rejected as a non-prime.
        if ( !OddPrimeSieve.get( getSieveIndex( value ) ) )
            return false;

        // Find primes until an equal or higher prime has been found.
        while ( MaxSieved < value )
        {
            getNthPrime( NumPrimes + 1 );
        }

        // Check the sieve to see if the value is a prime.
        return OddPrimeSieve.get( getSieveIndex( value ) );
    }

    /**
     * Returns the n<sup>th</sup> prime.
     * @param n The ordinal number of the prime to return.
     * @return The nth prime
     */
    public static int getNthPrime( final int n )
    {
        if ( n < 1 )
            throw new IllegalArgumentException( "Zeroth or negative primes do not exist." );
        if ( n > MAX_NUMBER_OF_PRIMES )
            throw new IllegalArgumentException( "n exceeds maximum." );

        int sieveIndex = getSieveIndex( MaxSieved );
        int multiple;

        while( NumPrimes < n )
        {
            // Set all higher multiples of the current prime to be non-prime.
            for ( multiple = sieveIndex + MaxSieved;
                    multiple < OddPrimeSieve.size();
                    multiple += MaxSieved )
            {
                OddPrimeSieve.set( multiple, false );
            }

            // Find the next index in the sieve which is prime.
            sieveIndex = OddPrimeSieve.nextSetBit(sieveIndex + 1);

            // Check there is a valid sieve index.
            if ( sieveIndex == -1 )
                throw new IndexOutOfBoundsException( "Next prime is outside of sieve limits." );

            // Convert the sieve index to a prime and store it in the list.
            Primes[ NumPrimes ] = MaxSieved = getInverseSieveIndex( sieveIndex );
            NumPrimes++;
        }

        return Primes[ NumPrimes - 1 ];
    }
}

Then if you want to get the sum up to a given limit you could do:

public static void main( final String[] args )
{
    final int LIMIT = 2000000;
    long sum = 0;
    int  n = 0,
         p;
    long start = System.nanoTime();
    do
    {
        sum += p = getNthPrime( ++n );
    }
    while ( p < LIMIT );
    sum -= p;
    long end   = System.nanoTime();
    System.out.println( "Number of primes found: " + n );
    System.out.println( String.format( "First prime above %d: %d", LIMIT, p ) );
    System.out.println( String.format( "Sum of primes up to %d: %d", LIMIT, sum ) );
    System.out.println( "Time to calculate (ms): " + (end-start)/1e6 );
}

Which outputs:

Number of primes found: 148934
First prime above 2000000: 2000003
Sum of primes up to 2000000: 142913828923
Time to calculate (ms): 25.896941
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.