読者です 読者をやめる 読者になる 読者になる

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

Project Euler - Problem 10

Problem 10

200万以下の素数の和を求める問題.

use strict;
use warnings;
use bigint;

my $sum;
my @primes = (2);

for (1..2_000_000) {
    $sum += $_ if is_prime($_);
}

print "$sum\n";

sub is_prime {
    my $n = shift;

    if($n < 2) {
        return 0;
    } elsif($n == 2) {
        return 1;
    }

    for my $prime (sort {$a <=> $b} @primes) {
        last if $prime ** 2 > $n;

        return 0 if $n % $prime == 0;
    }

    push @primes, $n;
    return 1;
}

なんとか計算はできるんですが, めっちゃ遅いです... もう少しスマートな実装はないのかなぁ.
200万までの素数表を持っておく, という手法もアリといえばアリですが, こちらもまたスマートではないですし.