[C/C++] 에라토스테네스의 체를 이용한 소수 출력 (1)

# Visual Studio 2019

# 1부터 n까지의 수 중 소수를 전부 출력하는 프로그램이다

 

# 에라토스테네스의 체(Sieve of Eratosthenes)란?

수학자 에라토스테네스가 만든 소수 판별법. 체(sieve)로 치듯이 수를 걸러낸다는 것에서 착안

 

# 에라토스테네스 체 알고리즘

1. 1부터 n까지의 표를 만들고 (=> 배열) 1을 제외한다 (*1은 소수가 아님)
2. 제외되지 않은 가장 작은 수를 취하고 그 수의 배수는 제외한다
3. 2의 과정을 표 전체에 반복한다

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main() {
	int n;
	int arr[100000] = { 0 };

	scanf("%d", &n);

	for (int i = 0;i <= n;i++) {
		arr[i] = i;
	}

	for (int i = 2; i <= n;i++) {
		if (arr[i] != 0) {
			for (int j = 2 * i;j <= n;j += i) {
				arr[j] = 0;
			}
		}
	}

	for (int i = 2;i <= n;i++) {
		if (arr[i] != 0) {
			printf("%d\n", arr[i]);
		}
	}

	getchar();
	return 0;
}

 

# 프로그램 설명

1. n을 입력받는다
2. 0부터 n까지의 arr [n]=n가 되는 배열을 만든다
3. arr [2] 일 때부터 n만큼 반복문을 실행하며, 이중 for문을 이용해 n의 배수 배열에는 0을 넣는다
   (* 이미 합성수로 검증된 수의 배수는 검증하지 않는다)
   
4. 0이 들어있는 배열(합성수)을 제외한 arr [n](소수)을 출력한다