플레찍었으니 정리해보는 알고리즘 노트 3- GCD, 유클리드 호제법,오일러 피 함수

GCD 알고리즘은 최대 공약수를 구하는 알고리즘이다.

GCD를 구현하는데 가장 흔히 알고리즘은 유클리드 호제법을 이용한 알고리즘이다.

수학적 증명은 그냥 넘어가자

def gcd(a,b):
    if a > b:
        a,b = b,a
        
    while b > 0:
        a,b = b,a%b
        
    return a

두 수 a,b(a < b)가 있을 때

b가 0이 될때까지 a에 b를, b를 a로 나눈 나머지를 계속 b에 대입시키면 남는 a가 최대 공약수가 된다.

 

https://www.acmicpc.net/problem/11689

11689번: GCD(n, k) = 1

이 문제는 n이 주어졌을때 GCD(n,k) = 1이 되는 k 즉 서로소가 되는 n이하 자연수 k의 개수를 찾는 문제인데 n의 범위가 매우 커서 유클리드 호제법을 사용한다면 시간초과가 발생한다.

이 문제는 오일러 피 함수를 이용해 풀었다.

오일러 피 함수는 특정한 수 n을 소인수분해 해 p1^a1  *  p2^a2  * p3^a3... 꼴로 나올때 1~N중 N과 서로소인 숫자의 개수는 p1^a1(1 - (1/p1)) * p2^a2(1-(1/p2)) .... 라는 함수이다.

 

소인수 분해하는 과정은 에라토스테네스의 체를 이용해 최대한 빠르게 구현했고 그 이후 오일러 피 함수를 이용해 서로소인 숫자의 개수를 구했다.

n = int(input())
ans = 1
temp = int((n**(1/2)) + 1)
lst = [True]*temp
stack = []


for i in range(2,temp): # 에라토스테네스의 채
    if lst[i] == True:
        j = 2
        while i*j < temp:
            lst[i*j] = False
            j += 1
        
        if n%i == 0:
            stack.append(i)
            

i = 0

while i < len(stack) and stack[i] < n: # 오일러 피 함수 구현
    if n % stack[i] == 0:
        ans *= stack[i]
        n = n/stack[i]
    else:
        ans = ans*(1-(1/stack[i]))
        i += 1

if n != 1:
    ans = ans * n * (1 - (1/n))
    
print(int(ans))