2005年6月10日金曜日

1は素数ではない(その2)

以前は素因数分解で説明.>くろべえ : 1は素数ではない.

理由のもう一つ.
素数を調べるエラトステネスのふるい.
その手順はまず自然数を並べる.
1,2,3,4,5,6,7,8,9,10,
11,12,13,14,15,16,17,18,19,20,


並べた自然数について、次の手順を実行する.
1は素数ではない.
1の次は2は素数で,その倍数を消す.
1,2,3,4,5,6,7,8,9,10,
11,12,13,14,15,16,17,18,19,20,
2の次の3は素数で,その倍数を消す.
1,2,3,4,5,6,7,8,9,10,
11,12,13,14,15,16,17,18,19,20,
・・・・・・
で残った 2,3,5,7,11,13,17,が素数である.

という具合に,素数が見つかったら,その倍数をすべて消して,次々に素数を突き止める手順を「エラトステネスのふるい」という.

ここでスタート時,「1は素数」にしてしまうとその倍数を消さなければならない.で,
 「1の倍数を消す」
をやれば,2以上のすべての自然数が消されて「素数は1だけである.」で終了.

だから,1を素数に含めないともいえる.

3 件のコメント:

  1. << ”NumberTheory`NumberTheoryFunctions`”
    Prime[100000000]
    NextPrime[Prime[100000000]]
    Timing[Table[NextPrime[Prime[100000000 + m]],
    {m, 0, 18}]]

    Table[n, {n, 2038074743, 2038074751}]

    Timing[FactorInteger[%]]

    (* 100000000番目の素数2038074743,から次の素数2038074751 の 狭間の
      非素数達で

    イチバンはやく篩いにかけられる合成数は? 

    イチバン遅く篩いにかけられる合成数は??*)

    (*リストラ の検索結果 約 974,000 件 の 話ではありませぬ*)

    http://mathworld.wolfram.com/SieveofEratosthenes.html

    返信削除
  2. イチバンはやく篩いにかけられる合成数は2038074744=2*1019037372
    イチバン遅く篩いにかけられる合成数は2038074749=2557*797057
    でしょうか.

    返信削除
  3. はい と 瞬時に mathematica;

    {0. Second, {{{2038074743, 1}}, {{2, 3}, {3, 1}, {991, 1}, {85691, 1}}, {{5,
    1}, {7, 1}, {311, 1}, {187237, 1}}, {{2, 1}, {137, 1}, {149,
    1}, {49921, 1}}, {{3, 1}, {679358249, 1}}, {{2, 2}, {19,
    1}, {26816773, 1}}, {{2557, 1}, {797057, 1}}, {{2, 1}, {3, 3}, {5,
    3}, {17, 1}, {17761, 1}}, {{2038074751, 1}}}}


    Sieve 免れせめて遅く

    返信削除

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.