[알고리즘] 에라토스테네스의 체 #c언어

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다.

알고리즘 설명

.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당

2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨강)

3. 자기 자신을 제외한 2의 배수를 모두 지운다.

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록)

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파랑)

7. 자기 자신을 제외한 5의 배수를 모두 지운다

8. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

알고리즘 구현 (c언어)

배열에서 소수인칸에는 1, 소수가 아닌칸에는 0을 넣어 나중에 갯수를 세어 소수의 갯수를 구할것이다. 

즉, arr[0]=숫자0 arr[1]=숫자1 arr[2]=숫자2 라 생각하면 되고 소수가 아닌칸에는 0, 소수인 칸에는 1을 넣는다 arr[0]=0 arr[1]=0 arr[2]=1 arr[3]=1 이런식으로.

우선 모든 배열은 1로 초기화를 하며 0과 1은 소수가 아니므로 먼저 0을 넣어준다.

반복문을 2부터 돌리며 배열의 크기만큼 반복문을 실행한다. 반복문 안에 반복문을 넣어주며 배수들의 칸에 0을 넣어 소수가 아님을 표시한다.

이 이중 for문이 다 돌고 나면 소수인 칸에는 1이 남고 소수가 아닌 칸에는 0이 남게 된다. 나중에 이 코드를 가지고 1의 갯수를 세어 0부터 n까지 소수의 갯수를 셀 수 있는 코드를 만들수 있다.

#include<stdio.h>

int main() {

    int arr[300000];
    arr[0] = 0;
    arr[1] = 0;
    int i, j;

    for (i = 2; i <= 300000; i++)
    arr[i] = 1;

    for (i = 2; i <= 300000; i++) {
        if (arr[i] == 1) {
            for (j = i + i; j < 300000; j += i) {
                arr[j] = 0;
            }
        }
        else continue;
    }

알고리즘 활용 

[백준4948] 베르트랑 공준 _ c language