Perl による next_prime の実装

はじめに

アルゴリズムの勉強に、もっとプログラマ脳を鍛える数学パズル アルゴリズムが脳にしみ込む70問 を解いています。
『Q53 重さが素数の荷物を運ぶエレベーター』で素数の話が出てきました。
（Q53 は、素数＋二分探索の良問です）

Ruby の 素数クラス

Ruby では標準で素数を順に抽出するクラス Prime が用意されています。

ruby.rb

require 'prime'

primes = Prime.each(100).to_a # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

上記のコーディングで、100以下の素数の配列が生成されます。
Perl では標準モジュールが用意されていないので、Rubyに乗り換えましょう自作する必要があります。

Perl による実装

primes.pl

my @primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97);
sub prime {
  my $n = shift;
  return $primes[$n] if defined $primes[$n];
  my $newprime = $primes[-1] + 2;
  while ($n + 1 > @primes) {
    my $f = 1;
    for my $i (@primes) {
      if ($newprime % $i == 0) {
        $f = 0;
        last;
      } elsif ($i ** 2 > $newprime) {
        last;
      }
    }
    if ($f == 1) {
      $primes[@primes] = $newprime;
    }
    $newprime += 2;
  }
  $primes[$n];
}
sub next_prime {
  my $n = shift;
  my $i = 0;
  while (1) {
    if ($primes[$i] == 0) {
      prime(scalar @primes);
      last if $n < $primes[$i];
    }
    $i++;
  }
  $primes[$i];
}

perl.pl

print prime(80);       # => 419　81番目の素数
print next_prime(743); # => 751

怠慢なので 予め100以下の素数を用意しておきます。
それ以降の素数は必要に応じ、随時追加する仕様にしました。

まとめ

• Ruby は prime や permutation や gcd 等が標準で用意されてます
• 今回は Perl で next_prime を実装しました
• 数学パズルはためになります

参照したサイト
class Prime
初学者によるプログラミングMemo　#22 素因数分解