반응형 에라토스테네스의 체2 [C/C++] 백준 #1929 소수 구하기(에라토스테네스의 체) 주어진 범위안의 숫자에 대해서 소수를 출력하라는 문제입니다. 사실 소수 구하기는 여러가지 방법이 있지만, 에라토스테네스의 체를 사용하는 것이 가장 빠른 편입니다. 에라토스테네스의 체를 사용하는 데 있어서 단점은 처음부터 해야한다는 것입니다. 특히 2의 배수의 개수는 많으므로, 보다 효율적인 형태를 만들려면, m이 2보다 작거나 같고, n이 2보다 크거나 같으면, 2는 무조건 출력하고, 홀수에 대해서만 처리하는 방법입니다. 그렇게 하면 전체적으로 \(\frac{1}{4}\)로 줄일 수 있습니다. 또한 메모리 문제입니다. 메모리 제한이 작으면, 에라토스테네스의 체를 비트필드 형태로 하든지 아니면, \(n \sqrt{n}\) 알고리즘으로 만들어야 합니다. 이 문제 자체가 Silver III 등급정도의 문제로 .. 2022. 11. 11. 백준 #1016 제곱 ㄴㄴ수 이번 문제는 1을 제외한 제곱수로 나누어 떨어지는 수를 구하는 것입니다. 에라토스테네스 체의 확장판이라고 생각하시면 될 것 같네요. 그리고 숫자의 범위는 작지만 숫자 자체가 꽤 커서 소수를 꽤 많이 구해야 합니다. 어떤 수 \(n\)이 소수인지는 \(O(\sqrt{n})\)의 복잡도로 판단할 수 있어서, 숫자가 \(10^{12}\) 오더이긴 하지만 제곱수이기 때문에 실제 구해야할 소수는 \(10^6\) 오더입니다. 계산량으로 보면 제한시간의 절반 이하로 가능합니다. 그런데 정답비율은 18%로 아주 낮습니다. 문제는 아래의 링크에 있습니다. https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,.. 2019. 12. 24. 이전 1 다음 728x90
