[Project Euler] 58. Spiral primes

1. 개요

    문제는 이곳에서 확인할 수 있다. 아래와 같이 1부터 자연수를 반시계 방향으로 늘어놓자.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

    흥미롭게도 대각 방향에 있는 수 13개는 1을 제외하고 모두 홀수이다. 또한 그 수들 가운데 8개는 소수이다. 위의 예시에서 그 비율은 \(8/13 \approx 62\%\)이다. 처음으로 그 비율이 10%보다 작아졌을 때 변의 길이를 구하는 것이 문제의 목표이다.

2. 구현

    중앙의 1을 \(n=1\)이라고 하면 오른쪽 아래 방향의 수는 모두 \((2n-1)^2\)이다. 따라서 그 방향의 모든 수는 소수가 아니다. 좌하, 좌상, 우상 방향의 수는 \((2n-1)^2\)에서 \(k(2(n-1), \ k=1,\ 2,\ 3\)만큼 뺀 값이다. 따라서 이 수들만 소수인지 검사하면 된다. 변의 길이는 \(2n-1\)과 같다.

# -*- coding: utf-8 -*-
# Project Euler 58

import sympy as sp

denom, num, n = 1, 0, 1

while True:
    n += 1
    denom += 4
    num += sum(map(sp.isprime, [(2*n-1)**2 - k*2*(n-1) for k in range(1, 4)]))

    if num/denom < 0.1:
        print(2*n-1)
        break

답은 26241이다.