[C++][백준 1929] 소수 구하기

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

 

제출 코드(시간 초과)

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

vector<int> dp;
int pnt = -1;
bool getPrimeNum(int num)
{
    for (int i = 0; i <= pnt; i++)
    {
        if (num == dp[i]) return true;
        if (num % dp[i] == 0)
            return false;
    }
    dp.push_back(num);
    pnt++;
    return true;
}

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

    int m, n;
    cin >> m >> n;

    for (int i = 2; i <= n; i++)
    {
        bool isPrime = getPrimeNum(i);
        if (i < m) continue;
        if (isPrime) cout << i << '\n';
    }
}

저장된 소수들로 나눠서 소수를 판별하는 함수를 만들어서 사용했는데 시간초과가 떴다

 

소수를 판별할 수 있는 다른 방법을 찾아보다가 에라토스테네스의 체를 발견하였다

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

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

    int m, n;
    vector<pair<int, bool>> v;
    cin >> m >> n;

    for (int i = 0; i <= n; i++)
    {
        v.push_back(make_pair(i, true));
    }

    v[1].second = false;
    for (int i = 2; i < n; i++)
    {
        if (!v[i].second) continue;
        int num = v[i].first;
        for (int target = num + num; target <= n; target += num)
        {
            v[target].second = false;
        }
    }

    for (int i = m; i <= n; i++)
    {
        if (v[i].second)
            cout << v[i].first << '\n';
    }
}

우선 int와 bool pair로 이루어진 vector를 선언하고, 0부터 n까지 수를 vector에 넣는다(전체 수 true로 설정)

이후 에라토스테네스의 체의 과정을 그대로 따라해준다

1. 1은 소수가 아니기 때문에 제외(false)

2. 2부터 순서대로 해당 수(i)의 배수들을 전부 제외

3. 만약 해당 차례 수(i)가 false일 경우 건너뛰기

 

위 방식으로 1부터 n까지의 수 중에 소수인 경우를 전부 찾은 뒤, m부터 n까지의 수 중에 true인 경우만 출력해 준다