에라토스테네스의 체

소수(prime number)란 1과 자신의 수 외에는 나눌 수 없는 숫자를 말한다.
그래서 소수는 1과 N만을 약수로 갖는다. 2부터 N-1까지의 수로는 나누어져서는 안된다.

N이하의 소수를 구하는 코드를 작성한다면, 일반적으로 2이상 N미만의 약수가 없는지 판단하고, 없으면 소수 리스트에 추가하면 된다.

이렇게 작성하면 소수는 구할 수 있지만, 시간 복잡도가 O(N^2)이므로, N의 크기가 커짐에 따라서 효율성은 매우 떨어지게 된다.

이에 고대 그리스의 수학자 에라토스테네스는 소수를 찾아내는 효율적인 방법을 알아내었다. 그래서 이를 에라토스테네스의 체라고 부른다.
마치 체로 치듯이 수를 걸러낸다고 해서 붙여진 이름이다.

에라토스테네스의 체 알고리즘을 이용하여 1부터 사용자가 입력한 수까지의 소수를 모두 출력하자.
(프로젝트 명은 Java로 작성하는 경우 Ex2Java로, C로 작성하는 경우 Ex2C로, C++로 작성하는 경우에는 Ex2Cpp로 작성하라.)

"에라토스테네스의 체" 의 원리는 1은 논외로 하고, 소수의 배수들을 모두 걸러내는 방식이다. 예를들어 1부터 50까지 소수를 찾는다고 가정하자.

① 1은 소수가 아니므로 제외한다.

② 2를 만났을 때 2를 제외한 2의 배수를 모두 제외한다.

③ 3을 만났을 때 3을 제외한 3의 배수를 모두 제외한다. 이미 앞서 제외한 수는 무시하면 된다.

④ 4는 2의 배수로 이미 제외된 상태이므로 소수가 아니다.

⑤ 5는 소수이고, 5의 배수들을 모두 제외한다.

이렇게 50이하의 모든 소수에 대해 이 방법으로 반복하면 최종적으로 50 이하의 소수만 남게 된다.

시간 복잡도는 O(NloglogN)으로 N의 값이 큰 수여도 처리하는데 큰 무리가 없다.

---

내 코드

#include<stdio.h>

void Func(int num);

void main()
{
	int num = 0;

	printf("정수 입력 : ");
	scanf_s("%d", &num);

	if (num == 1) return;

	Func(num);
}

void Func(int num)
{
	for (int i = 2; i <= num; i++)
	{
		if (i == 2 || i % 2 != 0)
		{
			if (i == 3 || i % 3 != 0)
			{
				if (i == 5 || i % 5 != 0)
				{
					printf("%d ", i);
				}
			}
		}
	}

}

...
이렇게 하는 건 당연히 아니겠지?
검색해보니까 전부 배열을 사용하던데 나중에 배열로 다시 도전해봐야겠다.

+) 강사님이 칭찬해주셨다! 틀린코드는 아닌가보다 :D~!~!