Beakjoon] 소수 구하기 (백준 1929 코테) - 정수론 (C++)

---

🅰️문제주소 : https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

🚩문제 

 

 

🪡풀이 

 - 최대 범위가 1,000,000으로 주어졌으므로 에라토스테네스의 체를 사용해야 한다.
O(Nlog(logN)) 의 시간복잡도를 가진다
 - 연산하기 쉽게 0에서 N까지 모두 벡터에 넣은 뒤 에라토스테네스의 체를 돌리며 소수가 아닌 수는 0으로 변경시킨다.
 - M에서 N사이의 0이 아닌 값을 출력한다.

 

 

☕코드는 아래 숨김

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

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int M, N;

    std::cin >> M >> N;

    std::vector<int> nums(N+1, 0);

    for (int i = 0; i <= N; ++i) {
        nums[i] = i;
    }

    if (nums[1] == 1) {
       nums[1] = 0;
    }

    for (int i = 2; i <= std::sqrt(N); ++i) {
        if (nums[i] == 0)
            continue;
        for (int j = 2; j*nums[i]<=N; ++j) {
            nums[nums[i] * j] = 0;
        }
    }

    for (int i = M; i <= N; ++i) {
        if (nums[i] != 0)
            std::cout << nums[i] << '\n';
    }
    
    return 0;
}

 

💡알게 된 것 

 - 에라토스테네스의 체
 - 에라토스테네스는 천재인가? 그는 신인가?

---