오일러 프로젝트 69
오일러 프로젝트 69 번 문제는 오일러의 피(phi)함수에 관한 내용이다. 사실 소인수분해를 빠르게 할 수 있는 방법만 있다면, 오일러 피함수 역시 간단하게 구현할 수 있으나, 여기서는 범위가 1,000,000까지이므로 만만한 문제가 아닐 수 있다. 그런데 문제를 잘 파악해보면 의외로 쉬운 문제이기도 하다.
오일러의 피(phi)함수 φ(n)은 n보다 작거나 같으면서 n과 서로 소인 숫자의 개수를 나타냅니다. 예를 들어, 9보다 작거나 같으면서 9와 서로 소인 것은 1, 2, 4, 5, 7, 8이므로 φ(9)=6이 됩니다.
n 서로 소인 수 φ(n) n/φ(n) 2 1 1 2 3 1, 2 2 1.5 4 1, 3 2 2 5 1, 2, 3, 4 4 1.25 6 1, 5 2 3 7 1, 2, 3, 4, 5, 6 6 1.1666… 8 1, 3, 5, 7 4 2 9 1, 2, 4, 5, 7, 8 6 1.5 10 1, 3, 7, 9 4 2.5 위에서 보듯이 n ≤ 10인 경우 n/φ(n)의 값은 n=6일때 최대가 됩니다. n이 백만 이하의 자연수일 때, n/φ(n)는 언제 최대가 됩니까? (http://euler.synap.co.kr/prob_detail.php?id=69)
접근
사실 10,000 이하의 수에 대해서 이 값을 찾으라고 하면 피함수를 구현해서 찾으려고 했을 수도 있겠다. 하지만 백만 단위까지라면 사실 매우 단순한 함수를 백만번 호출하는 것도 단시간 내에 해결을 보기가 어려운 문제가 많다. 따라서 우리는 서로소에 대해서 좀 더 자세히 들여다볼 필요가 있겠다.
문제가 요구하는 것은 N에 대해서 N/phi(N)이 최대가 되는 N을 찾는 것이다. 분수식이기 때문에 분모는 작아야 하고, 분자는 커야 한다. 여기서 분모가 작다는 말은, N과 서로소인 수가 작다는 것이고, 이는 공약수를 갖는 수들이 많다는 것이다. (그리고 N은 백만을 넘지 않는 범위에서는 가장 커야 한다.)
공약수를 갖는 수가 많으려면 소인수의 개수가 많고, 중복되는 소인수가 적어야 한다. 이 조건에 의하면 N 이하에서 소인수를 가장 많이 갖는 수는 2 * 3 * 5… 의 식으로 연속된 소수의 곱으로 만들어지는 수여야 한다. (위 예에서도 보면 6, 10이 이 값이 크다) 따라서 문제의 답은 연속된 소수의 곱으로 만들 수 있는 수 중에서 백만을 넘지 않는 가장 큰 수이고, 이는 두 자리까지의 소수를 만들어서 백만을 넘기 전까지 곱해보면 된다.
result = 1
s = [False, False] + [True] * 99
for i in range(2, 11):
if s[i]:
s[2*i::i] = [False] * ((100 - i) // i)
for i in [x for x in range(100) if s[x]]:
if result * i > 100_0000:
break
result *= i
print(result)
소수체를 만드는 것도 이전에 많이 썼었고, 너무 간단한 계산만 하면 되는 코드라 Swift 코드는 생략하도록 하겠다.
부록 : Phi 함수
이 문제에서는 쓸 수 없었지만, 나름 괜찮은 성능의 phi 함수 구현체를 소개한다.
def factorize(n):
def helper(a):
if a in (1, 2): return a + 1 if n % (a + 1) is 0 else helper(a + 1)
if a is 3: return 5 if n % 5 is 0 else helper(5)
k, l, i = a + 2, n**0.5, 0
ds = [4, 2] if k % 3 == 1 else [2, 4]
while k <= l:
if n % k is 0: return k
k, i = k + ds[i], (i + 1) % 2
return n
a, result = 1, []
while n > 1:
a = helper(a)
e = 0
while n % a is 0:
n, e = n // a, e + 1
result.append((a, e))
return result
def phi(n):
if n < 4: return n - 1
xs = [x[0] for x in factorize(n)]
l = int(n**0.5 + 0.5)
s = [False, True] + [True] * (n-1)
for x in xs:
s[x::x] = [False] * (n//x)
return sum(1 for x in range(1, n) if s[x])
