Project Euler prob. 3 IndexOutOfBoundsException

Question

I'm trying to use a Sieve of Eratosthenes method for finding the largest prime factor of a large number (problem 3 in Project Euler).

My syntax seems to be correct, and i am using Long (not int), but I'm getting the following error message:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 1
    at java.util.ArrayList.rangeCheck(Unknown Source)
    at java.util.ArrayList.get(Unknown Source)
    at problem3.ProblemThree.Factor(ProblemThree.java:49)
    at problem3.ProblemThree.Recursion(ProblemThree.java:37)
    at problem3.ProblemThree.main(ProblemThree.java:83)

I don't know why this is happening. Could somebody please tell me what I'm doing wrong here?

 package problem3;

 import java.util.List;
 import java.util.ArrayList;

 public class ProblemThree 
 {
    //initializing variables and lists
    long factorNo;
    long nowTesting;
    int i;  
    List<Long> allPrimeList = new ArrayList<Long>();
    List<Long> ourPrimes = new ArrayList<Long>();

    ProblemThree(long x)    //constructor; the input "x" is the number whose highest prime factor is being sought
    {
        factorNo = x;     
    }       

    void initialize()   //use the workaround initialization (add 2 to the allPrimesList, set nowTesting to 3). 
                        //If the factorNo is even, add 2 to the primes list
                        //TODO: need more elegant solution 
    {
        allPrimeList.add((long) 2);
        nowTesting=3;
        if(factorNo % 2 == 0) ourPrimes.add((long) 2);
        i = 0;
    }        

    void recursion()    //keep factoring the next nowTesting until the next nowTesting is greater than half of the factorNo
    {
        while (nowTesting <= (factorNo/2))
        {
            nowTesting = factor(nowTesting);
        }
        System.out.println(ourPrimes);
    }

    long factor(long t) //The factorization algorithm. Lists all the factors of long t
    {
        nowTesting = t;

 // Line 49:
     if ((nowTesting % allPrimeList.get(i)) == 0)
        {
            i = 0;
            return (nowTesting + 2);            
        }
        else
            if(i <= allPrimeList.size()) //if we have not yet reached the end of ourPrimeList
            {
                i++;
                return nowTesting;
            }
            else    //if the end of ourPrimeList has been reached without a single modulus==0, this number is a prime
            {
                allPrimeList.add(nowTesting);

                if(factorNo%nowTesting==0) //if the nowTesting is a prime factor of factorNo, it will be perfectly divisible
                {
                    ourPrimes.add(nowTesting);
                }                    
                i=0;
                return (nowTesting+2);   
            }            
    }

    public static void main (String[] args)
    {
        ProblemThree pt = new ProblemThree(600851475143L);
        pt.initialize();
        pt.recursion();
    }
 }

Answer 1

thank you everyone for patiently wading through my code, I realize that it must have been excruciatingly painful :)

I have just solved the problem. My previous approach seems very complicated in retrospect. This is the final solution I used, quite a bit more elegant, although it still has room for improvement:

//second attempt from the ground up!
package problem3;


public class BiggestPrime 
{
    long lInput;
    long factorTest;
    long currentHeight;
    boolean divided;

    public BiggestPrime(long n)
    {
        factorTest = 2;
        currentHeight = n;

        System.out.println("The prime factors of " + n + " are:"); 

        while (factorTest<currentHeight)
        {
            if (divided == true) {factorTest = 2; divided = false;}
            if (factorTest > currentHeight) {System.out.println("factorTest is greater than currentHeight; breaking"); break;}
            if (currentHeight%factorTest==0)
            {
                System.out.println(factorTest); 
                currentHeight /= factorTest; 
                divided = true;
            } 
            else { factorTest = factorTest + 1L; divided = false;}
        }
        if (factorTest == currentHeight)
        {
            System.out.println(factorTest);
        }
        System.out.println("The end"); 

    }


    public static void main (String[] args)
    {
        BiggestPrime bp = new BiggestPrime(600851475143L);
    }

}

Answer 2

At line 49, shouldn't you be checking if nowTesting is divisible by i, not the ith element of allPrimes?

Answer 3

An interesting approach. Of course, nobody should solve your Euler challenges. But did you know that the second time, you enter 'factor' nowTesting is 3?

// The factorization algorithm. Lists all the factors of long t
long factor (final long nowTesting) 
{
    System.out.println ("entering factor: " + nowTesting);

Minor ideas:

 allPrimeList.add ((long) 2);

can be written:

 allPrimeList.add (2L);

and you pobably recognized the "final" in front of the 'long' parameter in factor? It helps reasoning about code, if you mark everything which isn't changed final. In practise, the consequence is, that your Javacode is cluttered with 'final' modifiers, but that's how it is. It's a sign of good code - maybe not of good design. Final could have been the default.