(매일 BOJ) C++ 1929번 소수 구하기

이번 문제는 실버 3 난이도의 1929번 소수 구하기 문제이다.

1차 접근법

이 문제를 처음 봤을 때에는 브루트포스를 사용하여 소수를 구하는 방식으로 접근하였다.

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

 

따라서 이 함수를 만들어 소수인지 아닌지를 하나하나 판단한 후 출력하는 방식으로 구현하였지만, TLE가 발생하는 것을 볼 수 있었다.

 

• 각 숫자마다 O(√N)의 검사할 때, N = 1,000,000일 경우 약 O(N√N) = 10^6 * 10^3 = 10^9 = 1,000,000,000 이 되기에 TLE 발생!

2차 접근법 - 에라토스테네스의 체

핵심 아이디어

• 2부터 시작하여 배수들을 지워나가는 방식
• 지워지지 않고 남아있는 수 = 소수

작동 방식

1. 2부터 √N까지 모든 수 i에 대해
2. i*i, i*i+i, i*i+2i, ... (i의 배수)를 전부 제거
3. 남은 수는 모두 소수

시간복잡도

 

 

• 에라토스테네스의 체: O(N log log N)
• 1,000,000 이하에서 매우 빠르게 작동한다!

아래 코드는 에라토스테네스의 체 알고리즘을 사용하여 다시 작성한 코드이다.

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


int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    int M,N;
    cin >> M >> N;
    vector<bool> v (N+1, true);
    v[0] = v[1] = false;
    for(int i = 2; i * i <= N; i++){
        if (v[i] == false) continue;
        for (int j = i*i; j <= N; j += i){
            v[j] = false;
        }
    }
    for(int i = M; i <= N; i++){
        if (v[i] == true) cout << i << '\n';
    }
}

 

 

이러한 문제를 해결하기 위해서 정수론을 공부해야 하는구나.......

수학공부를 열심히 해야겠다.