dotdotdot

https://www.acmicpc.net/problem/9020문제 설명1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같..

에라토스테네스의 체소수(prime number)란?1과 자기 자신을 제외한 다른 어떤 수로도 나누어지지 않는 자연수이다. 예를 들어, 2, 3, 5, 7, 11 등은 소수이다. 일반적으로 소수를 판별하는 방법 중 하나는 특정 수가 소수인지 하나씩 확인하는 O(√N) 방식이다. 예를 들어, 어떤 수 xxx가 소수인지 판별하려면 1부터 xxx까지 모든 수를 나누어보는 대신, √x까지만 확인하면 충분하므로 O(√N)의 시간 복잡도를 갖는다.하지만 N까지의 모든 소수를 찾을 때 이 방식을 그대로 적용하면, 각 숫자마다 O(√N) 연산을 수행해야 하므로 전체적으로 O(N√N)의 시간 복잡도가 발생한다.이 때문에 여러 개의 소수를 한 번에 찾기에는 비효율적이며, 보다 빠르게 소수를 구하기 위해 에라토스테네스의 체 ..