0
私は任意の数x
を持っています。私はx
の平方根に近い(ish)の数値を計算したいと思います。私はそれらをすべて見つける必要はなく、因数はx
です。私はただ一つの番号が必要です。一般的な大きさの相似数を見つける
一定時間、好ましくは。
私は任意の数x
を持っています。私はx
の平方根に近い(ish)の数値を計算したいと思います。私はそれらをすべて見つける必要はなく、因数はx
です。私はただ一つの番号が必要です。一般的な大きさの相似数を見つける
一定時間、好ましくは。
Euclidean algorithmでGCDを計算することは非常に効率的です。したがって、平方根に近い数値を試してみると、候補をすばやく見つけることができます。
一般的な素数pを見つけると、次回同じ素数でヒットすることができるので、後にpとなるため、一般的な要素を持つ数値の文字列を得ることはまずありません。
xを分割しない素数を選んで、ルートxに近づける(ish)? – dmuir
コンピューティング素数は高価です... – Scott
...それらがたくさんあります... "特別な"素数でない限り。メルセンヌ素数はあまりにも希薄で、xより小さいlog(x)のようなものがあります。しかし、xより小さい根(x)が存在する素数のクラスがあれば、それはきれいに分布し、閉じた形を見つけることが理想的です。私はこのような解決策を望んでいました...ユークリッドのalgoはlog(x)であり、任意の数のcoprimesの分布についてはわかりませんが、素数の分布は素数に近いroot(x)を見つけることが期待されています>> log(x)... log(x)^ 2だと思います。 – Scott