에라토스테네스의 체6 [Kotlin] 백준 1644 : 소수의 연속합 문제 링크 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 해설 사용 알고리즘 : 에라토스테네스의 체, 누적합과 부분합, 투 포인터 N이 최대 4,000,000이기 때문에 단순 이중 반복문으로 소수 판정을 하면 시간초과가 발생한다. 따라서 에라토스테네스의 체를 사용하여 소수를 판정해야 한다.(코드의 26~35번째 줄) N 이하의 모든 소수를 판정했다면 이제 N이 소수들의 합으로 나타낼 수 있는지 확인해야 한다. 그런데 문제에서 '연속된 소수의 합'으로 나타낼 수 있는 경우의 수를 구하라는 언급이 있기 때문에 누적합과 투 포인터를 이용한 부분합을 사용하여 이를 효율적으로 구할 수 있다. 소수를 판별한 후 소수의 리스트를 반환.. 2023. 8. 11. [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. [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 다음
