大數字怎麼樣？（素性測試）

-2

這是一個'真正'的任務，可以寫在任何語言（例如C/C++）大數字怎麼樣？（素性測試）

所以，我的任務是'生成'隨機數的長度超過50位數字= 200）？

然後，我必須在素數測試中檢查這個數字。

那麼，這個任務是「真實的」，它將消耗多少時間/資源？

另一種方法是生成特殊的類質Mersenn號碼或其它號碼（可以使用類？）

來源

2012-02-09 gaussblurinc

你是什麼意思「真實」？你問我們這是否是功課嗎？你應該知道...... – PlasmaHH 2012-02-09 11:31:45

證明一個數字是素數是難以置信的困難（好，微不足道但非常慢）。 GMP（GNU多精度算術庫）有一個可能的主要功能，可以運行測試（你可以告訴它有多少iirc）來告訴你一個數字是否可能是主要的。 http://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions 使用起來有點費勁，因爲它確實是C語言，但是您可以從C++中使用它。 – BoBTFish 2012-02-09 11:35:04

'真實' - 任務，只需要一臺電腦，耗時不到一個小時。個人使用，是的。 – gaussblurinc 2012-02-09 12:02:54

有一些有效的概率算法用於素性測試，如Miller-Rabin，通常用於這些目的。

選擇一個隨機數並使用隨機算法測試素數是有效的，因爲素數密度保證您對於n位數字需要選擇n個數字進行測試。

來源

2012-02-09 11:31:57 Krystian

使用Miller-Rabin primality test。此外，由於50位數字不適合原生數據類型，因此您需要一個大數字小數庫。

這是一個Javascript implementation of Miller-Rabin，它做了50次迭代Miller-Rabin。它在幾秒鐘內完成。

來源

2012-02-09 11:30:40 Sjoerd

大數字怎麼樣？ （素性測試）

回答

相關問題

大數字怎麼樣？（素性測試）