책 이야기

Euler discovered the remarkable quadratic formula:

n²+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²+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41,41²+41+41 is clearly divisible by 41.

The incredible formula n²−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²+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²+n+41

이 공식은 0≤n≤39 범위에서 연속된 40개의 소수를 만들어내는 것으로 밝혀졌다. 그러나, n=40일 때, 40²+40+41=40(40+1)+41은 41로 나눠지고, 당연하게도 n=41일 때,41²+41+41은 분명하게 41로 나눠진다.

믿을수 없는 공식 n²−79n+1601은 0≤n≤79에서 80개의 연속된 소수를 만드는 것으로 밝혀졌다. 계수인 -79와 1601의 곱은 −126479이다.

|a|<1000이고, |b|≤1000인 다음 형태의 이차방정식 n²+an+b을 생각해 보자.
|n|은 n의 계수값/절대값이다. 즉, |11|=11이고, |−4|=4이다.

n=0으로 시작해 최대 길이의 연속된 소수를 만들어 내는 계수 a와 b의 곱을 구하라.

--------------------------------------------------------------------------

아직 26번을 해결하는 아이디어가 떠오르지 않아 생략하고 진행한다.

문제는 읽기 까다로운 편인데, 반복문을 이용한 단순한 접근으로 해결 가능하다. a는 -999에서 999, b는 -1000에서 1000까지 검증하는 반복문에, n을 0부터 대입하면서 가장 길게 소수를 만드는 경우를 계산하면 된다.

출제 의도는 좀 더 효율적으로 계산하는 방법을 고민하기를 원했던 것 같은데 단순한 방법으로 해결 가능했다.