오일러 프로젝트 50 번은 연속된 소수의 합인 소수에 관한 문제이다. 1백만이하의 소수 중에서 연속된 소수의 합으로 표현할 수 있는 소수들을 구분하고, 다시 이 중에서 가장 긴 소수의 합으로 표현되는 소수를 찾는 문제. 간단해보이면서도 쉽지 않은 문제이며, 특히 성능 측면에서 많은 고민과 개선이 필요하다.
41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.
41 = 2 + 3 + 5 + 7 + 11 + 13
이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다. 1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다. 1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?
http://euler.synap.co.kr/prob_detail.php?id=50
접근
특정한 소수 P를 다른 소수의 합으로 나타낸다. 이 때 주목해야 하는 부분은 합을 구성하는 소수들이 연속으로 나열된다는 뜻이다. 이는 중복으로 들어가거나, 중간의 소수를 건너뛰지 않고 오롯이 연속되는 소수의 합으로 구성되는 것을 말한다. 이를 테면 2 + 9 = 11 이나 3 + 3 + 7 = 13 과 같은 케이스는 생각하지 않아도 된다는 점이다.
다행스러운 점은 일단 범위가 한정되어 있다는 부분이다. 연속된 소수의 리스트를 만든다. 그리고 이 리스트에서 i번째 요소와 j 번째 요소 (단 i < j)사이의 구간의 합이 소수가 되는 케이스를 찾으면 된다. 이 때 중요한 것은 소수간의 거리이므로 j - i 가 가장 길 때를 찾으면 된다.
따라서 다음과 같이 접근해보자.
- 100만 이하의 소수 리스트를 만든다.
- 이 리스트에 대해서 맨 앞 요소부터의 합을 저장하는 누적합 리스트를 만든다.
- 길이 l 을 정한다. 누적합 리스트의 길이 – 1을 그 초기값으로 한다.
- 누적합리스트에서 길이 l 인 구간의 합을 체크한다. 이는 누적합 리스트의 0번과 l 번 요소의 차이이다. 만약 이 값이 한계값보다 크다면 길이를 줄여야 한다. 한계값 이내라면 그 구간합이 소수인지 판단한다. 만약 소수가 아니라면 이 구간의 오프셋을 +1 해서 1번~l + 1 번째 소수의 합을 체크하는 식으로 진행한다. 물론, 합이 한계값을 넘어서면 l을 줄여서 진행한다.
- 이렇게 구간 길이를 줄여나가면서, 구간의 오프셋을 조절하면서 조건에 맞는 소수가 발견되는지 확인한다. 길이를 최장으로 하고 찾고 있기 때문에 최초로 발견된 값이 답이 된다.
누적합 리스트 만들기
소수체는 100만 까지 체크하여 만든다.
limit = 100_0000
sieve = [False, False] + [True] * (limit - 1)
for i in range(int(limit**0.5 + 0.5)):
if sieve[i]:
sieve[i*2::i] = [False] * ((limit - i) // i)
primes = [2] + [x for x in range(3, limit) if sieve[x]]
is_prime = lambda x: sieve[x]누적합 리스트는 [0] 을 앞에 하나 붙인다. 이는 후에 offset 처리에도 편하고, 누적합 리스트를 만드는 과정도 깔끔하게해준다.
sop = [0] * (len(primes) + 1)
for i, e in enumerate(primes):
sop[i+1] = sop[i] + e
sop = [x for x in sop if x <= limit * 2]실제 계산
이제 준비 작업을 마쳤으니 실제로 계산해보자. 누적합 리스트의 최대 길이 구간으로부터 1씩 짧아지는 구간 길이에 대해서 오프셋을 늘려가며 비교한다.
maxLength = len(sop) - 1
for length in range(maxLength, 0, -1):
completed = False
for offset in range(0, maxLength - length):
## 부분합을 구해서 비교해본다. 일단 해당 값이 100만 이하의 소수여야 한다.
k = sop[length + offset] - sop[offset]
if k <= limit and is_prime(k):
print(k)
completed = True
break
if completed:
break해당 로직은 매우 짧게 계산한 후에 거의 즉시 답을 낸다. 최초로 이 문제를 풀었을 때 몇 분씩 걸렸던것에 비하면 큰 발전이라 하겠다.
부록 : Swift 풀이
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 준비작업 – 소수체를 생성하고, 누적합 리스트를 만든다. | |
| let limit = 100_0000 | |
| let seive: [Bool] = { | |
| var s = [false, false] + Array(repeating: true, count:limit) | |
| for i in 2…limit where s[i] { | |
| for j in stride(from:i*2, through:limit, by:i) { s[j] = false } | |
| } | |
| return s | |
| }() | |
| let isPrime: (Int) -> Bool = { seive[$0] } | |
| let primes: [Int] = (1…limit).filter(isPrime) | |
| var sums: [Int] = { | |
| var xs = Array(repeating: 0, count: 1 + primes.count) | |
| for i in 1..<xs.count { | |
| xs[i] = xs[i–1] + primes[i–1] | |
| } | |
| return xs.filter{ $0 < limit * 2 } | |
| }() | |
| // 최대길이를 줄여나가고, 오프셋값을 늘려나가며 조건에 맞는 부분합을 찾는다. | |
| main: do { | |
| let maxLength = sums.count – 1 | |
| for l in stride(from: maxLength, to:0, by: -1) { | |
| for offset in 0..<(maxLength – l) { | |
| let gap = sums[l+offset+1] – sums[offset] | |
| if gap <= limit { | |
| if isPrime(gap){ | |
| print(gap) | |
| break main | |
| } | |
| } else { | |
| break | |
| } | |
| } | |
| } | |
| } |