cpp) 백준 1929: 소수 구하기

Problem

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

1929번: 소수 구하기

M이상 N이하의 소수를 모두 출력하시오.

 

 

Solution

#include<iostream>

using namespace std;

int arr[1000001];

void Primesieve(int m, int n){
    // 배열 초기화
    for(int i=2;i<=n;i++){
        arr[i] = i;
    }
    // 에라토스테네스의 체
    for(int i=2;i<=n;i++){
        // 소수가 아닌 것들은 skip
        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] << ' ';
    }
}

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

    int m, n;
    cin >> m >> n;
    Primesieve(m, n);
  
    return 0;
}

 

- 그냥 풀면 시간 초과가 나기 때문에 에라토스테네스의 체를 이용하여 풀이해야 한다.

 

Mechanism
0. 우선 2부터 주어진 수 n까지 배열을 만든다.
1. 어떤 수의 배수는 소수가 아니기 때문에 제외시켜준다.
2. 소수가 아닌 수들을 무시하고 다음 수로 넘어가는 과정을 반복한다.
에라토스테네스의 체 시간 복잡도: O(n log(logn))

 

 

Reference

https://www.youtube.com/watch?v=5ypkoEgFdH8&t=508s