Math Battle [ 0188: 2019年の素数日は？ ]

[ 0188: 2019年の素数日は？ ]

[ 丘品花志先生の出題 ] -- 最新版は 0340

皆さん、幾何学や最大最小問題には飽きたでしょうから、素数の問題を出題します。

素数日 (prime date) とは、 yyyy 年 mm 月 dd 日を yyyymmdd という 8 桁の整数であらわしたときそれが素数になる日付のことです。

たとえば今年の元旦の yyyymmdd 表記は 20190101 ですね。これは 17*137*8669 という具合に素因数分解できますから素数日ではありません。

2019 年の素数日を全部リストしてください。 (ヒント: 19 日あるはず)

なお、sqrt(20191231) は約 4493.5 ですから、そのあたりまでの素数をあらかじめ用意しておけばいいです。

しかし、簡単にはゆきませんからまず sqrt(4493.5) = 約 67 までの範囲の素数を見つけます。これだったら手計算でもできるはず。これをグループ P1 と呼びましょう。 1000 までの範囲だったら下の画像の一覧を参考にしてください。

68〜4493 の範囲の自然数それぞれに対して P1 の中の素数で割り切れない数があれば、それは新たに見つかった素数です。

こうして 4493 までの素数が出そろいますから、これをグループ P2 (P1を含む) とします。

20190101〜20191231 の範囲の日付数それぞれに対して P2 の中の素数で割り切れない数があれば、それらが素数日です。

[ 広世正憲君の回答 ]

2019 年の素数日は:

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

の 19 個ですね。間違っていませんか？
今年は大晦日が素数日です。

Perl スクリプトを作って求めました。結果が正しければ Perl ソースコードを皆さんにご紹介します。 P1 や P2 は配列 (array) として定義しました。

[ 浅見多絵さんのコメント ]

カレンダーのデザインも手がけている私がやろうと思っていたら正憲君に先を越されちゃった。やることが早いわね。三奈ちゃんの「早々蛮蛮」の影響かしら。

[ 広世正憲君のコメント ]

方針通り書いてみました。Perl ソースコードは以下のとおりです。

#!/usr/local/bin/perl

# 素数集合(どんどん追加)

@p = (2,3,5,7,11,13,17,19,23,29,31,37,
　41,43,47,53,59,61,67);

# 68〜4493の範囲の素数を見つけしだい@pに追加する。

for ($n=68; $n<=4493; $n++) {
　for ($k=0; $k<($num_p=@p); $k++) {
　　goto skip_1 if (($n % $p[$k]) == 0);
　}
# printf("新しい素数: %d\n", $n);
　push @p, $n;
　next;
skip_1: ; # 既知の素数で割り切れた。素数ではない。
# printf("(%d) は素数ではない。\n", $n);
}

$num_p = @p;
printf("2〜4493 の範囲の素数個数: %d\n", $num_p);

# 2019 年での yyyymmdd それぞれに対して:
# @pの中の素数で割り切れない数があれば素数日。

@m_days = # 西向く侍 (2,4,6,9,11) は小なり。
　(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);

$n = 0; # 得られた素数日の順番をあらわす。

for ($mm=1; $mm<=12; $mm++) {
　for ($dd=1; $dd<=$m_days[$mm-1]; $dd++) {
　　$date = 20190000 + $mm * 100 + $dd;
　　for ($k=0; $k<$num_p; $k++) {
　　　goto skip_2 if ($date % $p[$k] == 0);
　　}
　　printf("*** 素数日(%02d) %8d\n", ++$n, $date);
　　next;
skip_2: ; # 素数日ではない。
　}
}

これでいいですか？

実行結果は:


2〜4493の範囲の素数個数: 610
*** 素数日(01) 20190221
*** 素数日(02) 20190227
*** 素数日(03) 20190301
*** 素数日(04) 20190319
*** 素数日(05) 20190323
*** 素数日(06) 20190421
*** 素数日(07) 20190523
*** 素数日(08) 20190529
*** 素数日(09) 20190601
*** 素数日(10) 20190613
*** 素数日(11) 20190719
*** 素数日(12) 20190811
*** 素数日(13) 20190823
*** 素数日(14) 20190913
*** 素数日(15) 20191009
*** 素数日(16) 20191027
*** 素数日(17) 20191109
*** 素数日(18) 20191117
*** 素数日(19) 20191231

[ 湯会老人のコメント ]

正憲君、いいと思います。うまくコメントを入れていますので、わかりやすいコードです。

[ 0201: 次の記事 ]

[ 0200: MITの超簡単入試問題 ]

[ 0199: 残っている課題 ]

[ 0198: サーバー契約の切り替え ]

[ 0197: 二つの正方形の重なり部分 ]

[ 0196: 本田三角形の重ね描き ]

[ 0195: 平衡二分木とハッシュ ]

[ 0194: カッコーハッシュとは？ ]

[ 0193: 1を998で割ると ]

[ 0192: pentominoは何種類？ ]