2023/04/081 [Kotlin] 백준 1630 : 오민식 문제 링크 1630번: 오민식 첫째 줄에 자연수 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해설 1~N의 모든 자연수로 나누어 떨어지는 수를 구해야 한다. 다시 말해 N이하의 모든 자연수의 최소 공배수를 구해야 하는데, 이는 N 이하인 소수들의 거듭제곱으로만 이루어진 곱인 소인수분해의 형태로 나타낼 수 있다. 예를 들어, \(N=10\)일 때 오민식을 만족하는 가장 작은 수인 2520은 \(2520=2^3\times 3^2\times 5\times 7\)로 나타낼 수 있다. 우선 N 이하의 모든 소수는 에라토스테네스의 체를 이용하여 구한다. 그리고 각 소수에 대하여 N 이하인 가장 큰 거듭제곱을 구해서 곱하면서 각 연산마다 987654321로 나.. 2023. 4. 8. 이전 1 다음