[백준/BOJ] 1929번 소수 구하기 (C++)

www.acmicpc.net/problem/1929

1929번: 소수 구하기

입력값이 최대 1,000,000 이므로 단순 소수를 찾는 방법은 시간 초과가 발생합니다. 따라서 에라토스테네스의 체라는 방법을 이용해서 해결해야합니다.

 

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int m, n;
    cin>>m>>n;
    vector<int> v(n + 1);
    for(int i = 2; i <= n; i++) {
    	v[i] = i;
	}
	
	for(int i = 2; i <= n; i++) {
		if(v[i] == 0) continue;
		
		for(int j = 2*i; j <= n; j+=i) { // 처음 시작 숫자는 포함하면 안되므로 *2
			v[j] = 0;
		}
	}
	
	for(int i = m; i <= n; i++) {
		if(v[i] != 0) cout<<v[i]<<"\n";
	}
}