백준 11689 파이썬 오일러 피

백준 11689 - GCD(n, k) = 1

문제

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

11689번: GCD(n, k) = 1

11689번

답안 코드 :

import math

N = int(input())

result = N

for p in range(2, int(math.sqrt(N)) + 1):  # 제곱근까지만 진행

    if N % p == 0:  # p가 소인수인지 확인

        result -= result / p  # 결괏값 업데이트

        while N % p == 0:  # 2의 7승*11이라면 2의 7승을 없애고 11만 남김

            N /= p

if N > 1:  # 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락되는 케이스 처리

    result -= result / N

print(int(result))

생각 :

# 문제 분석

# 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램

# 이게 바로 오일러 피 함수의 정의 이다

# 문제 풀이

# 오일러 피 함수 구현하면 되겠지

 

정수론 정리 글들

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B1%84

정수론 : 소수 구하기 에라토스테네스의 채

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%98%A4%EC%9D%BC%EB%9F%AC-%ED%94%BC

정수론 : 오일러 피

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

정수론 : 유클리드 호제법

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%ED%99%95%EC%9E%A5-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

정수론 : 확장 유클리드 호제법