에라토스테네스의 체

에라토스테네스의 체

테네스형

이분은 아주 대단하신 분이에요.

지구의 크기를 처음으로 계산하신 분이며 소수를 걸러내는 에라토스테네스의 체를 고안한 사람이기도 합니다.

그래서 우리는 에라토스테네스의 체를 배울 건데

소수가 아닌 값들에 대한 bool 배열을 만들어서 소수만을 걸러낼 수 있는 방법이 있습니다.

 

어우 저게 뭔소리냐.

우리가 아는 소수는 3.141592 뭐 이런거지만

소수

2를 나누었을 때 1과 2밖에 없죠?

3의 약수는요? 3도 똑같죠 1과 3

53의 약수는요?

똑같습니다 1과 53

이런 것들을 소수라고 합니다.

 

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 40;
bool che[MAX + 1];

vector<int> Eratosthenes(int max)
{
    vector<int> vec;
    for (int i = 2; i <= MAX; ++i)
    {
        // 만약 che라는 배열에 값이 true라면 continue
        if (che[i]) continue;
        // 4부터 시작해서 소수를 체크
        // 증감식은 += i이기에 2씩 증가 4, 6, 8, ...
        for (int j = 2 * i; j <= MAX; j += i)
        {
            // 이 값들은 다 소수가 아님
            che[j] = 1;
        }
    }
    
    // 1은 소수가 아니니 2부터 시작한 값들을 넣음
    for (int i = 2; i <= MAX; ++i)
    {
        // 만약 값이 0이라면 소수임
        if (che[i] == 0)
            vec.push_back(i);
    }
    
    return vec;
}

int main()
{
    vector<int> vec = Eratosthenes(MAX);
    for (int i : vec)
        cout << i << " ";
}

 

 

여기서 소수들을 체크하는 방법은 아래 코드를 보면서 해석하면 됩니다.

 

    for (int i = 2; i <= MAX; ++i)
    {

        if (che[i]) continue;

        for (int j = 2 * i; j <= MAX; j += i)
        {
            che[j] = 1;
        }
    }

 

 

여기서 i는 2부터 시작합니다 1은 소수가 아니기 때문이죠.

i가 2부터 시작할 때 2에 2를 곱한 값들은 다 소수가 아니죠 2로 나누어지기 때문입니다.

그래서 4부터 시작해서 40까지 의 값들을 다 1 즉 true로 바꿔주는 거죠

그렇다면 i가 3일때도 똑같습니다.

i가 3일 때 j는 3에서 2를 곱해서 시작합니다.

증감식을 통해 i가 3이니 3을 더해서 3에 관련된 약수들을 다 true로 바꿔줍니다.

그래서 i가 증가할 때마다 4도 똑같고 5도 똑같고 6도 ....똑같은 방식으로 진행이 될때

2로 시작했을 때 2는 4부터 시작하니 2는 소수

3도 똑같습니다.

여기서7이 되었을 때도 j는 7부터 시작이 아닌 2를 곱한 14부터 시작합니다.

 

이렇게 소수를 구별할 수가 있습니다.

 

하지만 이는 배열의 크기가 필요하기 때문에 배열의 크기가 일정 수준을 벗어나면 쓰기가 힘들어져요.

예를들어 1000만이라는 값이 들어오면 배열을 쓰기가 힘들어집니다.

 

그래서 이와 같이 1000만을 넘었을 때는 소수를 판별하는 bool함수를 따로 만들어 주어야 합니다.

 

#inlcude <iostream>

using namespace std;

bool check(int n)
{
    // n이 1이거나 그 이하면 종료
    if (n <= 1)
        return 0;
        
    // n이 2이면 소수니 1을 반환하고 종료
    if (n == 2)
        return 1;
        
    // n이 2로나누어지면 소수가 아니기에 0을 반환하고 종료
    if (n % 2 == 0)
        return 0;
        
    // 2는 위에서 자체적으로 소수를 판단하는 조건을 걸어놨으니 3부터 시작한다.
    for (int i = 3; i * i <= n; ++i)
    {
        if (n % i == 0) return 0; 
    }
    
    return 1;
}

int main()
{
    for (int i = 1; i <= 20; ++i)
    {
        if (check(i))
        {
            cout << i << '\n';
        }
    }
    return 0;
}

 

이와 같이 소수를 뽑아내는 방식이 있습니다.

    for (int i = 3; i * i <= n; ++i)
    {
        if (n % i == 0) return 0; 
    }

이 코드가 잘 이해가 안갈 수도 있는데

3이 들어왔을 때 이 반복문의 조건을 검사하겠지만 애초에 2로나누어지는 수들은 이 반복문에 들어오지 않습니다.

그래서 7같은 게 들어오면 이 때 반복문의 조건을 검사하는데 3 * 3(i * i)는 9이기 때문에 조건에 맞지않아 바로 반복문을 종료해 1로 반환하고 예를 들어 19가 들어온다면 위에 조건들은 다 무시하게 되고 반복문으로 들어와 i가 3부터 시작해 조건을 검사하게 되죠 19는 3으로 안나뉘어지니 ++i를 하게 되면 4일때 조건도 맞습니다 4 * 4 = 16이기 때문에 19보다 작아 검사를 한 번 더하게 되는데 19를 16으로 나누어도 0이 아니기 때문에 1을 반환하죠.

이런식으로 소수를 뽑아낼 수 있습니다.

3의 제곱

7의 제곱

2로 안나누어지는 홀수들을 곱조건을 통해 나머지 수들의 소수를 뽑아내죠.

 

 

어려우면 한 번 디버깅해서 확인해보시는 것을 추천드립니다!

끄으읕