아리토스테네스의 체란?
소수를 판별하는 알고리즘으로 소수들을 대량으로 빠르게 구할 수 있다.
소수란?
양의 약수를 2개만 가지고 있는 자연수
단일 숫자 소수 여부 확인
어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^(1/2))의 시간 복잡도로 빠르게 구할 수 있다.
8의 경우 2 4 = 4 2와 같은 식으로 대칭을 이루기 때문입니다. 그러므로 제곱근까지만 약수의 여부를 검증하면된다.
- 시간 복잡도 O(N) *비효율적
bool isPrimeNumber(int x) {
// x 미만의 소수 구하기
for(int i = 2; i < x; i++) {
if(x % i == 0 ) return false;
}
return true;
}- O(N^(1/2))
bool isPrimeNumber(int x) {
// x 미만의 소수 구하기
int end = (int)Math.sqrt(x);
for(int i = 2; i <= end; i++) {
if(x % i == 0 ) return false;
}
return true;
}만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다.
에라토스테네스의 체 원리
에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.
- 배열을 생성하여 초기화한다.
- 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
=> 2부터 시작하여 남아있는 수를 모두 출력한다.
int[] arr = new int[n];
void isPrimeNumber(int n) {
// n 미만의 소수 구하기
for (int i = 2; i < n; i++) {
a[i] = i;
}
for (int i = 2; i < n; i++) {
if (a[i] == 0) continue;
for (int j = i + i; j< n; j += i) {
a[j] = 0;
}
}
for (int i =2; i < n; i++) {
if(a[i] != 0)
System.out.println(a[i])
}
}
Hello World!!