알고리즘 - Python / 백준 - 13926번 : gcd(n, k) = 1
13926번: gcd(n, k) = 1 (acmicpc.net) 13926번: gcd(n, k) = 1 자연수 n이 주어졌을 때, gcd(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 자연수 n이 주어졌을 때 , n보다 작고 gcd(n,k) = 1을 만족하는 자연수 k의 개수를 구하는 문제다. gcd(a,b)는 a와 b의 최대공약수를 의미하고 이 최대 공약수가 1이라는 뜻은 두 수가 서로소라는 뜻이다. 그러면 어떠한 수 n과 1 ~ n 까지의 k가 서로소인지 아닌지 판별해야 한다. 이때 , 다음과 같은 과정을 통해 알아낼 수 있다. 1. 어떠한 수 n을 소인수 분해 한다. 2. n을 소인수 분해한 수들이 p1,p2,p3....
더보기
