[백준 알고리즘] 1929 소수구하기 C++ (시간초과 해결)

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

1929번: 소수 구하기

문제

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

출력

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

 

C++ 코드 및 풀이

소수 구하기 문제는 에라토스테네스의 체를 이용해서 풀이하면 시간초과 문제를 해결할 수 있습니다.

에라토스테네스의 체란 아래와 같은 원리로 소수 이외의 숫자를 제외해주는 방법이에요.

출처: https://ko.wikipedia.org/wiki

 

에라토스테네스의 체를 이용해서 코딩하면 아래와 같이 작성하면 됩니다. 저는 모든 숫자에 boolean 값을 true로 대입해준뒤, false로 변경하며 하나씩 제거해줬습니다.

#include <stdio.h>
#include <math.h>
 
int main() {
 
    bool prime[1000001];
    int m, n;
    int i, j;
 
    scanf("%d %d",&m, &n);
 
    for (i = 2; i < 1000000; i++) {
        prime[i] = true;
    }
 
    prime[1] = false;
 
 
    for (i = 2; i<= sqrt(1000000); i++) 
    {
        if (prime[i] == true) 
        {
            for (j = 2 * i; j <= 1000000; j = j + i) 
            {
                prime[j] = false;//(2배수)4, 6, 8, 10,....//(3배수)6, 9, 12...//(4배수)8, 12//(7배수)14, 21, ..제거 
            }
        }
    }
 
 
    for (j = m; j <=n; j++) {
        if (prime[j])
            printf("%d\n", j);
    }
 
    return 0;
 
}

결과