如何讓此代碼適用於BigIntegers？此代碼是關於查找數字（n）的最大素數因子

-4

public class E2 { 

    public static void main(String[] args) { 
     long i,f,n=12345,p=1,j; 
     for(i=2;i<n;i++) 
     { 
      if(n%i==0) 
      { 
       f=i; 
       for(j=2;j<=f/2;j++) 
       { 
        if(f%j==0) 
         break; 
        else 
         continue; 
       }j--; 
       if(j==f/2) 
        p=f; 
      } 
      else 
      {continue;} 
     } 
     System.out.println(p); 
    } 
}

這裏，n是一個隨機數，其最大質數要查找。代碼適用於很長的整數。我首先應用一個for循環來找到一個因子n，並檢查該因子是否爲素數，如果它們是素數，則它們存儲在p中，因此p的最後一個值是最大的素數因子。如何讓此代碼適用於BigIntegers？此代碼是關於查找數字（n）的最大素數因子

來源

2016-01-23 Shubham

您是否嘗試過使用'BigInteger'？如果是，你失敗了？您是否閱讀過[JavaDoc]（https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html）？ – Tom

是的，我試過BigInteger，當我需要在循環（重複）中分割並找到BifInteger的mod時，我被卡住了。 – Shubham

這種方法效率很低，如果您需要處理更大的數字，那麼長時間不適合，您還需要使用更好的算法。

以下程序仍然只適用於long，但效率更高。然而，它仍然不足以超越long的範圍。請注意，對於您添加的每兩位數字，最差情況下的運行時間將增加10倍。

將給定測試用例的運行時間與您的方法進行比較。或者如果你不想等這麼長時間，可以拿一些較小的數字，如1234567890L。

它通過劃分較小的素數因子來工作，並且因此避免了需要檢查發現的因素是否爲素數，因爲之前已經發現了較小的因子。

經過檢查高達sqrt（n）的因素後，剩餘的未分割片n必須是素數（或1）。這是因爲否則其中一個主要因素必須小於或等於sqrt（n），因此以前會發現它。

實際上，只用質數進行試用分區就足夠了，但由於我們沒有列表，所以在這裏採取的折衷辦法是將2作爲特例，然後只嘗試奇數。與簡單版本相比，該算法加快了算法的2倍。

public class Main { 

    public static void main(String[] args) { 
     long n = 123456789L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
     n = 123456789L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
     n = 123456789L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
     n = 123456789L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
     n = 4611686014132420609L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
    } 

    public static long largestPrimeFactorOf(long n) { 
     long last = 1; 
     while (n % 2 == 0) { 
      System.out.printf("prime factor 2 found%n"); 
      n /= 2; 
      last = 2; 
     } 
     for (long t = 3; t * t <= n; t += 2) { 
      while (n % t == 0) { 
       System.out.printf("prime factor %d found%n", t); 
       n /= t; 
       last = t; 
      } 
     } 
     return n == 1 ? last : n; 
    } 
}

這個程序的輸出是

prime factor 3 found 
prime factor 3 found 
prime factor 101 found 
prime factor 3541 found 
prime factor 3607 found 
prime factor 3803 found 
largest prime factor of 123456789is 27961 
prime factor 7 found 
prime factor 164005957 found 
largest prime factor of 123456789is 1075368509 
prime factor 38429233 found 
largest prime factor of 123456789is 32125748909 
largest prime factor of 123456789is 123456789
prime factor 2147483647 found 
prime factor 2147483647 found 
largest prime factor of 4611686014132420609 is 2147483647

來源

2016-01-23 09:32:08 Henry

是的，這段代碼真的很高效，感謝您的幫助！ – Shubham

對於完全不同的問題，這是一個很好的答案。 –

@DavidWallace在技術上是的，因爲我覺得原來的問題是一個XY問題的實例http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem，真正的問題是「如何可以我讓它適用於更大的數字「 – Henry

如何讓此代碼適用於BigIntegers？此代碼是關於查找數字（n）的最大素數因子

回答

相關問題