개념정리/자료구조
에라토스테네스의 체
김발자~
2023. 3. 30. 20:36
반응형
소수를 구할 때 가장 잘 알려진 알고리즘이 에라토스테네스의 체
유튜브에 치면 그 원리가 자세히 나와있다
간단하게 보자면, 위의 표에서 소수인 2, 3, 5, 7, 11... 들의 배수를 하나하나 지우면서 소수가 아닌 수를 거르는 과정이다
1000000까지 어떤 수가 소수인지 확인하는 코드는 다음과 같다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public static boolean prime[] = new boolean[1_000_001];
//에라토스테네스의 체: false->소수
public static void get_prime() {
prime[0] = true;
prime[1] = true;
for(int i = 2; i < Math.sqrt(prime.length); i++) { //2부터 구하려는 숫자 범위의 제곱근까지 구한다
for(int j = i*i; j < prime.length; j += i) { // i의 제곱이라면 -> i*(i보다 작은 수)는 앞선 반복문에서 모두 사라졌을 것이므로 -> 소수가 아니다
prime[j] = true;
}
}
}
|
cs |
첫 번째 반복문에서 제곱근까지만 구하는 경우는 쉽게 생각해볼 수 있다
그림처럼, 소수가 아닌 수의 약수들은 대칭성을 가진다
따라서 2부터 구하려는 수의 제곱근까지 구해봤을 때 약수가 없다면 이 숫자는 소수라고 판별할 수 있는 것이다
반응형