[BOJ/C++] 백준 1929번: 소수 구하기

 

🔗 문제 링크 : https://www.acmicpc.net/problem/1929

 

---

 

문제

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

 

 

 

 

 

입출력 예시

입력

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

 

 

출력

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

 

 

 

입출력 예시

 

 

---

 

풀이 

입력값 M, N에 대하여, M ~ N 범위의 소수를 구하는 문제이다.

에라토스테네스의 체 알고리즘을 이용하면, ⏱ 시간복잡도 $\mathbf{O(n\;log\;log\;n)}$으로 간단히 해결할 수 있다. 

 

✒ 에라토스테네스의 체

 

에라토스테네스의 체는 2부터 시작하여 소수의 배수를 지워나가는 방식으로 소수를 찾는 알고리즘이다.

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    int M, N;
    cin >> M >> N;
    
    vector<bool> isPrime(N + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 0; p * p <= N; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= N; i += p) {
                isPrime[i] = false;
            }
        }
    }

    for (int i = M; i <= N; i++) {
        if (isPrime[i]) {
            cout << i << "\n";
        }
    }
}

 

 

 

---

 

"에라토스테네스의 체" 알아보기

 

에라토스테네스의 체(Sieve of Eratosthenes) : 소수를 구하는 고효율 알고리즘

[Algorithm] 에라토스테네스의 체(Sieve of Eratosthenes) : 소수를 구하는 고효율 알고리즘

 

 

---