素數分解算法大數失敗

Question

我遇到了項目歐拉問題3的一個奇怪問題。該方案適用於那些小的，像13195等號碼，但是當我嘗試緊縮大的數字，如600851475143它拋出這個錯誤：

Exception in thread "main" java.lang.ArithmeticException:/by zero 
    at euler3.Euler3.main(Euler3.java:16) 

這裏是我的代碼：

//Number whose prime factors will be determined 
    long num = 600851475143L; 

    //Declaration of variables 
    ArrayList factorsList = new ArrayList(); 
    ArrayList primeFactorsList = new ArrayList(); 

    //Generates a list of factors 
    for (int i = 2; i < num; i++) 
    { 
     if (num % i == 0) 
     { 
      factorsList.add(i); 
     }   
    } 

    //If the integer(s) in the factorsList are divisable by any number between 1 
    //and the integer itself (non-inclusive), it gets replaced by a zero 
    for (int i = 0; i < factorsList.size(); i++) 
    { 
     for (int j = 2; j < (Integer) factorsList.get(i); j++) 
     { 
      if ((Integer) factorsList.get(i) % j == 0) 
      { 
       factorsList.set(i, 0); 
      } 
     } 
    } 

    //Transfers all non-zero numbers into a new list called primeFactorsList 
    for (int i = 0; i < factorsList.size(); i++) 
    { 
     if ((Integer) factorsList.get(i) != 0) 
     { 
      primeFactorsList.add(factorsList.get(i)); 
     } 
    } 

爲什麼只有大數字導致這個錯誤？

Answer 1

你的代碼只是使用Integer，這是一個32位類型，最大值爲2147483647.當用於比這個數字大得多的數字時，它並不會令人驚訝。請注意，您的初始循環使用int作爲循環變量，所以如果它沒有拋出異常，它實際上會永久循環。 i的值將從2147483647變爲-2147483648並繼續。

使用BigInteger來處理任意大的值，或者如果您對有限的範圍感到滿意，但是對較大的值感到滿意，則可以使用Long。 （中long/Long的最大值爲9223372036854775807L。）

但是，我懷疑，這是真的的預期的做法......這將花費很長時間爲大數這樣。

Answer 2

除了由喬恩斯基特提到BigInteger問題，注意以下幾點：

1. 你只需要測試的因素多達每次sqrt(num)
2. 你找到一個因素，由要素劃分num和然後測試因素再次
3. 有真的無需使用收集到的素數預先存儲

我的解決方案（最初是用Perl編寫的）會是這個樣子在Java中：

long n = 600851475143L;   // the original input 
long s = (long)Math.sqrt(n);  // no need to test numbers larger than this 
long f = 2;      // the smallest factor to test 
do { 
    if (n % f == 0) {   // check we have a factor 
     n /= f;     // this is our new number to test 
     s = (long)Math.sqrt(n); // and our range is smaller again 
    } else {      // find next possible divisor 
     f = (f == 2) ? 3 : f + 2; 
    } 
} while (f < s);     // required result is in "n" 

Answer 3

不知道這是否是因爲我不知道這行是如此 - 但我注意到你的第一個循環使用一個int。

//Generates a list of factors 
for (int i = 2; i < num; i++) 
{ 
    if (num % i == 0) 
    { 
     factorsList.add(i); 
    }   
} 

爲num是一個長期的，它可能是num > Integer.MAX_INT和你的循環在MAX_INT蔓延到負值，則循環，直到0，給你一個num % 0操作。

Answer 4

爲什麼您的解決方案無法正常工作？

井號在硬件上是離散的。離散意味着你有一個最小值和最大值。 Java使用two's complement來存儲負值，所以2147483647+1 == -2147483648。這是因爲對於類型int，最大值是2147483647。這樣做被稱爲溢出。

看起來好像你有一個overflow bug。首先變爲負數，最終爲0，因此您得到java.lang.ArithmeticException:/by zero。如果您的計算機每秒可循環1000萬條語句，則需要1小時10分鐘才能重現，因此我將其作爲假設並非證明。

這也是一個普通的簡單陳述如a+b可能會產生錯誤的原因。

如何解決？

package margusmartseppcode.From_1_to_9; 

public class Problem_3 { 
    static long lpf(long nr) { 
     long max = 0; 

     for (long i = 2; i <= nr/i; i++) 
      while (nr % i == 0) { 
       max = i; 
       nr = nr/i; 
      } 

     return nr > 1 ? nr : max; 
    } 

    public static void main(String[] args) { 
     System.out.println(lpf(600851475143L)); 
    } 
} 

你可能會想：「那麼這是如何工作的？

那麼我艱難的過程很類似：

1. （動態規劃方法）如果我有質數列表X{2,3,5,7,11,13,17, ...}達價值X _我> NR/2，然後尋找最大素因素是微不足道的：
   • 我從最大的素數開始，並開始測試如果devision提醒與我的號碼是零，如果是，那麼這就是答案。
   • 如果循環所有元素後，我沒有找到答案，我的編號必須是本身的素數。
2. （蠻力，帶過濾器）我認爲，這
   • 我的號碼最大素因數小（不到10萬美元）。
   • 如果我的數字是某個數字的倍數，那麼我可以減少這個倍數的循環大小。

我在這裏使用了第二種方法。

但是，請注意，如果我的電話號碼和{600851475013, 600851475053, 600851475067, 600851475149, 600851475151}中的一個很少，那麼我的方法假設就會失敗，程序運行的時間會很長。如果計算機可以每秒執行10m語句，則需要6.954天才能找到正確的答案。

在你的蠻力的方法，只是生成一個因素列表將需要更長的時間 - 假設你以前沒有用完內存。

有沒有更好的方法？

當然，在數學，你可以把它寫成：

P3[x_] := FactorInteger[x][[-1, 1]] 
P3[600851475143] 

或只是FactorInteger[600851475143]，並且查找最大的價值。

這是可行的，因爲在Mathematica中你有任意大小的整數。 Java也有任意大小的整數類BigInteger。