[BOJ] 1929번 : 소수 구하기

1. problem : 

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

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n, m; 

vector<int> eratos(int a) {
	vector<int> primes; 
	vector<bool> numbers(1000005, true); 
	numbers[1] = false; 
	for (int i = 2; i * i <= a; i++) {
		if (!numbers[i]) continue;
		for (int j = i * i; j <= a; j += i) {
			numbers[j] = false; 
		}
	}
	for (int i = 2; i <= a; i++) {
		if (numbers[i]) primes.push_back(i);
	}
	return primes;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m; 
	vector<int> primes = eratos(m); 
	for (auto p : primes) {
		if (n <= p) cout << p << '\n';
	}
}

 sieve of Eratosthenes를 이용해 풀었다. 아직 에라토스네스의 체가 이해가 가지는 않지만, 외워서 풀었다. 

여기서 vector <bool>을 이용하면, 공간 절약과 cache hit rate 가 높아진다고 한다.