소수구하기 - 에라토스테네스의 체

오늘 구해볼 내용은, 바로 소수 구하기이다.

알고리즘 문제중에 메인보다는 곁들여져서 문제가 나오는 경우가 많은데 이를테면, 어떤 순열을 구해서 그 수가 소수인지 판별 후 최대값을 구해보라. 이런식의 문제류가 많은데, 소수의 정의부터, 어떻게 구할 수 있는지 한번 생각해보도록 하자.

#소수란?

1과 자신만을 배수로 갖는 수이다. 이를 테면 2, 3, 5, 7, 11... 이런수를 소수라고 할 수 있는데 1은 소수가 아니다. 사실 100이라는 수를 입력받았을때 소수인지 아닌지 판별할 수 있는 방법은 무엇일까? 2부터 100까지 쭈욱 나눠보고 100이 아닌 수중에 나눠진다면 소수가 아니기에 아래와 같이 구현할 수 있다.

#include <stdio.h>

int main(void)

{ int num;

int flag = 0;

scanf("%d", &num);

for (int i = 2; i < num; ++i){

if (0 == (num % 2)){

printf("소수 아님\n");

flag = 1;

break;

}

}

if (flag == 0) printf("소수 임\n");

return 0;

}

하지만,,, 여러가지 숫자일 경우, 또 매번 소수를 이런식으로 구하는 건 비효율적이다. 한번의 계산을 통해 배열에 저장해놓고 이용하면 속도에서 굉장히 유리하기 때문에 이런 방법이 있을까 생각해볼 수 있는데 이 방법이 바로 에라토스테네스의 체라는 방법이다.

#에라토스테네스의 체

고대 그리스의 수학자 에라토스 테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.소수를 찾는 가장 간단한 방법이자 가장 무식한 방법이다. 방법은 전체 배열을 생성하고 배열의 모든 값을 1로 세팅한뒤, 2의 배수 부터 n의 배수까지 0으로 지워나가는 방법이다. 2배수, 3배수,...n배수를 지우다보면 50이하의 수를 기준으로 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47이 남는다. 이것이 50미만의 소수이다. 자 그럼, 코딩을 해보자. 의외로 정말 간단하다. 50을 입력하면 소수들이 출력되고 15개임을 알 수 있다.

#include <stdio.h>

#define MAX 1000

int data[MAX + 1];

int main(void)

{

int num;

int i, t, cnt = 0;

scanf("%d", &num);

// 모든 수를 소수로 세팅

for (i = 0; i <= num; ++i){

data[i] = 1;

}

// 체로 걸러준다.

for (i = 2; i <= MAX; ++i){

for (t = 2 * i; t <= num; t+=i){

data[t] = 0;

}

}

// 0과 1은 소수가 아니기에 수동으로 걸러준다.

data[0] = 0;

data[1] = 0;

// 남은 것들을 살펴본다.

for (i = 1; i <= num; ++i){

if (data[i] == 1){

printf("%d\n", i);

cnt++;

}

}

printf("Total [%d]\n", cnt);

return 0;

}

앞으로 소수구할때는 이 방법을 꼭 적용해보자!