[Silver 3] 1929번 소수 구하기

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

1929번: 소수 구하기

 

이 문제는 시간 제한으로 인해 어려웠던 문제이다.

 

처음 해결 시 소수를 구하는 함수인 isPrime(int n)을 생성하여 구하려고 하였다.

이 방법은 최대 숫자인 1000000인 경우 시간이 오래 걸리기 때문에 제한 시간을 초과하는 상황이 발생하였다.

 

해결 방법으로는 에라토스테네스의 체를 사용하였다.

이 방법은 배열에 2부터 N까지의 값을 넣어놓고 2의 배수나 3의 배수를 소거하는 방식이다.

예를 들어 i = 2부터 i * i <=N까지 순회를 한다면 N의 범위내에 있는 모든 배수를 찾아낼 수 있다.

문제의 예시인 3부터 16까지인 경우 2의 배수와 3의 배수를 검사할 수 있다.

더 높은 숫자의 경우 4의 배수 5의 배수도 검사할 수 있을 것이다.

 

#include<iostream>
using namespace std;
#define MAX_ARRAY_LENGTH 1000000
int arr[MAX_ARRAY_LENGTH + 1] = { 0, };

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

    for (int i = 2; i <= N; i++) {
        arr[i] = i;
    }

    for (int i = 2; i*i <= N; i++) {
        if (arr[i] == 0) continue;
        for (int j = i * i; j <= N; j += i)
        {
            arr[j] = 0;
        }
    }
    for (int i = M; i <= N; i++)
    {
        if (arr[i] != 0)
        {
            cout << arr[i] << '\n';
        }
    }
}

 

https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

[Algorithm] 에라토스테네스의 체