에라토스테네스의 체

에라토스테네스의 체

- 개념 : 소수(prime number)를 판별하는 알고리즘

     소수? '양의 약수를 두 개만 가지는 지연수' = '1과 자기자신'

- 원리 : 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여 해당하는 값을 넣어주고, 이후에 하나씩 지워가는 방법

1. 배열을 생성하여 초기화한다.

2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.

   이미 지워진 수라면 배수를 확인하지 않고 다음 수로 넘어간다.

   (2를 제외한 모든 2의 배수를 지움

    3을 제외한 모든 3의 배수를 지움

    4를 제외한 모든 4의 배수를 지움

    ... 

   이런식)

3. 2부터 시작하여 남아있는 수를 모두 출력한다.

- 구현 코드

#include <stdio.h>
using namespace std;
 
int arr[10001]; //배열 생성, 1~10000 범위 확인 
 
int main() {
 
    int num;
    scanf("%d",&num); // 1~10000까지
    // 입력받은 수 만큼 배열에 모두 초기화 해둔다    
    for (int i = 2; i <= num; i++) {
        arr[i] = i;
    }
    // 나누는값 2부터 시작
    for (int i = 2; i <= num; i++) {  
        if(arr[i] == 0) continue; //이미 소수가 아닌 경우를 check했으면 pass
 
        for (int j = 2*i; j <= num; j+=i) {
            arr[j] = 0; // 소수가 아닌 경우 0으로 check
        }
    }
 
    for(int i = 2; i <= num; i++) {
        if(arr[i]!=0) printf("%d ", arr[i]);
    }
    return 0;
}