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

소수를 구하는 문제입니다.

m부터 n까지의 소수를 모두 구해야합니다.

먼저 소수를 전부 구해놓고 m~n사이의
for문을 통해서 소수를 출력합니다.

소수를 구하는 법은 모든 소수의 배수를
전부 소수가 아니라고 체크하는 방식으로 하였습니다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int arr[1000010];

int main(int argc, char *argv[])
{
	int m, n;

	cin >> m >> n;

	memset(arr, 0, sizeof(arr));

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

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