Tag Archives: rectangle

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];
        }
    }