에라토스테네스의 체와 백준 1929 소수구하기

 

 

백준 소수구하기 소스

#include <iostream>
#include <cstdio>
int prime_num[1000001] = { 0, };
using namespace std;
int main(void){
	int n;
	int m;
	scanf("%d", &n);
	scanf("%d", &m);

	prime_num[1] = -1;

	for (int k = 2; k * k <= m; k++) {
		if (prime_num[k] == 0) {

			for (int i = k*k; i <= m; i+=k) {
				prime_num[i] = -1;
			}
		}
	}

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