C++長長的費馬原始性測試的最大素因子

-2

我對編程有點新，現在試圖找到項目歐拉最大的主因子600851475143。當我真正嘗試並進行Fermat Primality測試時，我的代碼不會編譯。C++長長的費馬原始性測試的最大素因子

#include <iostream> 
#include <cmath> 
#include <cstdlib> 

using namespace std; 

int main() { 

long long int num = 600851475143; 
long long int factor = num/2; 

for (long long factor; factor > 0; factor--) { 

    //Use Fermat primality test. 

    if (num % factor == 0) { 

     long long int testNum1 = rand() % 50 + 1; 
     long long int testNum2 = rand() % 50 + 1; 

     long long int test1 = (pow(testNum1, factor - 1) % factor); 
     long long int test2 = (pow(testNum2, factor - 1) % factor); 

     if (test1 == 1 && test2 == 1){ 

     cout << "The greatest prime factor is: " << factor; 
     break; 

     } 
    } 

} 

return 0; 
}

來源

2015-10-25 Tim Gillis

發佈有關構建問題/錯誤的問題時，請始終在問題主體中包含完整和未編輯的錯誤輸出。請編輯您的問題以包含它，並顯示錯誤在您的來源中的位置。 –

這是一個奇怪的因數分解嘗試。我不確定Fermat的素性檢驗是如何適用的：它可以以一定的概率告訴你一個給定的數字是否爲素數，如果它可能不是非素數，就不會告訴任何它的影響因素。你也用'pow'計算huuuge數字（不起作用），並迭代可能的很多數字（循環從600851475143/2下降到1）。 – WhiteViking

啊，也許你想實施費馬的因子分解方法呢？ https://en.wikipedia.org/wiki/Fermat%27s_factorization_method（這個傢伙知道一些關於數字的東西:-) – WhiteViking

看一看的documentation available爲std::pow：

如果任何參數已經整型，已經拋在表達

所以仔細pow(testNum, factor - 1)，參數testNum和factor - 1被提升爲雙精度浮點數，結果是雙精度浮點數。

您不能在雙精度型上使用operator %，因爲此運算符用於整型。向下轉換pow的結果可能會奏效，但您可能很容易遇到整數溢出問題。

編輯見this answer，關於如何做這種大整數計算的。

來源

2015-10-25 19:30:50

我被教導說算法是費馬素性測試，它測試一個數是否爲素數。這是否意味着我將不得不使用另一種方法來處理這個大整數？ –

檢查我在答案中包含的鏈接，它解釋瞭如何做這種大整數數學 –

@DanielStrul是正確的，你應該閱讀它的解釋，以瞭解如何做modular exponentiation。

但是，您並不需要使用費馬測試。認爲如果這個數字是合成的，它將至少有一個因子（不是最大的），低於sqrt(n)。

爲質數的密度大約是x/ln(x)你可以期望找到72000，素數更多或更少（公式是不確切），這是不是大了。

只需計算一百萬以下的所有素數（使用篩子）。並一個接一個地嘗試它們。當你找到一個因子時，請繼續分割n，直到用盡分解n的當前素數的所有冪。

當你用盡所有的素數在一百萬（或當n等於1），要麼n不是1，它是最大的主要因素，還是最大的主要因素是最後的黃金，你在上一步中找到。

來源

2015-10-26 12:44:56 fjardon

C++長長的費馬原始性測試的最大素因子

回答

相關問題