프로젝트 오일러: 가장 큰 소수
어떤 수를 소인수분해하면 그 수에 대한 소수로 이루어진 약수들을 얻을 수 있다. 예를 들어 13159에 대한 소수는 5, 7, 13, 29가 된다.
그렇다면 600851475143에 대한 소수 중 가장 큰 소수는 무엇인가?
풀이 #1
#!/usr/bin/env python3
MAX=600851475143
prime_list = [2]
pf = []
def is_prime(n):
if n == 2: return True
for p in reversed(prime_list):
if n % p == 0: return False
return True
def prime_generator(m):
for i in range(3, m, 2):
if is_prime(i):
yield i
prime_list.append(i)
def prime_factorial():
m = MAX
for i in prime_generator(m//2):
while True:
if m % i == 0:
pf.append(i)
m = m // i
else:
break
if m == 1: break
prime_factorial()
print(prime_list)
print(pf)
우선 소인수분해를 하기 위해서는 당연히 소수를 만들어낼 수 있어야 한다. 그래서 소수를 만드는 함수 prime_generator
와 소수를 판별하는 함수 is_prime
을 만들었다.
어떤 수가 소수가 되기 위해서는 1과 자기 자신으로만 나누어져야 하므로, 1부터 n/2까지의 수를 n에 나누어 보는 것으로 소수 여부를 판별할 수 있다. 나누는 것에 성공했다면 소수가 아니고 실패했다면 소수가 된다.
여기서 한번 더 최적화하면, 1부터 n/2까지의 수를 모두 나누어볼 필요가 없다. 왜냐 하면 소수가 아닌 모든 수들은 소수의 합성수로 볼 수 있기 때문이다. 예를 들어 4를 소인수분해하면 2와 2를 얻을 수 있는데, 어떤 수를 4로 나누는 것이 가능하다는 것은 4의 소수인 2로 나누는 것도 가능하다는 뜻이 된다.
소수를 매번 계산하지 않기 위해서 한번 계산된 소수는 prime_list에 저장한다. 이 소수 리스트는 is_prime에서 소수인지를 판별하기 위해 나누어볼 수로 사용한다. 따라서 많은 소수를 찾을수록 점점 더 많은 시간이 걸릴 것이다.