[c++/백준] 1929 소수 구하기

백준

[c++/백준] 1929 소수 구하기

돈 많은 백수가 되고싶다 2023. 5. 5. 21:39

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

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int arr[1000001] = { 0, };

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int a, b;
	cin >> a >> b;

	for (int i = 2; i <= b; i++) {
		arr[i] = i;
	}
	for (int i = 2; i <= b; i++) {
		if (arr[i] == 0) {
			continue;
		}
		for (int j = i+i; j <= b; j += i) {
			arr[j] = 0;
		}
	}
	for (int i = a; i <= b; i++) {
		if (arr[i] != 0) {
			cout << arr[i] << '\n';
		}
	}
}