The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
[출처 - projecteuler.net/]
항상 그렇듯... 아니 항상은 그렇지 아니하겠지만 현재까지 아주아주 적은 문제를 풀어본 결과 Project Euler에서 제출하는 문제는 아주아주 간단하게 나옵니다. 하지만 몇번 곱씹어야하고 알고리즘의 기본을 수학의 기본을 생각하게 하는 질문을 던지는게 그 특징이라고 생각됩니다.
이번에는 Prime 즉 소수를 구해서 그 합을 구하는게 그 문제입니다. Prime은 해당 수의 약수가 1과 자신인 수를 소수라고 하는데... two million까지 소수를 찾아서 다 더하려면 아무래도 뭔가 로직은 필요하겠죠?? 한번 자세하게 알아보겠습니다.
1. Basic
소수를 구하기 위해서는 1을 제외하고 2부터 시작해서 구하고자 하는 수의 바로 전까지 계속 나눠봤을때 나머지가 0인 수 입니다. 이를 기본적으로 pseudocode를 통해서 작성해보면,
소수인지 체크하는 변수 = true
변수 a를 반복을 2부터 구하고자 하는수까지 라고 하고:
만약 구하고자 하는수 % a == 0 이면:
반복을 멈추고 소수가 아니라하고 소수 체크 변수 = false
break
만약 위의 조건이 아니라면:
continue
최종 소수 체크 변수가 true면 소수결국 위의 로직으로 소수인지 판별하게 됩니다. 그렇다면 위의 문제처럼 이백만... 2,000,000 까지의 수에 대해서 소수를 구하고 그 합을 구한다면... 2부터 2,000,000까지 수를 반복하면서 위의 pseudocode를 그만큼 반복해서 찾아야 할 것 입니다.
그럼 거두절미하고 그대로 코딩을 해서 돌려볼까요??
[소스코드]
import time
def calcPrime(target):
isPrime = True
for i in range(2,target):
if target % i == 0:
isPrime = False
break
if isPrime:
return target
else:
return 0
if __name__ == '__main__':
target = int(input())
start = time.time()
res = 0
for i in range(2, target+1):
if i % 10000 == 0:
print(i)
res += calcPrime(i)
print(res)
end = time.time()
print('걸린시간 : ', end - start)결과는 아래와 같습니다.
[결과]
1940000
1950000
1960000
1970000
1980000
1990000
2000000
================================
[결과]
142913828922
걸린시간 : 23562.168999910355이 얼마나 비효율 적인 코드일까요... 왜냐하면 이 코드는 했던일을 수도없이 반복하기 때문입니다. 예를들면, 초반에는 그래도 수가 작기때문에 소수가 작은아이면 바로바로 결과가 나올 것 입니다. 하지만 후반으로 갈수록 소수가 큰 아이면 내부 함수에서 어마어마한 반복문을 돌려야 하기 때문입니다.
무려 23,562초가 걸렸습니다. 계산해보니 6시간이상이 걸렸습니다....ㅠㅠ
그렇다면, 이 로직을 효율적으로 구하는 방법으로 찾아야 할 것 입니다.
2. Advance
이번에는 다른 방법으로 생각해 보겠습니다. 제가 생각했을때 이 방법이 가장 효율적으로 빠르게 소수를 계산하는 방법이라고 생각합니다.
[Calculatecalculate Prime Number Algorithm]
사상은 간단합니다. 초기에 모든 수는 소수라고 지정합니다. 그리고 2부터 시작하면서, 처음에 등장한 그 수는 소수를 그대로 유지하고, 그 뒤로 그 수의 배수는 모두 소수가 아닌수로 변경합니다. 왜냐하면, 그 수들은 2를 약수로 가지게 되기 때문에 당연히 소수가 아닙니다.
그 다음으로는 3을 확인해서 소수인지 아닌지를 확인합니다. 소수라고 한다면 그대로 소수를 유지하고, 그 뒤로 그 수의 배수를 모두 소수가 아닌수로 변경합니다.
그다음으로 4를 확인합니다. 이 수는 2에 대해서 전처리할때, 이미 소수가 아닌수로 변경되었습니다. 그렇다면 다음수로 자연스럽게 넘어갑니다.
그럼 5를 확인합니다. 이 수는 2와 3의 배수가 아니였기 때문에 소수라고 되어있습니다. 우리의 로직대로 그 뒤의 모든 5의 배수는 소수가 아닌수로 변경합니다.
...............................
이를 목표수까지 반복하면, 하나의 소수 테이블이 만들어 집니다. 이제 남은일은 우리가 원하는 위치로 가서 그 수가 소수인지 아닌지만 꺼내면 되는 것 입니다.
- 모두가 소수라고 적혀있는 저장소를 만든다.
- 2부터 시작하여, 자신은 소수로 유지하고 자신의 배수에 해당하는 모든 수는 소수가 아니라고 변경한다.
- 목표로하는 수까지 반복해서 소수 저장소를 완성한다.
- 소수인지 아닌지를 판단하고자 하는 수의 저장소 위치로 가서 소수인지 결과를 확인한다.
이게 과연 얼마나 빠를지... 예상이 되시나요?? 복잡도로 표현한다면... 우선 2부터 목표수인 n까지 전체 반복이 이루어질 것이고, 해당 반복에 대해서 최대 n/2만큼의 내부 반복이 이루어 질 것입니다. 당연히 나누어 지는 수가 점점 커지기 때문에.... ex) n/2, n/3, n/5.....
O(N^2 / 2)의 복잡도를 가지게 될 것입니다.
[소스코드]
def calcPrePrime(target):
res = [True] * (target+1)
for i in range(2,target+1):
if res[i] == False:
continue
for j in range(2, target):
if i*j > target:
break
else:
res[i*j] = False
return res
def sumPrime(target, pre):
res = 0
for i in range(2, target+1):
if pre[i] == True:
res += i
return res
if __name__ == '__main__':
target = int(input())
start = time.time()
pre = calcPrePrime(target)
res = sumPrime(target,pre)
print(res)
end = time.time()
print('걸린시간 : ', end - start)
[결과]
2000000
142913828922
걸린시간 : 1.6130001544952393음청 단축이 되었네요?? 하지만 이 것보다 더 단축이 가능합니다.
[Advanced Calculatecalculate Prime Number Algorithm]
그렇다면 어떻게 더 줄일 수 있을까요?? 반복을 꼭 목표수까지 돌려야 할까요?? 이런 고민을 하는 이유는... 위에서 로직대로 한다면... 2일때, 2를 제외한 모든 배수에 대해서 소수가 아님을 처리한다고 했습니다.
2x2, 2x3, 2x4, 2x5, 2x6......
그 다음에는 3일때, 3을 제외한 모든 배수에 대해서 소수가 아님을 처리합니다.
3x2, 3x3, 3x4, 3x5, 3x6......
자 이렇게 2와 3만해도 중복되는 로직이 발생합니다. 바로.... 2x3 과 3x2 입니다. 이미 3을 할때는 2에 대해서는 이전 로직에서 적용이 되었기 때문에 할 필요가 없는 것입니다.
그렇다면 어떻게 수정을 하면 될까요??
- 내부 반복문에서는... 구하고자 하는 수를 기준으로 자신의 위치부터의 곱을 계산하는 것입니다.
- 외부 반복문에서는... 1번의 로직때문에... 목표수의 sqrt( ) 즉 제곱수까지만 반복을 하면 됩니다.
1번에 대해서 예를들어보자면...
2x2, 2x3, 2x4, 2x5, 2x6, 2x7, 2x8, 2x9
3x3, 3x4, 3x5, 3x6, 3x7, 3x8, 3x9
5x5, 5x6, 5x7, 5x8, 5x9
2번에 대해서는, 내부 반복문에서 결국 자신의 수의 곱부터 그 계산을 수행하기 때문에, 자신의 제곱수가 구하고자 하는
목표치보다 작거나 같으면 됩니다. 예를들어서, 10000이 목표치인데 99는 99x99 부터 계산하기 때문에 유의미한 연산이
되겠지만... 101의 경우는 101x101 = 10201로 목표치보다 넘어가는 수로 의미가 없어지게 됩니다.
그렇다면 코드로 구현해 보면 아래와 같습니다.
[소스코드]
def calcPrePrime(target):
res = [True] * (target+1)
for i in range(2,target+1):
if res[i] == False:
continue
for j in range(2, target):
if i*j > target:
break
else:
res[i*j] = False
return res
def calcPrePrime2(target):
res = [True] * (target+1)
for i in range(2,int(math.sqrt(target)+1)):
if res[i] == False:
continue
for j in range(i, target):
if i*j > target:
break
else:
res[i*j] = False
return res신규로 calcPrePrime2라는 메서드를 생성하였습니다.
차이점은...
1. 외부 반복문에 범위를 math.sqrt(target)+1 까지로 제한. 단, float오류가 발생하기 때문에 int( )형변환 필요
2. 내부 반복문에는 시작시점을 외부 반복문의 자신부터 시작
[결과]
2000000
142913828922
걸린시간 : 1.0779998302459717그래도 많이 줄었습니다.
금번 문제의 최적화 방법은 Advanced Calculatecalculate Prime Number Algorithm 의 적용으로 마무리 하겠습니다.
- Ayotera Lab -
댓글