소수 찾기

소수를 찾는 방법을 찾기 위해서 에라토스테네스의 체를 사용하겠다.

에라토스테네스의 체란 소수를 찾는 가장 간단한 방법이다.
예를 들어, 1 ~ 10 까지의 정수 중에서 소수를 찾는다면,

1. 1은 소수도 합성수도 아니므로 제외
2. 다음 수인 2는 소수, 2의 배수는 모두 지운다.
3. 다음 수인 3는 소수, 3의 배수는 모두 지운다.
4. 다음 수인 5는 소수, 5의 배수는 모두 지운다.
5. 다음 수인 7는 소수, 7의 배수는 모두 지운다.
6. 다음 수가 없다. 따라서 10 이하의 소수는 {2, 3, 5, 7}이다.

이렇게 구할 수 있다.

또한 한 가지 더 있다. 만약 에라토스테네스의 체를 이용하여 1 ~ N 까지의 소수를 구한다면, n까지 모든 수의 배수를 다 나누지 않아도 된다.
n이하의 어떤 수 a, b에 대해서 a와 b중 적어도 하나는 √​n 이하 이다.
즉, n보다 작은 합성수 m(a×b)은 √​n​​​ 보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이다.
_조금 설명을 위해선 더 이해가 필요하다_

 

이제 알고리즘을 짜보자.

 

Find Prime Number Algorism

1. 시작 숫자는 3 이고 마지막 숫자는 fn(Final Number) 이다.
(∵ 2 이하의 수는 이미 소수 인 것을 알고 있고, fn는 정의 참고)
2. 수는 2씩 더해 간다.(∵ 짝수는 이미 소수가 아니기 때문이다.)
3. 다음 소수의 배수를 모두 지운다.
4. 다음 소수까지 증가한 후, 위 내용을 반복하여 fn 까지의 소수를 구한다.

 

그럼 위 알고리즘을 C언어로 구현해 보자.

#include <stdio.h>
#include <stdlib.h>
#define INT unsigned int 

void Find_Prime_Number(char * num_str,INT fn) {
	INT start = 3;
	int i = 2;
	for (start = 3; start < fn; start += 2) {
		if (0 == num_str[start]) {
			while (start * i < fn) {
				num_str[start*i] = 1;
				i++;
			}
			i = 2;
		}
	}
}

int main(void) {
	char * num_str;
	INT fn, i;
	fn = 100;

	num_str = calloc(fn, sizeof(char));

	Find_Prime_Number(num_str, fn);
	
	/* 소수 출력 {{ */
	for (i = 3; i < fn; i+=2) {
		if(0==num_str[i])
			printf("%u ", i);
	}
	/* }} */
	
	free(num_str);
	return 0;
}

변수 설명

start	시작 값
fn	마지막 값
num_str	start~fn 까지의 수

잠시 주목할 점은 “num_str[i]“
배열 안에 들어 있는 수는 0(소수) 1(합성수)로, 판단시에만 쓰이고
그 배열의 이름인 “i” 값이 바로 소수가 됨