[PE] Project Euler 72

프로젝트 오일러 72번은 분모가 1,000,000 이하인 진분수의 전체 개수를 구하는 문제다.

이 문제를 풀기 위해서는 분모가 k로 주어져있을 때 진분수가 몇 개인지 구하는 방법을 알아야 하는데, 분자를 a, 분모를 b라 하면 진분수는

- gcd(a, b) = 1

- a<b

를 만족하므로, 이건 오일러 파이함수 φ(k)값과 같다는 것을 관찰해내면 쉽게 풀 수 있다.

 

즉, 분모가 1,000,000 이하인 진분수의 전체 개수는 φ(1)+φ(2)+...+φ(1,000,000) 를 계산한 값과 같은데, φ(k)의 값은 k를 나누는 소수 p들에 대해 k*((p_1-1)/p_1)*((p_2-1)/p_2)*...*((p_i-1)/p_i)를 계산하는 방법으로 구할 수 있으므로,

- 크기 1000000+1짜리 리스트를 만들어서 i번째 아이템이 i가 되도록 초기화하고,

- 에라토스테네스의 체를 써서 1000000 이하의 소수 p를 구해나가면서, p의 배수들에 대해 (p-1)/p값을 곱해주면

리스트에는 φ(i)들을 계산한 값이 남게 되므로 해당 리스트의 아이템을 전부 더해주면 된다.

n=10**6
p = [True for _ in range(n+1)]
x = [i for i in range(n+1)]
 
for i in range(2,n+1):
    if p[i]:
        for j in range(i,n+1,i):
            p[j]=False
            x[j]=x[j]//i*(i-1)
 
print(sum(x[2:]))

이때 이 리스트의 0번째 아이템이 0, 1번째 아이템이 1이 되는데, 분모가 0, 1인 케이스에서는 진분수가 나올 수 없으므로 이 두 값을 제외해주고 sum을 해주면 원하는 결과를 얻을 수 있다.