소수 (Prime Number) & 에라토스테네스의 체 (Eratosthenes's Sieve)

소수 (Prime Number) ?

• 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다.
• 소수의 반대말로는 합성수가 있다.
  • 합성수 (Composite Number) ? - 세 개 이상의 양의 약수를 갖는 자연수.

소수 판별

• 주어진 수 n이 소수인지를 판단하는 가장 단순한 방법은 2부터 n - 1 까지의 모든 수를 순회하면서 이 중 n의 약수가 있는지 확인하고, 약수가 없다면 소수란 사실을 알 수 있다.
• 여기에 합성수 n이 p x q로 표현될 때 한 수는 항상 √n 이하, 다른 한 수는 √n 이상이라는 점을 이용하면, n - 1 까지 순회하지 않고 √n까지만 순회하도록 최적화할 수 있다.

O(√n)의 시간복잡도로 동작하는 소수 판별 알고리즘

 

• 1과 2는 예외로 처리한다.
• 2를 제외한 모든 짝수는 소수가 아니다.
• 3이상 √n 이하의 모든 홀수로 나누어진다면 소수가 아니다.
• 위 모든 조건들에 해당되지 않는 숫자는 모두 소수가 된다.

 

 

 

소인수 분해 (Prime Factorization)

• 하나의 합성수를 소수들의 곱으로 표현하는 방법이다.
• 가장 쉬운 방법은 위의 소수 판별 알고리즘을 응용하는 것이다.
• 아래 코드는 n이 소수인 경우, √n번 반복문을 수행한다.

O(√n)의 시간복잡도를 가지는 소인수 분해 알고리즘

 

• 2부터 시작하여 n의 소인수가 될 수 있는 수들을 하나하나 순회한다.
• n의 약수를 찾을 때마다 n을 이 숫자로 나눈다.

 

 

 

 

 

에라토스테네스의 체 (Sieve of Eratosthenes) ?

• 에라토스테네스의 체는 아래와 같이 2부터 n까지의 수를 쓴 상태에서 시작한다.

• 위 목록에서 지어지지 않은 수들을 순회하며 이 수의 배수를 지우기를 반복한다.
• 처음엔 아무 수도 지워지지 않았으니, 지워지지 않은 첫 번째 수는 2이다.
• 이 뒤에 나오는 2의 배수들을 전부 지우면 다음과 같은 상태가 된다.

• 다음으로 지워지지 않는 수는 3이다. 따라서 3의 배수들을 모두 지운다.

• 마찬가지로 5의 배수, 7의 배수를 모두 지우고, 이와 같은 작업을 모두 반복수행하고 나면 결과적으로 남는 수들은 모두 소수가 될 것이다.
• 에라토스테네스의 체는 사실상 앞에서 다룬 간단한 소수 판별 알고리즘을 [2, n] 범위의 모든 자연수에 대해 확장한 것이다.
• 단, 각 수 m이 소수인지 판단하기 위해 √m까지의 모든 수로 나눠보는 대신, 소수를 찾을 때마다 그 배수들을 지우는 형태로 동작하기 때문에 훨씬 빠르게 수행된다.
• 에라토스테네스의 체를 구현할 때 문제가 되는 것은 메모리 사용량이다. 범위 내의 정수가 지워졌는지 여부를 저장해야 하기 때문이다.

동작 애니메이션 (출처 : 위키피디아)

구현

 

• 추가적인 최적화 방식은 i의 배수들을 모두 지울 때, 2 x i에서 시작하는 것이 아니라 i x i에서 시작하는 것이다.
• 2 x i 는 이미 2의 배수를 지울 때 지워졌을 테고, 3 x i 는 3의 배수를 지울 때 이미 지워졌기 때문이다.

 

 

 

 

비트마스크를 이용한 에라토스테네스의 체

• 메모리 사용량이 많다는 문제점에서 출발하여, 메모리 사용량을 줄이기 위한 방법이다.
• 과정은 아래와 같다.
• 숫자 2부터 20까지 중 소수를 뽑아낸다고 해보자.

소수를 판별하는 isPrime 함수

• 숫자 n이 소수라면 (0 이외의 값) true, 소수가 아니라면 (0) false를 반환한다.
• n이 15라고 했을 때, 아래와 같은 과정을 true, false 값이 나온다.

n >> 3

• n >> 3은 n을 오른쪽으로 3비트 Shift하는 것이고 이는 n을 8로 나눈 몫을 구하는 것과 같다.
• 연산을 진행하고 나온 결과 값은 인덱스 역할을 하여 sieve를 참조한다.

1 << (n & 7)

• n & 7은 n과 7을 AND 연산 하는 것이고, 이는 n을 8로 나눈 나머지를 구하는 것과 같다.
• 그리고 1 << m은 1을 m만큼 왼쪽으로 Shift하는 것이며, 이는 2^m 과 같다.

합성수 (소수가 아닌) 를 설정하는 setComposite 함수

• 위 isPrime 함수와 굉장히 비슷하지만 '~' (Not연산자) 연산 차이점이 있다.
• ~ 연산자는 1을 0으로, 0을 1로 바꿔주면 된다.
• 따라서, 1 << (n & 7) 의 결과인 1 0 0 0 0 0 0 0 에 ~연산을 취하면 0 1 1 1 1 1 1 1 이 된다.
• 초기에는 모든 비트가 1로 초기화 되있으며, setComposite 함수를 통해 소수가 아닌 수의 비트는 0으로 갱신된다.

 

• boolean 배열을 왼쪽의 char배열로 대체한다.
• 모든 비트를 1로 만들기 위해 배열을 255로 채워 넣는 것을 주목하자.

 

 

 

 

 

Reference

• https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4
• https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220973318428&proxyReferer=https%3A%2F%2Fwww.google.com%2F
• 도서 : 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략