백준 1929번 소수 구하기 [C/C++]

1929번: 소수 구하기

서론

이 문제는 자연수의 범위가  (1 ≤ M ≤ N ≤ 1,000,000) 까지 주어졌다. 즉, 최대 백만개가 되는 수들이 소수인지 판단해야 하기 때문에 일반적인 소수 구하는 방식으로는 시간초과가 뜰 것이다. 그래서 사용할 방법이 에라토스테네스의 체이다.

 

에라토스테네스의 체

간단한 개념이다. 소수는 자기자신과 1로 밖에 나누어지지 않는 수이다. 그러면 어떤 수의 배수는 소수가 될 수 없다. 그래서 2의 배수인 4,6,8 ... 들은 소수가 될 수 없고, 3의 배수도 마찬가지로 6, 9, 12 ...들은 소수가 될 수 없다. 그래서 2,3,4,5 등의 배수들은 소수가 아니라고 결론지을 수 있다. 이러한 개념을 사용하여 쉽게 소수를 판별할 수 있다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int arr[1000001]; //전역 변수 선언시 자동으로 0으로 초기화.

void findPrimeNum(int m, int n)
{
	//0과 1은 소수가 아니기에 1로 체크해준다.
	arr[0] = 1;
	arr[1] = 1;

	//n이하이기 때문에 n+1임.
	for (int i = 2; i < n+1; i++) { 
		/* 배수의 시작은 4부터이다. 즉, 숫자 3이하까지는 소수에 해당하는 부분이기 때문에 2*i부터 시작해도 상관이 없다.
		j+=i는 i만큼 더해지는데, 처음에는 2씩, 다음에는 3씩 더해진다. 즉, 배수의 역할을 하고 있다.
		ex) i가 2이면 2의배수, 3이면 3의 배수의 역할 */
		for (int j = 2*i; j < n+1; j += i) {
			if (arr[j] == 0) {
				arr[j] = 1; //배수는 배열에서 1로 체크된다.
			}
		}
	}

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

int main()
{
	int m, n;
	scanf("%d %d", &m, &n);

	findPrimeNum(m, n);

	return 0;
}

위의 코드처럼 단순히 배열에서 0은 소수인 것, 1은 소수가 아닌 것으로 구분하여 문제를 풀 수 있다.