-4

次の問題を考えてみましょう。「与えられた整数の範囲にいくつの数があり、そこから数字の合計とその平方の合計の両方が素数になりますか？」

私はコードレビューを見回していましたが、ここで興味深い質問を見つけて解決しようとしました。

したがってprime numbers、通常の方法でチェックできます。つまり、からへのforループを使用して、除算性をチェックできます。2i

面白いのはここです。BlueRaja - Danny Pflughoeftトリックを提案します：「素数性をテストしている数の平方根までふるいにかける必要があるだけなので、3から*までふるいをかけるだけで済みますsqrt(⌈log10(B)⌉*81)」。

の実装について質問がありSieve of Eratosthenesます。
ふるいにかける数字が入ったの大きさはboolean array？誰かがコードやヒントを書くことができますか？

4

1 に答える 1

1

Javaを使用したエラトステネスのふるいの実装例を次に示します。link。

質問の2番目の部分については、次のリンクを参照してください。

「n桁の数の2乗の最大合計はn*9 * 9 = n *81です。数Bの桁数は⌈log10（B）⌉です。原始性をテストしている数値の平方根の場合、ふるいを3からsqrt（⌈log10（B）⌉* 81）まで実行するだけで済みます。B= 10億の場合でも、これはふるいにかける必要のある最大値を意味します。 toは28です。」

于 2012-04-15T18:48:58.860 に答える