2019年の素数日（エラトステネスのふるい）

プログラミング

こんにちは。2018年最後の投稿になります。2018年を総括してもよいのですが、あまり気持ちが向いていません。

このサイトについての話では、年始にサーバへのインストールしていましたが、８月中旬まで放置していて約4か月だけの運用でした。

情報科については、学習指導要領が公示されたり、大学入試関係でも動きがあったりしました。１つ１つが未来に向かって進んでいるので、ちゃんと書いた方がいいように思っています。

そこで、2019年の話にします。といっても私が書く未来予測なんて与太話以上にはなりません。そこで、唐突ですが2019年の素数日について書くことにします。（書く時間が短そうという裏の理由もありますが・・・）

素数日とは

素数について復習しておきます。「１より大きい自然数で、約数が１とその自然数自身だけの数」です。平たく言うと「自然数で正の約数の個数が２個のもの」です。

次に素数日について判定します。例えばこの投稿の公開日2018年12月30日ですが、これを20181230としてその数が素数になっていれば素数日です。残念ながら20181230は、1でも自身でもない2を約数にもつため（2で割り切れるため）、素数日ではありません。

エラトステネスのふるい

素数判定法はいくつもありますが、かなり単純な「エラトステネスのふるい」を今回は使います。（プログラムのストックがあるから・・・）このアルゴリズムは比較的簡単で、for文の練習問題的な存在です。簡単に説明します。

Ｓｔｅｐ１　チェック表を作る（１には素数でない目印をつける）

Ｓｔｅｐ２　チェックされていない最小の数は素数で、その倍数に素数でない印をつける

Ｓｔｅｐ３　チェックされていない最小の数を２乗して、最大数を超えるまで、Ｓｔｅｐ２を繰り返す

（Ｓｔｅｐ２－１　チェックされていない最小の数２は素数で、２の倍数に×をつける）

（Ｓｔｅｐ２－２　チェックされていない最小の数３は素数で、３の倍数に×をつける）

（Ｓｔｅｐ２－３　チェックされていない最小の数５は素数で、５の倍数に×をつける）

（Ｓｔｅｐ３－３　次のチェックされていない最小の数７を２乗すると、最大数３６を超えるので、以上で繰り返しは終了）

Ｓｔｅｐ４　この時点で×がついていない数が素数

エラトステネスのふるいでの工夫

繰り返しの終了条件

上のＳｔｅｐ３で、「チェックされていない最小の数を２乗して、最大数を超えるまで」繰り返しています。×が付いていない数は、上の表では7～３１まで8個も残っています。その理由を確認します。

素数でない数として３６を例に考えてみます。３６を２つの数の積で表すと

１×３６、２×１８、３×１２、４×９、６×６、９×４、１２×３、１８×２、３６×１

があります。これより６×６の前後で対称になっていることがわかります。チェックされていない最小の数を２乗して最大数を超えたら、新たに×が付くことはないため、計算時間がかかるだけで無駄な計算です。

素数になりうる数

偶数は２の倍数です。自然数で最初の偶数である２は素数ですが、それ以外の偶数は素数でないことはすぐにわかります。また、偶数は他の数の倍数よりも圧倒的に多いため、チェックするにも時間がかかります。偶数のチェックをしなければ時間短縮につながります。

さらに３の倍数も数が多いので工夫してみましょう。２と３の最小公倍数である６の倍数に着目して表を再確認してみます。

６で割ったときに、余りが０・２・４のものは偶数です。また、余りが０・３のものは３の倍数です。これらは素数ではありません。そうすると、素数になりうる候補は、６で割ったときの余りが１・５のいずれかに限られます。これを用いると、さらに時間短縮できます。

エラトステネスのふるいのプログラム

今回はＪａｖａのプログラムを掲載します。出力は２０１９年の素数日だけが表示されるようにしています。なお、上で素数になりうる数は６で割って余りが１・５だけと書いていますが、紹介するプログラムでは偶数だけを除外したものになっています。

package prime_number;

public class PrimeNumber {

  public static void main(String[] args) {

    int N = 20191232;

    boolean[] prime = new boolean[N + 1];

    for (int i = 1; i <= N; i++) {
      prime[i] = true;
    }
    prime[1] = false;

    for (int i = 3; i <= Math.sqrt(N); i+=2) {
      if (!prime[i])
        continue;
      for (int j = 3; i * j <= N; j+=2) {
        prime[i * j] = false;
      }
    }

    int count=1;
    int[] days = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    
    for (int m = 1; m <= 12; m++) {
      for(int d = 1; d<=days[m-1]; d+=2) {
        int i = 20190000 + m*100 + d;
        if (prime[i]) {
          System.out.println(i);
          count++;
        }
      }
    }
    System.out.println(count);
  }
}

この出力は次の通りです。

20190221
20190227
20190301
20190319
20190323
20190421
20190523
20190529
20190601
20190613
20190719
20190811
20190823
20190913
20191009
20191027
20191109
20191117
20191231
20

2019年の最初の素数日は2月21日で、大晦日も素数日、年間通して20日あります。ちなみに2018年最後の素数日は2018年12月29日で、この記事の公開前日でした。

さらについでの話ですが、今上天皇が天皇としての最後の誕生日2018年12月23日、皇太子殿下が天皇に即位して最初に迎える誕生日2020年2月23日の両方とも素数日です。

素数にまつわるアルゴリズムはたくさんあるので、そのうちきっと取り上げると思います。それでは、よいお年をお迎えください。

[mathjax]

Posted by 春日井 優