[개념] 4.에라토스테네스의 체

에라토스테네스의 체란?

*소수(Prime number)판별 알고리즘으로 대량의 소수 한꺼번에 판별하고자 할 때 사용하는 알고리즘

*1과 자기자신을 약수로 가지는 수

 

배수를 제거함으로써, 탐색 속도를 줄일 수 있는 방식

#include<iostream>
using namespace std;
int number=100;
int arr[100+1];
void primeNumberCheck(){
    for(int i=2;i<=number;i++){
        arr[i]=i;
    }
    for(int i=2; i<=number; i++){
        if(arr[i]==0)continue;
        for(int j=i+i; j<=number;j+=i){
            //배수의 경우 0으로 값 설정해줌
            arr[j]=0;
        }
    }
    for(int i=2; i<=number; i++){
        if(arr[i]!=0)cout<<i<<" ";
    }
}
int main(){
    primeNumberCheck();
}

 

**나동빈님 강의 정리하면서 공부한 내용입니다.

https://youtu.be/5ypkoEgFdH8

 

|본 포스팅은 쿠팡 파트너스의 일환으로 소정의 수수료를 제공받을 수 있음을 알립니다 |