sieve_eratosthenes.cc

#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long ll;
#define MAXN 10000

int min_factor[MAXN]; //약수 중 가장 작은 녀석


int main() {
	//에라토스테네스의 채

	//0,1 빼고 모두 소수라고 가정하고 시작
	min_factor[0] = -1;
	for (int i = 2; i < MAXN; i++) {
		min_factor[i] = i;
	}
	for (int i = 2; i*i < MAXN; i++) {
		if (min_factor[i] == i) { // i가 소수이면

			//i^2 부터 +i씩 한 값들은 모두 합성수에 해당됨
			for (int j = i * i; j < MAXN; j += i) {
				if (min_factor[j] == j) {
					min_factor[j] = i;
				}
			}
		}
	}
	//소수들 출력
	for (int i = 2; i < MAXN; i++) {
		if (min_factor[i] == i) {
			cout << i << endl;
		}
	}
}