一般的な大きさの相似数を見つける

Question

私は任意の数xを持っています。私はxの平方根に近い（ish）の数値を計算したいと思います。私はそれらをすべて見つける必要はなく、因数はxです。私はただ一つの番号が必要です。

一定時間、好ましくは。

Answer 1

Euclidean algorithmでGCDを計算することは非常に効率的です。したがって、平方根に近い数値を試してみると、候補をすばやく見つけることができます。

一般的な素数pを見つけると、次回同じ素数でヒットすることができるので、後にpとなるため、一般的な要素を持つ数値の文字列を得ることはまずありません。