숫자를 1부터 시작해서 하나씩 늘려나가며 아래와 같이 시계반대방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다. 우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선상에 놓인 13개의 숫자 중 8개가 소수라는 점입니다. 그 비율은 대략 8/13 ≈ 62% 정도가 됩니다. 이런 식으로 계속 소용돌이를 만들어갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.
범위가 한정되지 않았으므로 1부터 시작하여 모서리에 있는 수들을 찾아서 소수인지 검사하여 비율을 구해보는 수 밖에 없다. 모서리에 있는 수들이 어떤 식으로 커지면서 나타나는지 패턴을 파악하고, 성능 좋은 소수 판별함수가 있으면 되겠다. 지금까지 문제를 풀어보면서 작성했던 소수 판별함수 정도의 성능이면 충분히 사용할 수 있다.
가장 가운데 있는 1은 소수는 아니지만 대각선에 포함되는 수이다.
처음 4개의 모서리에 있는 수들은 3, 5, 7, 9로 2씩 커지면서 위치한다. 이 때 정사각형의 한 변은 2 + 1 이다.
4번을 돌고나면 다음번 정사각형의 한 변은 아래 위로 한 칸씩 커지므로 5가 된다. 따라서 건너뛰는 수는 4 가 된다. 즉 간격은 한 바퀴를 돌 때마다 2씩 증가한다.
이상의 내용으로 아래와 같이 코드를 작성할 수 있다. while 루프 한 번을 한 바퀴 도는 것으로 볼 수 도있고, 그냥 한 스텝씩 이동하는 것으로 할 수도 있다. 단 두 경우 모두 우측 아래 (한 바퀴 내에서 네 번째 스텝)의 수는 완전제곱수이기 때문에 소수 검사를 생략하면 1/4 가량의 수행 시간을 단축할 수 있다.
%%time
cursor, step, total, prime = 1, 0, 1, 0 # 1은 이미 포함한 것으로 보고 시작한다.
while True:
step += 2
total += 4 # 전체 모서리 수는 4개씩 증가, 각 모서리에 있는 소수의 개수는 prime에 추가
prime += sum(1 for i in range(3) if isprime(cursor + step * (i + 1)))
if prime * 10 < totla:
print(step + 1)
break
