Euler Problem 58

This one was pretty easy except for the fact that I need about 1024M of heap space to run it. 800M prime numbers will do that you know. Initially did it with ArrayLists but took too long. Used raw boolean arrays and dropped it to 4 mins.

public String Problem ()
    {
        Primes P = new Primes();
        P.buildPrimes();
        double ratio = 1;
        int count = 0, side = 3, number = 3;
        while (ratio >= .1)
        {
            if (side > 3)
                number += (side - 1);
            for (int i = 1; i <= 3; i++)
            {
                if (P.testPrime(number))
                    count++;
                number += (side - 1);
            }
            ratio = (double) count/(2*side-1);
            side = side + 2;
        }
        return String.valueOf(side-2);
    }
    public class Primes
    {
        int limit = 800000000;
        boolean [] isPrime = new boolean [limit];
        public void buildPrimes ()
        {
            for (int i = 2; i < limit; i++)
                isPrime[i] = true;
            for (int p = 2; p*p < limit; p++)
                if (isPrime[p] == true)
                    for (int m = p*p; m < limit; m = m+p)
                        if (m % p == 0)
                            isPrime[m] = false;
        }
        public boolean testPrime (int num)
        {
            return isPrime[num];
        }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s