Problem 7

10001個目の素数を求めろという問題。調べたら素数に関するMath::Prime::XSというモジュールが
あってその中の is_primeという関数を使ってみたんだけど 10分ぐらい待っても答えがでません
でしたね。一応 core2duo 1.8GHzぐらいなんですけど。ある数以下の素数で割り切れなければ
その数は素数になるんですね。知らなかったけど、よくよく考えるとそうですね。
これだと 9秒ぐらいで答えが出ました。

参考
http://blog.livedoor.jp/dankogai/archives/50534089.html

#!/usr/bin/perl
use strict;
use warnings;

my @primes;
my $nth = 10001;
print "$nth prime is ", p7($nth), "\n"; # 104743

sub p7
{
  my ($nth) = @_;

  my $prime_number = 1;
  my $num = 3;

  while(1){
    $prime_number++ if is_prime($num);
    return $num     if $prime_number == $nth;
    $num += 2;
  }
}

sub is_prime
{
  my ($num) = @_;

  for my $i (@primes){
    return 0 if $num % $i == 0;
  }

  push @primes, $num;
  return 1;
}