취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 4355번 문제인 서로소이다.
문제는 아래 링크를 확인하자.

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

양의 정수 N이 주어질 때 N "미만"의 양의 정수 중 N과 서로소인 수의 개수를 출력하는 문제이다.

양의 정수 N에 대하여 N "이하"의 양의 정수 중 N과 서로소인 수의 개수를 구하는 함수인 오일러 phi함수 \(\phi(N)\)를 구현해 문제를 해결해주자. 이 때, N이 1보다 큰 경우 phi함수와 문제의 답이 같지만 1인 경우 그렇지 않음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll N;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N) {
		if (N == 1) cout << 0 << '\n';
		else {
			ll x = 2, ans = N;
			while (x * x <= N) {
				if (N % x) x++;
				else {
					ans = (ans / x * (x - 1));
					while (N % x == 0) N /= x;
				}
			}
			if (N > 1) ans = (ans / N * (N - 1));

			cout << ans << '\n';
		}
		cin >> N;
	}
}