[C++] prime number. 소수 구하기: 에라토스테네스의 체

소수 찾을 때 무식하게 반복문 걸리면 시간이 많이 걸린다는 사실은 이미 알겠죠? 

아무튼 효율적으로 풀기 위한 방법이 에라토스테네스의 체를 이용한 방법입니다.  외우기 힘든 이름이네요..

 

https://terms.naver.com/entry.naver?docId=3405213&cid=47324&categoryId=47324 

에라토스테네스의 체

 

간단정리

 

1~100까지의 소수를 구해야 한다고 생각해봅시다. 

 

1. 100에 루트를 씌우면 10입니다. 
2. 1~10까지의 소수를 구해봅시다. 2, 3, 5, 7 입니다. 
3. 2, 3, 5, 7의 배수를 100 이하까지 다 제거합니다.
4. 남아있는 수가 소수입니다. 

 

#include <iostream>
#include <algorithm> // memset

int main()
{
    const int SIZE = 100;
    
    bool isPrime[SIZE+1];
    std::memset(isPrime, true, sizeof(isPrime));
    
    
    int N = SIZE;
    
    for (int i=2; i*i<=N; ++i)
    {
        for (int j = i*i; j<=N; j+=i)
            isPrime[j] = false;
    }
    
    
    for(int i=1; i<N; ++i)
    {
        if(isPrime[i])
            std::cout << i <<' ';
    }
    
    return 0;
}

 

 

근데 나는 배열로 메모리 차지하고 싶지않다?  

 

에라토스테네스의 체에서 제곱근을 이용해 반복 횟수를 줄일 수 있다는 점을 알게 됐습니다. 

그 점을 이용해 봅시다.

 

N: 100 -> sqrt(N): 10

 

100을 2~10까지 나눠봅시다. 나머지가 0인게 있나요? 있다면 소수가 아닙니다. 

소수는 1과 자기자신을 제외하고 나눠지지 않는 숫자를 뜻하니까요^^...

 

#include <iostream>
#include <cmath>

bool isPrime(int n)
{
    if (n == 1)
        return false;
    
    int tmp = std::sqrt(n);
    for (int i=2; i<=tmp; ++i)
    {
        if (n % i == 0)
            return false;
    }
    
    return true;
}

int main()
{
    int N;

    std::cin >> N;
    std::cout << (isPrime(N) ? "YES" : "NO");
    
    return 0;
}

 

 

이해가 안 간다면 제가 잘못 썼겠죠.  댓글 주세요.