오일러 프로젝트 58 번 문제는 28번 문제와 비슷한 나선모양 격자를 늘려가면서 대각선에 존재하는 숫자중에서 소수의 비율이 10%미만이 될 때의 사각형의 크기(한변의 길이)를 구하는 문제이다. 종료 범위를 미리 알 수 없기 때문에 나선을 따라가며 소수인 수와 소수가 아닌 수를 모두 세어서 그 비율을 계산해야 하기 때문에 소수 판별 검사 함수의 성능이 매우 중요하다.
숫자를 1부터 시작해서 하나씩 늘려가며 아래와 같이 시계반대방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다. 우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선상에 놓인 13개의 숫자 중 8개가 소수라는 것입니다. 그 비율은 대략 8/13 ≈ 62% 정도가 됩니다. 이런 식으로 계속 소용돌이를 만들어갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.
접근
얼마나 큰 사각형을 만들어야 할지 (혹은 최소한 어느 수준 크기 이하에서는 답이 나오는지)를 알 수 없기 때문에 미리 체를 만들거나, 그리드를 미리 만들어볼 수가 없다. 따라서 대각선 방향으로 돌아나가면서 일일이 소수 검사를 하는 수 밖에 없다.
다만, 우측 하단 대각선 방향의 수는 홀수 완전 제곱수 (한 변에 대해서 검사할 때는 마지막 네 번째 수)이므로 이는 항상 소수가 아니라는 것은 알 수 있다.
풀이
마지막 모서리를 건너뛰도록 함으로 25%가량 줄어서 3.5초가량 걸렸다. 이전 코드에서는 while 루프 안에 다시 range(3)에 대한 for루프를 돌아서 오른쪽 아래를 제외하고 검사했는데, 변수 하나를 두고 0, 1, 2, 3, 0, 1, 2, 3, .. 으로 늘려가면서 이 값이 0일 때 오른쪽 아래 모서리가 되도록 해서 조금 단순화했다.
def isprime(n: int) -> bool:
if n < 2:
return False
if n < 4:
return True
if n % 2 == 0 or n % 3 == 0:
return False
if n < 9:
return True
k, l = 5, int(n**.5+1.5)
while k < l:
if n % k == 0 or n % (k + 2) == 0:
return False
k += 6
return True
def e058() -> int:
step, pos, x, y = 2, 1, 0, 1
d = 0
while True:
pos += step
y += 1
d = (d + 1) % 4
if d == 0:
if x * 10 < y:
return step + 1
step += 2
elif isprime(pos):
x += 1 2020-06-02에 업데이트 : 코드 개선