Math Battle [ 0340: 素数日プログラム ]

[ 0340: 素数日プログラム ]

[ 三方万理先生 (algorithm teacher) の出題 ]

1900 年から 2045 年までの間の指定された年に対して、
その年に存在する素数日 (prime dates) を全て列挙するプログラムを書いてください。
実行結果例も添えて。

なお素数日とは年月日を yyyymmdd 形式の 8 桁の整数で表記したとき、
その数が素数であるような日付のことでしたね。
0188 で一度やりましたが、
「うるう年判定」もちゃんといれてください。

[ 井伊莞爾君の回答 ]

多絵さんの素数判定も参考にして書いてみました。
$year_min と $year_max を変えれば対応できる年の範囲は自由に拡張できます。

#!/usr/local/bin/perl

$year_min = 1900;
$year_max = 2045;
@primes = ();
$n_primes = 0;

my $year = accept_year();
prepare_primes($year);
find_prime_dates($year);

sub accept_year() {
　my $line, $year = 0;

　while ($year < $year_min || $year > $year_max) {
　　printf("素数日を探す年 (%d〜%d) を入力してください。\n",
　　　$year_min, $year_max);
　　$line = <STDIN>;
　　$year = $1 if ($line =~ /^\s*(\d{4})/);
　}
　return $year;
}
sub prepare_primes($year) {
　my ($year) = @_;
　my $i;
　my $max = sqrt($year * 10000 + 1231);

　for ($i=2; $i<=$max; $i++) {
　　next unless is_prime($i);
　　$primes[$n_primes++] = $i;
　}
}
sub is_prime {
　my $n = shift;
　my $j;

　return 1 if ($n == 2); # true

　for ($j=0; $j<$n_primes; $j++) {
　　last if ($n < $primes[$j]**2);
　　if (($n % $primes[$j]) == 0) {
　　　return 0; # false
　　}
　}
　return 1; #true
}
sub find_prime_dates($year) {
　my ($year) = @_;
　my @m_days = ();
　my $mm, $dd, $date;
　my $prime_dates = ();
　my $n_prime_dates = 0;
　my $j;

　@m_days
　　= (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);
　if ($year % 100 == 0) {
　　$m_days[1] = 29 if ($year % 400 == 0);
　} else {
　　$m_days[1] = 29 if ($year % 4 == 0);
　}

　for ($mm=1; $mm<=12; $mm++) {
　　for ($dd=1; $dd<=$m_days[$mm-1]; $dd++) {
　　　$date = $year * 10000 + $mm * 100 + $dd;
　　　if (is_prime($date)) {
　　　　$prime_dates[$n_prime_dates++]
　　　　　= sprintf("%4d/%02d/%02d", $year, $mm, $dd);
　　　}
　　}
　}
　printf("%d年には次のように %d個の素数日があります。\n",
　　$year, $n_prime_dates);
　for ($j=0; $j<$n_prime_dates; $j++) {
　　printf("%s\n", $prime_dates[$j]);
　}
}

2020 年を指定して実行しました。


$ perl prime_dates.pl
素数日を探す年 (1900〜2045) を入力してください。
2020
2020年には次のように 25個の素数日があります。
2020/01/09
2020/01/11
2020/01/21
2020/01/23
2020/02/23
2020/03/09
2020/04/29
2020/05/11
2020/05/29
2020/06/13
2020/06/19
2020/07/03
2020/07/11
2020/07/21
2020/07/23
2020/07/29
2020/08/01
2020/08/13
2020/09/03
2020/10/21
2020/10/29
2020/11/01
2020/11/13
2020/12/27
2020/12/31

[ 三方万理先生のコメント ]

莞爾君、ありがとうございます。
これでいいみたいですね。
ほかのかたから何かコメントはありますか。

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

先を越されてしまいました。

僕が最初に 0188 に取り組んだときとくらべて随分レベルアップしましたね。
うまくサブルーチン分けができていると思います。
指定された年にあわせて除数とする素数集合を用意する際と、
個々の素数日判定の両方に同じ is_prime 関数を使っているところなど。
当然といえば当然ですが。

[ 0341: 次の記事 ]

[ 0340: 素数日プログラム ]

[ 0339: emirp 探し ]

[ 0338: 0331の解きなおし ]

[ 0337: ubuntu 20.04 へ upgrade ]

[ 0336: πの近似計算 ]

[ 0335: 0253 の振り返り ]