https://www.acmicpc.net/problem/11689 문제자연수 n이 주어졌을 때, 1~n 의 자연수 중 n 과 서로소인 숫자의 개수를 구하는 문제이다. 접근 방법오일러 파이 함수를 이용해야 한다.이는 1부터 n까지의 수 중에서 n과 서로소인 수의 개수를 계산하는 함수이므로 이 문제를 해결하기에 적합하다.따라서, n의 소인수만 찾으면 효율적으로 계산이 가능하다. 오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.이렇게, 소수를 찾아서 순차적으로 p[i] = p[i] - (p[i]/2) 연산을 반복적으로 수행해주면 최종 결과는 오일러 피 함수의 결괏값이 배열에 남게 된다. 코드#include #include #include #include // 오일러 파이 함수 구현long long ..
