오일러 프로젝트 58

오일러 프로젝트 58 번 문제는 28번 문제와 비슷한 나선모양 격자를 늘려가면서 대각선에 존재하는 숫자중에서 소수의 비율이 10%미만이 될 때의 사각형의 크기(한변의 길이)를 구하는 문제이다. 종료 범위를 미리 알 수 없기 때문에 나선을 따라가며 소수인 수와 소수가 아닌 수를 모두 세어서 그 비율을 계산해야 하기 때문에 소수 판별 검사 함수의 성능이 매우 중요하다.

숫자를 1부터 시작해서 하나씩 늘려가며 아래와 같이 시계 반대 방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다.

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

우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선의 놓인 13개의 숫자 중 8개가 소수라는 것입니다. 그 비율은 약 8/13 ~= 62% 정도가 됩니다.

이런 식으로 계속 소용돌이를 만들어 나갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.

접근

얼마나 큰 사각형을 만들어야 할지 (혹은 최소한 어느 수준 크기 이하에서는 답이 나오는지)를 알 수 없기 때문에 미리 체를 만들거나, 그리드를 미리 만들어볼 수가 없다. 따라서 대각선 방향으로 돌아나가면서 일일이 소수 검사를 하는 수 밖에 없다.

다만, 우측 하단 대각선 방향의 수는 홀수 완전 제곱수 (한 변에 대해서 검사할 때는 마지막 네 번째 수)이므로 이는 항상 소수가 아니라는 것은 알 수 있다.

파이썬 풀이

마지막 모서리를 건너뛰도록 함으로 25%가량 줄어서 4초가량 걸렸다. (시스템 성능이 좀 좋으면 더 줄지도…)

def is_prime(n):
  if n < 2: return False
  if n in (2, 3): return True
  if n % 2 is 0 or n % 3 is 0: return False
  if n < 10: return True
  k, l = 5, n ** 0.5
  while k <= l:
    if n % k == 0 or n % (k + 2) == 0: return False
    k += 6
  return True

def e058():
  edge, cursor, pcount, ncount = 2, 1, 0, 1 
  while True:
    for _ in range(3):
      cursor += edge
      if is_prime(cursor):
        pcount += 1
      ncount += 1
    cursor, ncount = cursor + e, ncount + 1
    if pcount * 10 < ncount:
      print(edge+1)
      break
    edge += 2     

Swift 풀이

파이썬과 동일한 코드이다. 대신 수행속도는 훨씬 빠르다. IBM 서버가 좋아서 그런지도 모르겠다… (실행: http://swift.sandbox.bluemix.net/#/repl/59a53eb4ffaee1404783d4f4)

func isPrime(_ n: Int) -> Bool {
  if n < 2 { return false }
  if (2...3) ~= n { return true }
  if n % 2 == 0 || n % 3 == 0 { return false }
  if n < 25 { return true }
  var k = 5
  let l = Int(sqrt(Double(n)) + 0.5)
  while k < l {
    if n % k == 0 || n % (k + 2) == 0 { return false }
    k += 6
  }
  return true
}

do {
  var (e, c, p, n) = (2, 1, 0, 1)
  while true {
    (1...3).forEach{ _ in 
      (c, n) = (c + e, n + 1)
      if isPrime(c) { p += 1 }
    }
    (c, n) = (c + e, n + 1)
    if p * 10 < n { break }
    e += 2
  }
  print(e + 1)
}