找到一個大小的互質數

我有一個任意數x。我想計算一個與x相近的數字，它與x的平方根很接近（ish）。我不需要全部找到它們，並且因子x是昂貴的。我只需要一個號碼。找到一個大小的互質數

恆定時間，最好。

2017-09-15 Scott

選擇一個素數，它不會將x關閉（ish）到根x？ – dmuir

計算素數是昂貴的... – Scott

...有很多他們......除非他們是「特殊」素數。梅森素數太稀少，有像log（x）那樣的東西比x小。然而，如果有一類素數的根（x）小於x，很好地分佈，封閉形式來尋找，那將是理想的。我希望得到這樣的解決方案...歐幾里德算法是log（x），我不知道任意數的副本的分佈情況，但是素數的分佈是這樣的，以至於在根（x）附近找到一個素數在>> log（x）... log（x）^ 2我想。 – Scott

您可以用Euclidean algorithm相當有效地計算GCD，所以如果您只是嘗試接近平方根的數字，您應該很快找到候選人。

你不可能得到一串有共同因素的數字，因爲如果你找到一個普通的素數p，下一次你可以用相同的素數命中p後。

來源

2017-09-15 21:20:28

找到一個大小的互質數

回答

相關問題