[BaekJoon 1978][🟤2] 소수 찾기

❓ 문제

백준 1978 - “소수 찾기”

🎯 난이도

Bronze 🟤2

🧠 풀이

1. 내 풀이 (소수 판별)

- 알고리즘

• Mathematics, Prime Number

- 설명

가장 간단한 방식의 소수 판별 풀이이다. 기본적으로 판별할 숫자 표본이 적어서 가장 먼저 떠올랐다.

루프 횟수를 루트 방식으로 줄였으므로 시간 복잡도는 O(√N)이라고 볼 수 있다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

bool IsPrime(int iNum);

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

    int iNum{};
    int iResult{};

    cin >> iNum;

    while(iNum--)
    {
        int iInput{};
        cin >> iInput;

        if(IsPrime(iInput))
        {
            ++iResult;
        }
    }

    cout << iResult;

    return 0;
}

bool IsPrime(int iInput)
{
    if(iInput == 2)
    {
        return true;
    }
    else if(iInput <= 1 ||
            iInput % 2 == 0)
    {
        return false;
    }

    for(int i = 3; i * i <= iInput; i += 2) // 짝수 제외, Input의 루트 == 경계
    {
        if(iInput % i == 0)
        {
            return false;
        }
    }

    return true;
}

---

2. 추가 풀이 (에라스토테네스의 체)

- 알고리즘

• Mathematics, Prime Number, Sieve of Eratosthenes

- 설명

소수 판별할 때 가장 많이 쓰인다고 생각하는 에라스토테네스의 체 알고리즘을 적용한 풀이 방식이다.

사실 이 알고리즘은 범위가 작거나 판별할 숫자 표본이 많을 때 가장 효율이 좋아서 이 문제에는 약간 과할 수 있다. 하지만 코드를 보면 알겠지만 표본을 입력 받으면서 그 중 최대값을 알아내 소수 판별에 필요한 경계값으로 쓰면 소수 판별 루프수를 확 줄일 수 있으므로 나름 최적화가 가능하다.

에라스토테네스의 체 알고리즘에서 소수 테이블을 만드는 전처리 과정은 O(N log log N)이지만 찾는건 임의 접근이므로 O(1)의 시간복잡도를 가진다.

- 코드

추가 풀이 코드

#include <iostream>

#include <vector>


using namespace std;

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

    int iNum{};

    cin >> iNum;

    int iMax{};
    vector<int> vecInput(iNum, 0);
    for(int i = 0; i < iNum; ++i)
    {
        cin >> vecInput[i];
        iMax = vecInput[i] > iMax ? vecInput[i] : iMax; // 최대값 찾아서 소수 판별식 최소화
    }

    vector<bool> vecPrime(iMax + 1, true);
    if(iMax >= 0)
    {
        vecPrime[0] = false;
    }
    if(iMax >= 1)
    {
        vecPrime[1] = false;
    }

    for(int i = 2; i * i <= iMax; ++i)
    {
        if(!vecPrime[i])
        {
            continue;   // 이미 소수면 어차피 배수도 소수이므로 뒤의 과정 필요 없음
        }
        
        for(int j = i * i; j <= iMax; j += i)   // 소수의 제곱부터 시작해서 배수로 올라가며 모두 소수 아님 처리
        {
            vecPrime[j] = false;
        }
    }

    int iResult{};
    for(const auto& iInput : vecInput)
    {
        if(vecPrime[iInput])
        {
            ++iResult;
        }
    }

    cout << iResult;

    return 0;
}

---

💭 후기

소수 판별 알고리즘의 가장 기본적인 형태 중 하나가 아닐까 싶어 한 번 정리해놓고자 싶었다.

기존의 내 풀이도 충분히 좋고 이 문제의 상황에선 정석에 가깝지만, 나름 또 에라스토테네스의 체를 최적화 시켜서 적용시킬수도 있다는 것을 알 수 있다.

🔗 참고자료

• 소수 판별 알고리즘