Project Euler with Ruby on WSL [Problem 27]

Project Euler Programming ruby

さてはて

連休明けて全然すすめてないので少しだけ

問題

Quadratic primes

Euler discovered the remarkable quadratic formula:

n^2+n+41

It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤39. However, when n=40, 40^2+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41,412+41+41 is clearly divisible by 41.

The incredible formula n^2−79n+1601 was discovered, which produces 80 primes for the consecutive values 0≤n≤79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n^2+an+b, where |a|<1000 and |b|≤1000

where |n| is the modulus/absolute value of n e.g. |11|=11 and |−4|=4 Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n=0.

私訳

二次式による素数

オイラーの発見した n^2+n+41 は 0≤n≤39 で素数となる。

さらに驚くべき式 n^2−79n+1601 は 0≤n≤79 の 80 個が素数である。 この式の係数の積は -79 x 1601 = −126479 である。

二次式 n^2+an+b について |a|<1000 かつ |b|≤1000 のとき、 0≤n で最も多くの素数を生成するときの積 ab を求めよ

解答方針

えーめんどいので力づくで解く。 明らかに素数を生成しない a = b = 0 とかも除外しない。 それでも (2999+1)(2*1000+1) ≒ 400万ループくらいで解けるはずだ

あと、エラトステネスの篩を自前実装するのが面倒になったので prime 使っちゃう。

require 'prime'
``