9급_지방직_공무원_서울시_수학 2022년 기출문제 20번

Question

부터 3000까지의 자연수 중에서 3000과 서로소인 자연수의 개수를 구... 에 관한 핵심 기출문제

Accepted Answer

부터 3000까지의 자연수 중에서 3000과 서로소인 자연수의 개수를 구하기 위해 오일러의 피 함수(Euler's totient function)를 사용합니다. 3000은 $3000 = 2^3 \times 3^1 \times 5^3$으로 소인수 분해되며, 서로소의 개수는 $3000 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) \times (1 - \frac{1}{5}) = 3000 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 800$입니다. 따라서 정답은 ② 800입니다.