[알고리즘] 에라토스테네스의 체(c++)구현 및 문제풀이 - 코딩기록

에라토스테네스의 체는 소수를 찾는 방법 중 하나로 범위 안에 있는 소수들을 모두 구해야 할 때 유용하게 사용되는 알고리즘이다. 

원리

소수는 1과 자기 자신만을 약수로 가지는 수이기 때문에 약수의 개수가 2개이고 합성수는 소수가 아닌 수를 말하기 때문에 약수의 개수가 2개보다 많다.

이 사실을 통해 소수에 어떤 수를(1 제외) 곱하게 되면 그 수는 반드시 합성수가 된다는 것을 알 수 있다. 이것이 에라토스테네스의 체 알고리즘의 핵심 아이디어이다.

 

에라토스테네스의 체-위키백과

코드

일단 우리의 목표는 2부터 100까지에 해당하는 모든 소수를 구하는 것이다.

우리가 처음 만나는 수를 2라고 가정해보자. 그렇다면 소수인 2에 어떤 수를 곱하면 그것은 합성수일 것이다. 즉, 4, 6, 8, ... 50, ..., 100(2에 어떤 수를 곱한 수)는 소수에서 제외할 수 있는 것이다. 약수의 개수가 2개보다 많아지기 때문이다.

 

그 다음 수인 3을 만났다. 3은 소수이므로 3에 어떤 수를 곱하면 그것은 합성수이므로 소수에서 제외할 수 있다. 위와 같은 원리로 작용한다.

이 과정을 반복하면 합성수가 걸러지고 소수만 남게 된다. 이렇게 합성수를 고르는 과정을 배열에 0과 1을 집어넣음으로써 코드로 구현할 수 있다.

#include <iostream>
using namespace std;
bool primes[100]={1,1};
//0과 1이 소수로 체크되는 경우를 방지하기 위해 primes[0],primes[1]을 1로 초기화
int main()
{
    for(int i=2;i*i<=100;i++)
    {
        if(primes[i]==0)//만약 소수를 만난다면
        {
            for(int k=i*i;k<100;k+=i)//소수에 어떤 값을 곱하더라도 합성수이므로
            {
                primes[k]=1;//범위 내에 있는 k의 배수들을 모조리 1로 체크
            }
        }
    }
    //만약 primes[i]==0이라면 i는 소수
    for(int i=1;i<=100;i++)
    {
        if(primes[i]==0)
        {
            printf("%d ", i);//출력
        }
    }
    return 0;
}

실전 적용 문제

주석을 따라가보면 코드가 이해가 될 것이다. 하지만 이 코드를 실전에 다시 적용하는 것은 또다른 문제이다. 백준 1929번 <소수 구하기> 문제와 백준 9020, 6588번 <골드바흐의 추측> 문제가 이 알고리즘을 연습하기에 좋은 문제라고 생각한다. 이 문제들을 풀다 보면 어느 정도 감이 잡힐 거라 생각한다.

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

1929번: 소수 구하기

#include <iostream>
using namespace std;
bool primes[1000001]={1,1};
int M,N;
int main()
{
    scanf("%d %d",&M,&N);
    for(int i=2;i*i<=N;i++)
    {
        if(primes[i]==0)
        {
            for(int k=i*i;k<=N;k+=i)
                primes[k]=1;
        }
    }
    for(int i=M;i<=N;i++)
    {
        if(primes[i]==0)
        {
            printf("%d\n", i);
        }
    }
    return 0;
}

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

9020번: 골드바흐의 추측

#include <iostream>
using namespace std;
int N,a;
bool prime[10000]={1,1};
int main()
{
    for(int j=2;j*j<=10000;j++)
    {
        if(prime[j]==0) 
          for(int k=j*j;k<=10000;k+=j)
          	prime[k]=1;
    }
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        scanf("%d",&a);

        for(int j=a/2;j>=2;j--)//두 소수의 차이가 가장 작은 것을 출력해야 하므로
        {
            if(prime[j]==0 && prime[a-j]==0)
            {
                printf("%d %d\n", j, a-j);
                break;
            }
        }
    }
    return 0;
}