[백준 1929] 소수 구하기

문제설명

M,N을 입력받고, 그 범위내의 소수를 구해서 출력한다.

---

알고리즘

1. N,M을 입력 받는다.
2. bool type의 배열을 N+1만큼 만들고, 1로 초기화 시킨다.
3. 0번째와 1번째는 false로 초기화 해준다.
4. 소수를 구하기 위해서 에라토스테네스의 체 알고리즘을 사용한다.

---

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int M,N;
    cin >>M>> N;

    bool *arr = new bool[N+1];
    fill_n(arr, N + 1, 1);//초기화
    arr[0] = false;
    arr[1] = false;

    for (int i= 2; i <=sqrt(N);  i++)//소수구하기
    {
        if (arr[i])
        {
            for (int j=2*i; j <= N; j+=i)
                arr[j] = false;
        }
    }

    for (int i = M; i <= N; i++)//소수 출력
    {
        if (arr[i])//소수인 경우
            cout << i << "\n";
    }

    delete[] arr;

    return 0;
}

풀이

시간 복잡도: O(n*log(log(n)))

• 에라토스테네스의 체

  1. 작은수부터 나누어지는 수가 있는지 판단한다.
  2. 예를 들어 2를 제외한 2의 배수를 모두 지운다 -> 그럼 4의 배수와 8의 배수는 지울 필요가 없어진다. -> 구하고자 하는 수의 루트를 씌운 범위까지만 판단한다.
     https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

고찰

에라토스테네스의 체를 사용하지 않으면 시간 초과가 발생하는 문제였다.