Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Bakjoon Q1929 - C++

Q1929

Problem

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

Input

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

Output

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력

1

3 16

예제 출력

1
2
3
4
5

3
5
7
11
13

나의 제출

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

#include <bits/stdc++.h>
using namespace std;

int main(){
    int min, max;
    scanf("%d %d", &min, &max);
    bool *test = new bool[max+1];

    //for(auto a : test) a=true; dynamic array does not support range-based loop
    for(int i=0;i<max+1;i++) //bool array init.
        test[i]=true;

    test[0]=false;
    test[1]=false; //about 0 & 1, make its decision not prime.

    for(int i=2;i<=max+1;i++){
        if(test[i]){
            if(i*i>1000001) break; //to prevent timeout (integer overflow)
            else{
                for(int j =i*i; j<=max+1;j+=i){ //look at here. if j starting with i*i, integer overflow occurs when i is over 46341.
                    test[j]= false;
                }
            }
        }
    }

    for(int k=2;k<min;k++) //make hint array false whose index is under min.
        test[k]=false;

    //print values if it is true (=prime number)
    for(int j=0;j<max+1;j++){
        if(test[j])
            printf("%d\n", j);
    }
}

추가 내용

코드에 대한 전반적인 설명

  1. 먼저, hint array가 동적 할당 되었다. max 입력값에 따라 size가 달라지기 때문. hint array(in my code, named “test”)는 bool 자료형을 담은 array로 해당 index의 number가 prime num인지(=true), 아닌지(false)에 대한 정보를 저장한다.

  2. 먼저 모든 array의 value를 true로 initialization하고 시작한다. 0과 1은 소수가 아니기 때문에 false로 값을 바꾸어준다.

  3. 핵심 - main loop를 돌린다. 첫 소수인 2부터, max보다 하나 큰 값까지. 처음 idx인 2가 소수이기 때문에 if문을 통과하고, 내부의 j loop를 돈다.
    j loop는 j에서 +i씩(즉, i배수) 더해지기 때문에 모든 j의 값은 i의 배수를 의미한다. 따라서 첫 j loop에서는(i=2) 모든 2배수 idx의 값이 false가 된다. i=3에서도 마찬가지 과정이 되고, i=4에서는 이미 test[4]가 false여서 pass된다. 에라토스테네스의 체가 그대로 구현된 모습.

총평

진짜 개어려웠다. 소수 지우는거야 n square loop를 쓰면 금방 풀리지만, 시간 제한이 걸린 문제는 또 처음이다. 에라토스테네스의 체의 시간 복잡도는 O(Nlog(logN))이라고 한다. 그냥 떠올린건 아니고 여기를 참고했다.

https://wikidocs.net/21638

참고로, 중간 부분을 다시 보자.

1
2
3
4
5
6
7
8
9
10

for(int i=2;i<=max+1;i++){
        if(test[i]){
            if(i*i>1000001) break; //to prevent timeout (integer overflow)
            else{
                for(int j =i*i; j<=max+1;j+=i){ //look at here. if j starting with i*i, integer overflow occurs when i is over 46341.
                    test[j]= false;
                }
            }
        }
    }

여기서 “if(i*i>1000001) break;”를 넣지 않게되면 integer overflow가 발생한다. 이걸 삽입해서 i square가 overflow되는 것을 방지하거나,

int i, j 앞에 long을 붙여서 long int i, j로 define하면 문제가 해결된다.

주의할 점은, j = i*i라고 해서 j에만 long 선언을 해주면 안되고 int에도 각각 선언을 해주어야한다(int의 나눗셈 참고).

참고