Perlで素数判定と近隣素数の探索
2006-08-15-2
[Programming][Algorithm]
ハッシュのサイズを決める際に、
ある数に近い素数が欲しいと思うことがあったりします。
例えば「1000000に近い素数が欲しい!」など。
ということでPerl版の素数判定&近隣素数探索プログラムです。
素数判定は下記を参考にしました。
- 素数判定 - Wikipedia
http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A
以下、ソースと実行例。
ソース(prime.pl):
実行例:
ある数に近い素数が欲しいと思うことがあったりします。
例えば「1000000に近い素数が欲しい!」など。
ということでPerl版の素数判定&近隣素数探索プログラムです。
素数判定は下記を参考にしました。
- 素数判定 - Wikipedia
http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A
以下、ソースと実行例。
ソース(prime.pl):
#!/usr/bin/perl use strict; use warnings; my $n = shift @ARGV; my $prime = is_prime($n); if ($prime) { print "$n is a prime number.\n"; } else { print "$n is NOT a prime number.\n"; } ### 近隣の素数 for (my $i = $n-1; $i > 0; $i--) { if (is_prime($i)) { print "$i is the nearest prime number lower than $n.\n"; last; } } for (my $i = $n+1; ; $i++) { if (is_prime($i)) { print "$i is the nearest prime number higher than $n.\n"; last; } } ### 素数判定 sub is_prime { my $n = shift; return 0 if ($n < 2); return 1 if ($n == 2); return 0 if ($n % 2 == 0); for (my $i = 3; $i * $i <= $n; $i += 2) { return 0 if ($n % $i == 0); } return 1; }
実行例:
% ./prime.pl 1234567891 1234567891 is a prime number. 1234567811 is the nearest prime number lower than 1234567891. 1234567907 is the nearest prime number higher than 1234567891. % ./prime.pl 123456789 123456789 is NOT a prime number. 123456761 is the nearest prime number lower than 123456789. 123456791 is the nearest prime number higher than 123456789. % ./prime.pl 1 1 is NOT a prime number. 2 is the nearest prime number higher than 1.