Project Euler prob。 3 IndexOutOfBoundsException

Question

我正在嘗試使用Eratosthenes的Sieve方法來查找大數的最大素數因子（Project Euler中的問題3）。

我的語法似乎是正確的，我用龍（不是int），但我發現了以下錯誤消息：

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) 

我不知道爲什麼會這樣。有人能告訴我我在做什麼錯嗎？

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

一個有趣的方法。當然，沒有人應該解決你的歐拉挑戰。但是你是否知道第二次，你現在輸入'factor'TestTesting是3？

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

小想法：

allPrimeList.add ((long) 2); 

可以寫成：

allPrimeList.add (2L); 

，你pobably承認在因素 '長' 參數的前 「最後」？它有助於推理代碼，如果你標記最後沒有改變的所有東西。在實踐中，結果是，你的Javacode與'final'修飾符混雜在一起，但事實就是如此。這是一個好代碼的標誌 - 也許不是很好的設計。最後可能是默認的。

Answer 2

在49行，你不應該檢查nowTesting是否可以被i整除，而不是allPrimes的第i個元素嗎？

Answer 3

謝謝大家通過我的代碼耐心涉水，我知道這肯定是極其痛苦:)

我剛纔已經解決了這個問題。回顧過去，我以前的做法看起來非常複雜。這是我使用的最終解決方案，雖然仍有改進空間，但它仍然有更大的優勢：

//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); 
    } 

}