소수 구하기 - 실버3(1929)

작성일 | In

문제

문제 image

문제 해결

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>  
#include<algorithm>  
  
using namespace std;  
  
int N,M;  
int arr[1000001];  
  
void input() {  
    cin>>M>>N;  
}  
  
void solution() {  
    arr[1] = 1;  
    for (int i = 2; i <= N; i++) {  
        for (int j = 2; i * j <= N; j++) {  
            arr[i*j] = 1;  
        }  
    }  
}  
  
void solve() {  
    input();  
    solution();  
}  
  
void printResult() {  
    for (int i = M; i <= N; i++) {  
        if (arr[i] == 0) {  
            cout<<i<<"\n";  
        }  
    }  
}  
  
int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
  
    solve();  
    printResult();  
    return 0;  
}
  • 기존 소수 구하는 방법처럼 이중for문으로 자기보다 작은 수와 나머지 연산을 했을때 나머지가 0인지를 체크 해서 풀면 => 시간초과가 생긴다

2는 소수 이다 => 2의 배수는 소수가 아니다 3은 소수이다 => 3의 배수는 소수가 아니다

  • 위 방법을 이용해서 배열을 미리 만들어 놓고 0이면 소수이고 1이면 소수가 아니다로 체크
  • 1의 경우는 소수가 아니기 때문에 미리 1로 바꿔 놓는다