에라토스테네스의 체에 대해 알아보자

기본적인. 소수 구하는 알고리즘

익히고있자~~

1. 에라토스테네스의 체란?

  - 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법입니다.

    * 소수란? 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수

2. 에라토스테네스의 이해

                                       

(출처 : 위키백과<에라토스테네스의 체>) 

  ① 2부터 소수를 구하고자 하는 구간( 1 ~ 120 )을 정합니다.

  ② 2는 소수이므로 Prime numbers로 지정하고, 2의 배수를 모두 지웁니다.

  ③ 남은 수 중에서 3은 소수이므로 Prime numbers로 지정하고, 3의 배수를 모두 지웁니다.

       (지울 때 겹쳐지는 수는 무시하고 진행합니다. )

  ④ 5, 7, 11, 등 남은 수들을 위와 같은 과정으로 반복하면 Prime numbers 을 알 수 있습니다.

3. 에라토스테네스의 구현

#include<stdio.h>
 
int number = 120;
int a[120];
 
void isPrimeNumber() {
    for(int i=2; i<=number; i++) {
        a[i] = i; // 배열 
    }
    for(int i=2; i<=number; i++) {
        if(a[i]==0) { //지워진 수는 건너뜁니다.
            continue;
        }
        for(int j=i*i; j<=number; j+=i) {
            a[j] = 0; //소수를 제외한 배수들을 0으로 빼버립니다.
        }
    }
    
    for(int i=2; i<=number; i++) {
        if(a[i]!=0) {
            printf("%d\n", a[i]);
        }
    }
} 
 
int main(void) {
    isPrimeNumber();
}

※ 결과화면

- 결과를 보면 소수를 출력하는 것을 볼 수 있습니다.

＃주어진 구간이 아니라 주어진 수가 소수인지 판별한다면?

  - 주어진 수 N이 소수이기에 필요한 충분 조건은 N의 제곱근보다 크지 않은 어떤 소수로도 나누어 지지 않는다 입니다.

    Ex) ① 9라는 주어진 수 N은 9의 제곱근인 3보다 크지 않은 어떤 소수로 나누어 지기 때문에 소수이기에 불충분합니다.

           ② 13이라는 주어진 수 N은 13의 제곱근인 3.XXX (.... 대충 암산.....) 보다 크지 않은 어떤 소수로 나누어 지기 때문에 소수이기에 충분합니다.

           ③ 20이라는 주어진 수 N은 20의 제곱근인 4.XXX  보다 크지 않은 어떤 소수로 나누어 지기 때문에 소수이기에 불충분합니다.

  - 구현

#include<stdio.h>
#include<math.h>
 
bool isPrimeNumber(int x) {
    for(int i=2; i<=sqrt(x); i++) { //구하는 범위를 2부터 제곱근보다 적은 범위로 정한다.
        if(x%i==0) { // 나누어 떨어진다. 즉, 소수가 아니다.
            return false; 
        }
    }
    return true;
}
 
// 1이 true, 0이 false 
 
int main(void) {
    bool primeNumber = isPrimeNumber(13);
    if(primeNumber) {
        printf("소수다.");
    } else {
        printf("소수가 아니다.");
    }
    return 0;
} 

  ※ 결과화면