정수론-오일러 피

이론

📖 오일러 피
오일러 피 함수 P[N] 은 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.

1) 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스값으로 초기화한다.
2) 2부터 시작해 끝까지 현재 리스트의 값과 인덱스가 같으면(소수일때) 현재 숫자의 배수에 해당하는 수를 리스트 끝까지 탐색해 P[i]=P[i]/K 연산을 수행한다.

문제풀이

📖 백준 11689 (🔗백준 11689 문제)

✏ GCD(n,k)=1 (1<=k<=n) 을 만족하는 자연수의 개수 = 오일러 피 함수

# 오일러 피 함수
import math
import sys
input=sys.stdin.readline

n=int(input())
result=n

for i in range(2,int(math.sqrt(n))+1):
    if(n%i==0):
        result-=result/i
        while n%i==0:
            n=n//i

if n>1:
    result-=result/n

print(int(result))

◼ 참고사항

• https://0902.tistory.com/59
• Do it! 알고리즘 코딩테스트
• 백준