문제
풀이
특정 범위내의 소수를 찾을 수 있는 빠른 방법 중 하나이다. 소수가 아닌 수들을 거르는 논리인데, 2부터 시작하여, 2의 배수들을 다 제거하고, 3의 배수들을 다 제거… i*i<=최대범위값을 만족하는 i의 배수들은 소수가 된다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
bool arr[1000001] = {true, true, false, };
int main(){
int M, N;
cin >> M >> N;
for(int i = 2; i*i<=1000000; i++){
if(arr[i] == false){
for(int k = 2; k*i <= 1000000; k++){
arr[k*i] = true;
}
}
}
for(int i = M; i<=N; i++){
if(arr[i] == false){
printf("%d\n", i);
}
}
}
