-2

私の先生は私にこれをくれました：

n<=10^6;

n 整数の配列 :ai..an(ai<=10^9);

すべての素数を見つけます。

彼はエラトステネスのふるいについて何か言いました、そして私はそれについて読みました、また車輪の因数分解も読みましたが、プログラム（fpc）を1秒で実行する方法をまだ理解できませんでした.?? 私はそれが不可能であることを知っていますが、それでもあなたの意見を知りたい. ホイールの因数分解では、2*3 の円は 25 を素数として扱います。素数として誤って処理されたホイールの最初の数を見つける方法があるかどうか尋ねたいと思います。例: 2*3*5 円 、素数として扱われる最初の合成数を見つける方法?? 助けてください..そして悪い英語でごめんなさい。

4

2 に答える 2

1

エラトステネスの適切なふるいは、約 1 秒で 10 億未満の素数を見つける必要があります。それが可能だ。コードを見せていただければ、何が問題なのかを見つけるお手伝いをさせていただきます。

2、3、5 ホイールでマークされていない最小の合成は 49 です: ホイールのメンバーではない次に大きい素数は 7 で、7 * 7 = 49 です。

于 2014-10-08T12:40:46.247 に答える
0

私は今それを行いましたが、数ミリ秒で最大 1000000 の素数を見つけていますが、それらすべての数値は表示されていません。n + 1 bool の配列 a を宣言します (ゼロベースの場合)。最初は 0 番目と 1 番目の要素が false で、それ以外はすべて true です (false は素数ではありません)。アルゴリズムは次のようになります。

i = 2;
while i * i <= n
    if a[i] == true
        j = i * i;
        while j < n
            a[j] = false;
            j = j + i;
    i = i + 1;

ループでは、条件は i * i <= n です。これは、i * i から検索を開始するため (他の素数の 1 つによって既に見つかった素数よりも小さい素数)、i の平方根は n より大きくてはなりません。n までの素数の倍数であるすべての数を削除します。時間計算量は O(n log log n) です。素数を表示したい場合は、配列内の値が真であるインデックスを表示します。

因数分解は、たとえば、0 から n までのすべての半素数 (2 つの素数の積) を見つけたい場合に便利です。次に、0 から n/2 までのすべての最小素約数を見つけ、各数値に素約数があるかどうか、および素約数で割った数値にゼロ約数があるかどうかを確認します。もしそうなら、それは半素数です。私のプログラムは、最初にすべての素数を見つけてから乗算し、結果を配列に保存するよりも 8 倍速く計算するように書きました。

于 2014-10-10T22:09:10.333 に答える