古い記事
ランダムジャンプ
新しい記事
ハッシュのサイズを決める際に、
ある数に近い素数が欲しいと思うことがあったりします。
例えば「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.