에라토스테네스의 체1 1456. 거의 소수: 에라토스테네스의 체(Seive of Eratosthenes) 1456. 거의 소수 문제 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 제한 1 ≤ A ≤ B ≤ 1014 에라토스테네스의 체 정수론: 소수 에라토스테네스의 체는 범위 내에 있는 소수를 구하는 알고리즘으로, O(N)의 시간복잡도를 가진, 소수를 구하는 방법 중 가장 빠른 알고리즘이다. 당신이 이걸 고안해내지 않는 바에야 모르면 못 푼다. 못할 건 없겠지만 시간 낭비다. 어떤 한 수가 소수인지 아닌지 판단하는 소수 판별법과는 다르므로 하나의 수가 소수인지 판단하는 것은 나중에 살펴보자. 설명 소수도, 합성수도 아닌 유일한 자연수 1을 제외한다. 2를 제외한 2의 배수를.. 2023. 8. 16. 이전 1 다음