[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\mathrm{\%}$이다. 처음으로 그 비율이 10%보다 작아졌을 때 변의 길이를 구하는 것이 문제의 목표이다.

2. 구현

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

# -*- 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이다.