|
[ 0339: emirp 探し ]
[ 星楊令さんの出題 ]
数学には、いろいろ遊びの分野があります。
エマープ（emirp）とは
素数でありかつ逆から数字を読むと元の数とは異なる素数 （prime）
になる自然数のことです。Prime を逆から読むと emirp ですね。
あくまでも十進表記で成り立つことですが。
例えば 1097 は素数で、かつ 7901 も素数であるため
この 2つの数はエマープです。エマープと回文数になっている素数を合わせたもの
（つまり、逆から読んでも素数である素数全体）
を「回文素数 (palindromic prime)」ということもあります。
なお、エマープは無限に存在するかどうかはまだ数学で確かめられてはいませんが、
これまでに知られている最も大きなエマープは
2007 年 10 月に Jens Kruse Andersen が発見した
1010006 + 941992101 * 104999 + 1 です。
どうやって探したのでしょうね？
さて、問題です。
10000 までの範囲で emirp を全部探すプログラムを作ってください。
実行結果も添えて。
[ 浅見多絵さんの回答 ]
楊令さん、できました。次のような Perl プログラムです。
（一部訂正: もとの数と逆順の数が同じ場合を排除)
#!/usr/local/bin/perl
@primes = ();
$n_primes = 0;
@emirps = ();
$n_emirps = 0;
for ($n=2; $n<=10000; $n++) {
my $n2;
next unless is_prime($n);
$primes[$n_primes++] = $n;
$n2 = reverse_number($n);
if ($n != $n2 && is_prime($n2)) {
$emirps[$n_emirps++] = $n;
}
}
printf("Found %d emirps in %d primes.\n",
$n_emirps, $n_primes);
for ($j=0; $j<$n_emirps; $j++) {
printf("%4d | %4d\n",
$emirps[$j], reverse_number(@emirps[$j]));
}
sub reverse_number($n) {
my ($n) = @_;
my $str, @digits, $n2;
$str = sprintf("%d", $n);
@digits = split(//, $str);
@digits = reverse @digits;
$str = join('', @digits);
$n2 = $str + 0; # 数値に変換する。
return($n2);
}
sub is_prime($n) {
my ($n) = @_;
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
}
|
-
素数が何もない状態から始めます。
これまでに見つかった素数で割った剰余 (%) がゼロであれば素数ではありません。
このチェックは対象の数の平方根あたりまでの素数で
おこないます。
チェックをパスすれば素数です。
-
2 に対してはそれまでに見つかった素数がないため、そのまま最初の素数になります。
3 は 3 < 22 なのでそのまま素数チェックをバスします。
4 は 4 = 22 なので 2 で割った剰余のチェックをし、
ゼロなので素数でないとしてはじかれます。
以下同様。
-
見つかった素数に対しては
数字を逆順にした数と同じかどうかをチェックします。
同じ (対称) であれば emirp ではありません。
同じでなければ逆順の数に対して素数かどうかのチェックをおこないます。
これも素数であれば emirp です。
実行結果 (一部) は以下のとおりでした。
Found 240 emirps in 1229 primes.
13 | 31
17 | 71
31 | 13
37 | 73
71 | 17
73 | 37
79 | 97
97 | 79
107 | 701
113 | 311
149 | 941
157 | 751
167 | 761
179 | 971
199 | 991
311 | 113
337 | 733
347 | 743
359 | 953
389 | 983
701 | 107
709 | 907
.....
9721 | 1279
9749 | 9479
9769 | 9679
9781 | 1879
9787 | 7879
9791 | 1979
9803 | 3089
9833 | 3389
9857 | 7589
9871 | 1789
9883 | 3889
9923 | 3299
9931 | 1399
9941 | 1499
9967 | 7699
[ 星楊令さんのコメント ]
多絵さん、ありがとうございます。
プログラムは明快に書かれており、説明もわかりやすいです。
これでいいと思います。
[ 広世正憲君のコメント ]
なるほど、うまいやりかたですね。
Singularity が起きるといわれる 2045 年までの任意の年の
素数日
を求める場合は
sqrt(20451231) が 約 4522.3 ですから
4522 までの範囲の素数をあらかじめ用意しておけばいいですね。
614 個見つかりましたが、
これを配列としてソースコードに入れると行数を食いますから
そのつど求めてもあっという間に準備できます。
その年がうるう年かどうかは
「西向く侍」を参考にします。
|