1

我正在尝试使用 Eratosthenes 筛法来查找大量的最大素数（Project Euler 中的问题 3）。

我的语法似乎是正确的，我使用的是 Long（不是 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();
    }
 }
4

3 回答 3

1

感谢大家耐心地浏览我的代码，我意识到这一定非常痛苦:)

我刚刚解决了这个问题。回想起来，我以前的方法似乎非常复杂。这是我使用的最终解决方案，更加优雅，尽管它仍有改进的空间：

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

}
于 2012-04-17T02:21:34.160 回答
0

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

于 2012-04-15T03:59:45.780 回答
0

一个有趣的方法。当然，没有人应该解决您的欧拉挑战。但是你知道吗，第二次，你输入 'factor' nowTesting 是 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);

并且您可能在因素中识别出“长”参数前面的“最终”？如果您将所有未更改的内容标记为final，它有助于推理代码。在实践中，结果是，您的 Javacode 中充斥着“final”修饰符，但事实就是如此。这是好的代码的标志——也许不是好的设计。Final 可能是默认值。

于 2012-04-15T03:04:53.623 回答