[BOJ 23832] 백준 23832번 - 서로소 그래프

		SASA Programming Contest 2021 풀이
A		[BOJ 23825] SASA 모형을 만들어보자
B		[BOJ 23826] 와이파이
C1		[BOJ 23827] 수열 (Easy)
C2		[BOJ 23828] 수열 (Hard)
D		[BOJ 23829] 인문예술탐사주간
E		[BOJ 23830] 제기차기
F		[BOJ 23831] 나 퇴사임?
G		[BOJ 23832] 서로소 그래프
J1		[BOJ 23835] 어떤 우유의 배달목록 (Easy)

1. 문제

$23832$. 서로소 그래프 (SASA Programming Contest 2021 Open Contest G번)

백준 23832번 - 서로소 그래프 (https://www.acmicpc.net/problem/23832)

2. 풀이

$i(1\leq i\leq N)$와 서로소인 수의 개수의 총합을 구하는 문제이다. 이를 위해서는 ‘오일러 피 함수’를 이용해야 한다. (구글링하면 오일러 피 함수에 대한 여러 설명 글을 찾을 수 있다.)

최종적으로는 이런 방식으로 사용해야 한다. $ Φ(10,800)$ $=Φ(2^4\times 3^3\times 5^2)$ $=Φ(2^4)\times Φ(3^3)\times Φ(5^2) $ $=(2^4-2^3)\times (3^3-3^2)\times (5^2-5^1)$ $=8\times 18\times 20$ $=2880 $

각각의 수에 대해 소인수분해를 하고, 각각의 소수의 최대 개수로 만들어지는 $p^k$의 값을 구해서 $p^k-p^{(k-1)}$을 더해나가면 된다.

소인수분해 시, 각각의 $i$에 대해서 $sqrt(n)$까지만 검사하는 방식을 사용하고, 남는 $n$이 $sqrt(n)$를 넘는 소수일 경우를 대비하여 $n>1$인 경우를 예외처리한다. (코드 32~34줄)

3. 채점 결과

4. 회고

방법을 아예 잘못 접근하여 WA를 받았다.

5. 코드