[BOJ] C++ 1929 "소수 구하기" 문제 풀이 _ nov

#INFO

난이도 : SILVER3

문제유형 : 소수 판별 알고리즘

출처 : https://www.acmicpc.net/problem/1929

---

#SOLVE

특정 다수의 소수를 판별하는 문제이기에, 에라토스테네스의 채를 이용해 문제를 풀이했다. _about EratosSieve

int sieve[1000001] = {0, };
void eratos(int n, int m){
	for(int i = 2; i <= m; ++i) sieve[i] = i;
	// 2의 배수를 제거한다.
	for(int i = 2; i <= m; ++i){
		// 이미 지워진 숫자는 continue
		if(sieve[i] == 0) continue;
		for(int j = i + i; j <= m; j += i){
			sieve[j] = 0;
		}
	}
	for(int i = n; i <= m; ++i){
		if(sieve[i] != 0) cout << i << '\n';
	}
}

---

#CODE

#include <iostream>
using namespace std;

int sieve[1000001] = {0, };
void eratos(int n, int m){
	for(int i = 2; i <= m; ++i) sieve[i] = i;
	// 2의 배수를 제거한다.
	for(int i = 2; i <= m; ++i){
		// 이미 지워진 숫자는 continue
		if(sieve[i] == 0) continue;
		for(int j = i + i; j <= m; j += i){
			sieve[j] = 0;
		}
	}
	for(int i = n; i <= m; ++i){
		if(sieve[i] != 0) cout << i << '\n';
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	eratos(n, m);
	return 0;
}