에라토스테네스의 체는 가장 대표적인 소수(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();
}
관련문제
[문제]
첫째 줄에 테스트 케이스의 개수 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
'알고리즘' 카테고리의 다른 글
[개념] 플로이드 와샬 (Floyd Warshall) / 백준 11404 (0) | 2020.01.27 |
---|---|
[개념] Bit연산 (0) | 2020.01.18 |
[개념] 조합, 순열 + DFS,BFS (1) | 2020.01.16 |
[개념] 그래프 이론 (0) | 2020.01.15 |
[개념] 버블정렬, 선택정렬 (0) | 2020.01.13 |