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

初代Masteries

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

Project Euler - Problem 27

Problem 27

プログラミングのセンスもさることながら, 数学的センスも全っ然ないなあ... とヘコむ今日このごろです.

問題としては, 「連続するnの値から素数を生成したとき最長の長さとなる二次式を求めよ」という感じ.
簡単に言えば, n^2+an+bについて, nを0から1ずつ増やした時に, 答えが素数でなくなるのはいつかを求める問題です.

use strict;
use warnings;
use bigint;
use Memoize;

memoize('is_prime');

my @odd_primes = grep { is_prime($_) } (3..999);
my @odd = grep { $_ % 2 == 1 } (-999..999);

my ($max_length, $max_a, $max_b) = (0, 0, 0);

my $pattern = 0;

for my $coefficient_b (reverse @odd_primes) {
    next if $max_length >= $coefficient_b - 1;
    for my $coefficient_a (grep { $_ > -1 * $coefficient_b } @odd) {
        my $n = 0;

        while (is_prime($n ** 2 + $coefficient_a * $n + $coefficient_b)) {
            $n++;
        }
        if ($max_length < $n) {
            $max_length = $n;
            $max_a = $coefficient_a;
            $max_b = $coefficient_b;
        }
    }
}

print "$max_length: a = $max_a, b = $max_b, a * b = " . ($max_a * $max_b) . "\n";

sub is_prime {
    my $n = shift;

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

    if ($n % 2 == 0) {
        return 0;
    }

    for (my $i = 3; $i * $i <= $n; $i += 2) {
        if ($n % $i == 0) {
            return 0;
        }
    }
    return 1;
}

いろいろ頑張って条件を減らしたのですが, 結構時間がかかってしまいますね...