[알고리즘] 에라토스테네스의 체
: 소수 판별 알고리즘
기본적인 소수 판별 함수
bool isPrime(int x){
//모든 약수들은 대칭 형태를 가ㅣ기 때문에 제곱근까지만 약수의 여부를 검증하면 된다
int end = (int)sqrt(x);
for(int i=2;i<=end;i++){
if(x%i == 0) return false;
}
return true;
}
에라토스테네스의 체
#include<cstdio>
int N;
int a[100]; //N만큼의 배열 생성
int main(){
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){
printf("%d", a[i]); //0이 아닌 경우만 소수인 수
}
}
}