[개념] 에라토스테네스의 체

에라토스테네스의 체는 가장 대표적인 소수(Prime Number) 판별 알고리즘이다.

소수란 '양의 약수를 두 개만 가지는 자연수'를 의미하며 그 말은 결국 1과 자기자신만을 약수로 가지는 자연수이다.

 

 

#include <stdio.h>

bool isPrimeNumber(int x) {
	for(int i=2; i<x; i++) {
    	if(x%i==0) return false; // 1을 제외하고 자기자신을 나눌 수 있는 수가 존재하면 안되니깐
    }
    return true;
}

int main(void)
{
	printf("%d", isPrimeNumber(97));
    return 0;
}

 

위와 같이 알고리즘을 작성하는 경우 소수 판별 알고리즘의 시간 복잡도는 O(N) 이다.

모든 경우의 수를 다 돌며 약수 여부를 확인한다는 점에서 비효율적이다.

사실은 O(N^(1/2))로 손쉽게 계산이 가능하다. 왜냐하면 예를 들어 8의 경우 2*4=4*2와 같은 식으로 대칭을 이루기 때문이다.

그러므로 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 된다.

 

 

#include <stdio.h>
#include <math.h> 
// 제곱근 구하는 라이브러리 import

bool isPrimeNumber(int x) {
	int end = (int) sqrt(x);
	for(int i=2; i<=end; i++) {
    	if(x%i==0) return false; 
    }
    return true;
}

int main(void)
{
	printf("%d", isPrimeNumber(97));
    return 0;
}

다만 이렇게 한 두개의 소수를 판별하는 것이 아닌 대량의 소수를 한꺼번에 판별하고자 할 때 사용하는 것이 바로 에라토스테네스의 체이다. 

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당에 그 인덱스에 해당하는 값을 촥촥촥 넣어준다.

 

예를들어 1부터 25까지 판별한다고 하면

 

① 이차원 배열을 생성하여 값을 초기화한다.

 

 

 

② 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다.

먼저 2의 배수를 지워보자 (자기 자신은 지우지 않는다)

 

 

3의 배수를 지워보자. (자기 자신은 지우지 않는다)

 

 

③  이미 지워진 숫자의 경우 건너 뛴다.

-> 4는 이미 지워져있으므로 지우지 않고 건너 뛴다. 이 과정을 반복한다.

 

 

결과적으로 위와 같이 모두 지워졌다. 

④ 2부터 시작하여 남아있는 숫자들을 출력한다.

 

출력 : 2 3 7 11 13 17 19 23

 

따라서 한꺼번에 성공적으로 소수를 판별하게 되었다.

 

위 과정을 코드화 해보자.

#include <stdio.h>
#include <math.h> 

int number = 100000; // 100000 안에 들어있는 소수를 찾고 싶을 때
int a[100001];

bool primeNumberSieve {  // Sieve: 체
	// 1. 각 인덱스에 값을 할당한다
    for(int i=2; i<=number; i++) {
    	a[i] = i; // 인덱스 번호와 들어가는 값이 맞게 넣어줌
    }
	for (int i=2; i<=number; i++) {
   	// 2. 이미 지워진 숫자의 경우 건너뛴다
    	if(a[i]==0) continue;
    // 3. 자기 자신을 제외하고 배수들을 전부 지워준다.    
        for(int j= i+i; j<=number; j+=i) {
        	a[j]=0;
        }
    }
    // 4. 2부터 시작하여 남아있는 숫자들을 출력한다.
    for (int i=2; i<=number; i++) {
    	if(a[i]!=0) printf("%d",a[i]);
    }    
}

int main(void)
{
	primeNumberSieve();
}

 

---

관련문제

 

백준 3671. 산업 스파이의 편지

 

[문제]

첫째 줄에 테스트 케이스의 개수 c가 주어진다. (1 ≤ c ≤ 200) 각 테스트 케이스는 한 줄로 이루어져 있고, 종이조각에 쓰여 있는 수가 공백없이 주어진다. 종이조각의 수는 적어도 1개, 많아야 7개이다.

 

[출력]

각 테스트 케이스에 대해 종이조각을 적절히 배치해서 만들 수 있는 서로 다른 소수의 개수를 출력한다. 이때, 모든 종이 조각을 사용하지 않아도 된다. (7과 1이 있을 때, 만들 수 있는 소수는 7, 17, 71이다) 종이 조각을 적절히 배치해서 만든 숫자가 0으로 시작할 때, 앞에있는 0을 지운 수가 같으면 같은 숫자이다.

 

 

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<cstring>
 
#define endl "\n"
using namespace std;
 
string Inp; // 종이조각 문자열
bool Select[7]; // 각 종이조각 선택했는지 안했는지에 대한 t/f 값 (최대 7)
int Len, Answer; // 종이조각 문자열 길이
 
vector<char> V;
set<int> Visit;

// 2. 초기화
void Initialize()
{
    Inp.clear();
    Visit.clear();
    memset(Select, false, sizeof(Select)); // false로 전부 초기화
    Answer = 0;
    Len = 0;
    V.clear();
}

// 3. 하나의 테스트 케이스에 대한 문자열 입력 받음
void Input()
{
    cin >> Inp;
    Len = Inp.length(); // 변수 Len에 문자열 길이 저장
}

// 소수인지 판단하는 함수 
bool Calculate(int Data)    
{
    if (Data < 2) return false;
    // 16의 경우 약수는 1 2 4 8 16 
    // => 어짜피 2x8 = 8x2니깐 시간복잡도 줄이기 위해서 i*i로 계산하여 검사
    for (int i = 2; i * i <= Data; i++)
    {
        if (Data % i == 0) return false;
    }
    return true;
}

// 5. vector에 담긴 char 문자들을 합쳐서 숫자로 반환
int SumOf_Vector()
{
    int Sum = 0;
    for (int i = 0; i < V.size(); i++)
    {
        Sum = Sum + (V[i] - '0');
        if (i != V.size() - 1) 
        	Sum = Sum * 10;
    }
    return Sum;
}

// 4. DFS 
void DFS(int Cnt)
{
	// 문자열의 길이보다 크면 반환
    if (Cnt > Len) return;
    if (V.size() != 0)
    {
        int Value = SumOf_Vector();
        // 111, 111 -> 순열 dfs를 했을 때, 이렇게 두 개에 대해서 다 검사할 필요 없으므로
        // 중복 체크하기 위해 set에 담음
        
        // int 형으로 반환된 Value값을 가지고, set에 해당 Value값이 없으면 소수검사
        if (Visit.find(Value) == Visit.end())
        {
            Visit.insert(Value);
            // 6. Value가 소수인지 검사를 통해 소수 갯수를 ++ 해준다.
            if (Calculate(Value) == true) 
            		Answer++;
        }
    }
 	
    // 7. 순열 DFS 
    for (int i = 0; i < Len; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        // 선택한 것이니깐 vector에 집어넣는다.
        V.push_back(Inp[i]);
        DFS(Cnt + 1);
        Select[i] = false;
        V.pop_back();
    }
}
 
void Solution()
{
    DFS(0);
    cout << Answer << endl;
}

// 1. 테스트 케이스 입력받는다.
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

 

 

 

 

 

 

출처

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

https://blog.naver.com/ndb796/221233595886