record
에라토스테네스의 체 란?
- 소수(Prime Number) 판별 알고리즘이다.
- 소수란, ‘양의 약수를 두개만 가지는 자연수’ 를 의미 2, 3, 5, 7, …등이 존재한다. 즉, 1과 자기자신을 약수로 가지는 수를 말한다.
- 대량의 소수를 한꺼번에 판별 하고자 할 때 사용하는 알고리즘이다.
에라토스테네스의 체의 특징
- 소수를 대량으로 빠르고 정확하게 구할 수 있다.
에라토스테네스의 체의 알고리즘 예시
- 소수란, ‘양의 약수를 두개만 가지는 자연수’ 를 의미 2, 3, 5, 7, …등이 존재한다. 즉, 1과 자기자신을 약수로 가지는 수를 말한다.
일반적인 소수 판별 코드
- 시간복잡도 O(N) 만큼 걸린다.
- 모든 경우의 수를 다 돌며 약수 여부를 확인한다는 점에서 비효율적이다.
#include <stdio.h>
bool PrimeNumber(int x){
for(int i = 2; i < x; i++){
if(x % i == 0) return false;
}
return true;
}
int main(void){
printf("%d",PrimeNumber(97));
return 0;
}제곱근을 이용한 소수 판별 코드
- 시간복잡도 O(N^(1/2)) 만큼 걸린다.
- 제곱근 까지만 약수의 여부를 확인한다.
- 약수들은 대칭을 이룬다 ex) 8 : 2 * 4 = 4 * 2
#include <stdio.h>
#include <math.h>
bool isPrimeNumber(int x) {
// 제곱근을 확인하는 함수
int end = (int) sqrt(x);
for(int i = 2; i <= end; i++){
if( x % i == 0) return false;
}
return true;
}
int main(void){
printf("%d",isPrimeNumber(17));
return 0;
}에라토스테네스의 체 C 구현
#include <stdio.h>
#include <math.h>
int num = 100000;
int a[100001];
void PrimeNumberSieve() {
// 제곱근을 확인하는 함수
// 초기화
for(int i = 2; i <= num; i++){
a[i] = i;
}
for(int i = 2; i <= num; i++){
if(a[i] == 0) continue;
for(int j = i + i; j <= num; j += i ){
a[j] = 0;
}
}
for(int i = 2; i <= num; i++){
if(a[i]!=0) printf("%d ", a[i]);
}
}
int main(void){
PrimeNumberSieve();
return 0;
}