[백준] 알고리즘 1929번 - 소수 구하기 문제

N이 소수인지 판별하는데 시간복잡도는 O(루트N) 이다.

이 문제의 경우 1부터 백만까지의 소수가 있는지 없는지 저장해두고 M과 N사이의 소수를 출력해줘야 한다.

N이 백만인 경우 시간복잡도는 루트n = 1000 각각의 n의 소수를 구하기 위해서는 1000이 걸리고

N개의 시간복잡도를 계산하면 1000000*1000 = 많은 시간이 걸린다.

이런 시간초과를 해결하기 위해서 에라토스테네스의 체(1부터 N까지의 모든 범위의 소수를 구하기 위해서)를 사용한다.

 

2,3,4,5,6,7,8,9,10 * ** * **~~~~~~

2의 배수의 숫자를 제거한다.

3의 배수의 숫자를 제거한다.

5의 배수의 숫자를 제거한다. 쭉 백만까지 진행한다.

중복된 공배수의 숫자를 제거하기 위해서 이중포문의 j+=i 를 이용하여 공배수의 중복제거 연산횟수를 줄인다.

#include <bits/stdc++.h>
using namespace std; 
bool arr[1000001];
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int m, n;
	cin >> m >> n;
	for (int i = 0; i <= n; i++) {
		arr[i] = true;
	}
	arr[0] = false;
	arr[1] = false;
	for (int i = 2; i <= n; i++) {
		if (arr[i]) {
			if (pow(i, 2) > 1000001)break;
			else {
				for (int j = pow(i, 2); j <= n;) {
					arr[j] = false;
					j += i;
				}
			}
		}
	}
	for (int i = m; i <= n; i++) {
		if (arr[i] == true) {
			cout << i << "\n";
		}
	}
}