백준 4355번 서로소

< 백준 4355번 서로소 - 마포 코딩박 >

사용한 알고리즘: 수학


 양의 정수 n 이 주어질 때, n 보다 작은 n과 서로소인 양의 정수의 수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (수학)
 1. 소수 p 의 서로소의 개수 = §(p) = p^k - (1-1/p)  입니다.
 ( 오일러 함수 기호를 찾을수가 없어서 § 로 대체합니다... )
 2. a,b가 서로소일 때, §(ab) = §(a)*§(b)  입니다.
 이를 이용해 주어진 n을 소인수 분해 하여 서로소 개수를 찾습니다.

(2) (코드 24~29, 10~22)
 1~40000 까지의 소수를 미리 구해 n을 소인수 분해 합니다.
 ( 어떤 수 A 는 root(A) 초과의 소수로는 나누어 지지 않습니다. n은 최대 10^9 입니다. )

(3) (코드 30~45)
 과정 (1)에 따라 서로소 개수를 찾습니다.
 예를들어 §(n) = §(a^2*b^3) = §(a)*§(b) = ( a^(2-1)*(a-1) )*( b^(3-1)*(b-1) ) 입니다.