소수4 [Kotlin] 백준 1456 : 거의 소수 문제 링크 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 문제 해설 수의 범위가 주어졌을 때 해당 범위 내에서 소수의 거듭제곱이 되는 수의 개수를 찾는 문제다. 범위가 최대 \(10^{14}\)이지만 소수는 최대 \(10^{7}\) 범위 내에서만 찾으면 된다. 소수의 거듭제곱이 범위 내에 포함되는지를 찾아야하는데 \(10^{7}=\sqrt{10^{14}}\)이므로 \(10^7\)을 초과하는 소수는 거듭제곱을 하면 범위를 벗어나기 때문이다. 따라서 우선 에라토스테네스의 체를 이용하여 \(\sqrt{B}\) 이하인 소수를.. 2022. 12. 23. [Kotlin] 백준 9020 : 골드바흐의 추측 문제 링크 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 해설 10,000 이하의 짝수 \(n\)이 주어졌을 때, \(n\)을 차이가 가장 작은 두 소수의 합으로 나타내야 한다. 기본적으로는 4948번 문제와 접근 방법이 비슷하다. 모든 테스트 케이스 중 가장 큰 \(n\) 이하의 모든 소수를 탐색한 후 각 테스트 케이스에 대해 주어진 문제의 계산을 수행하면 된다. 문제에 \(n\)의 골드바흐 파티션을 구하면서 두 소수의 차이가 가장 작은 경우를 출력하라는 조건이 걸려있다. 어떤 짝.. 2022. 11. 29. [Kotlin] 백준 4948 : 베르트랑 공준 문제 링크 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 해설 어떤 자연수 \(n\)이 주어졌을 때 \(n\) 초과, \(2n\) 이하인 소수의 개수를 구해야하는 문제다. 어떤 수 \(x\) 이하의 모든 소수를 구하는 방법은 에라토스테네스의 체를 이용하는 방법이 있다. 이 문제도 에라토스테네스의 체를 이용하면 손쉽게 해결할 수 있다. 문제의 조건에 따르면 \(n\)의 최대값은 123,456이고, \(2n\) 이하인 소수의 개수를 구해야하므로 최악의 경우에는 246,912 이하인 소수를 구해야 한.. 2022. 11. 29. [Kotlin/Java] 소수 찾기와 에라토스테네스의 체 소수를 판별하는 기본적인 방법 소수(prime number, 素數)는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 자연수를 의미한다. 예를 들면 2, 3, 5, 7 ... 등이 있다. 어떤 수 \(x\)가 주어졌을 때 \(x\)가 소수인지 판별하는 가장 간단한 방법은 2부터 \(x-1\)까지 모든 수로 \(x\)를 나누었을 때 나누어 떨어지는 수가 있는지 확인하는 것이다. // Kotlin fun isPrime(x: Int): Boolean { for (i in 2 until x) {// 2부터 x-1까지 반복 if (x % i == 0) return false// x가 한 번이라도 나누어 떨어지면 소수가 아님 } return true// 모두 반복해도 나누어 떨어지지 않으면 소수 } // Java .. 2022. 11. 29. 이전 1 다음
