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; }