[백준1929] 에라토스테네스의 체 (C++)

BOJ 바로가기

#include <iostream>
using namespace std;
int arr[1000000];
int main() {
	int a, b;
	cin >> a; cin >> b;
	for (int i = 0; i < b + 1; i++) {
		arr[i] = i;
	}
	arr[1] = 0;
	for (int i = 2; i < b + 1; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = 2; i*j<=b; j+=1)
			arr[i*j] = 0;
	}
	for (int i = a; i < b + 1; i++) {
		if (arr[i] != 0)
			cout << arr[i]<< ' ';
	}
	return 0;
}

가장 핵심적인 코드는 아래 부분이다. 중첩 반복문을 이용해 에라토스테네스의 체를 만들 수 있다.

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

또는 아래와 같은 방식으로 에라토스테네스의 체를 만들 수 있다.

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