오늘의 코드. 9일차 (백준/1929번 소수 구하기)

 

지난번 오늘의 코딩지식 N0.2(골드바흐의 추측과 소수판별법)에서 다양한 소수판별법을 알아보았는데,
이 지식을 활용하여 문제를 풀어보고 리마인딩 하기 위해 문제를 가져왔다.

 

Baekjoon / Problem No.1929  (소수 구하기)

 

Problem

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

Input

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

Output

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

---

Solution

아주 간결한 문제이다. 지난 오늘의 코딩지식 No.2(골드바흐의 추측과 소수판별법)에서 소수를 판별하는 법에 대해 자세히 알아보았다. 이 문제는 M이상, N이하의 소수들을 모두 출력하는 문제로, 에라토스테네스의 체 알고리즘을 이용하면 범위내의 소수들을 빠르게 확인 할 수 있다.

일정 범위 내에서 소수가 얼마나 있고, 어떤 소수가 있는지 알아보는 방법이라고 볼 수 있다.

 

에라토스테네스의 체에 대한 내용은 " 오늘의 코딩지식 No.2(골드바흐의 추측과 소수판별법)의 Subject 3"을 참고바란다.

https://dailycode.tistory.com/21

오늘의 코딩지식. No. 2 (골드바흐의 추측과 소수판별법)

위의 포스팅에서 설명한 에라토스테네스의 체 알고리즘을 한번 구현하여 보겠다.

---

Code

#include <iostream>
#include <math.h>

using namespace std;

int arr[1000000]; // 문제 조건 이내
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 시간 소요를 줄이기 위해 사용되었다.

    int N, M, i, j;
    int num = 2;

    arr[0] = 1; // 추후에 소수가 아닌 것으로 판별되는 부분들이다.
    arr[1] = 1; // 당연하게도, 0과 1은 소수가 아니다.

    cin >> N >> M;

    while (num <= sqrt(M))
    {
        for (int i = 2; i * num <= M; i++)
            arr[num * i] = 1;
        // 자기 자신은 제외하고 자신의 배수를 지워야하므로, i=2부터 시작한다.
        num++;
    }
    for (int j = N; j <= M; j++)
    {
        if (arr[j] != 1)
            // 1은 소수가 아니기에 !=1 조건을 이용해 1까지 한번에 제거가 가능하다.
            cout << j << "\n";
            // endl; 을 사용 시 더 느려지므로 주의하자 
    }
}

 

위의 코드 중,

    ios::sync_with_stdio(false);
    cin.tie(0);
    // C언어의 버퍼와 C++의 버퍼를 분리시킨다.
    // 멀티스레드나 C,C++의 입출력 방식을 혼용할 시 오류 가능성 있음
    // 많은 입출력에 대한 시간 소요를 줄이기 위해 사용되었다.

 

해당 부분에 대해서는 "오늘의 코드. 2일차(백준/숫자카드)" https://dailycode.tistory.com/6에서 설명하였으니 참고바란다.

오늘의 코드. 2일차 (백준/10815번 숫자 카드)

 

또한,

cout << j << "\n";

 

다음과 같은 식으로 endl; 구문을 사용하지 않았는데, "\n" 구문이 시간 단축에 크게 도움이 된다. 이 점 참고하자.

---

Review

위의 코드 부분에서도 언급하였듯이, 생각보다 자잘한 기술적인 부분에서 문제가 시간 초과되는지, 맞을지가 결정이 된다.

이런 사소하다면 사소한 부분에서 코드의 효율성에서 차이를 보이는 것을 보니, 이미 알고 있는 내용(구문, 함수 등)이라도 다시보고, 어떤 특징이 가지는지에 대해서도 유의깊게 살펴 볼 필요가 있겠다.