[C] 백준 2960번 : 에라토스테네스의 체
오늘은 소수 구하기 문제를 풀어보았습니다! ٩꒰｡•◡•｡꒱۶
그중 하나는 2960번 에라토스테네스의 체입니다.
https://www.acmicpc.net/problem/2960
2960번: 에라토스테네스의 체
문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에
www.acmicpc.net
에라토스테네스의 체 는 정수 범위 내에서 소수를 찾을 때 흔히 사용하는 방법입니다.
여기서 말하는 소수란 1과 자기 자신만을 약수로 가지는 수입니다. ( 반대로 소수가 아닌 수를 합성 수라고 합니다. )
그럼 주어진 수가 소수인지 합성 수인지 판단하려면,
1과 자기 자신이 아닌 다른 수의 배수가 되는지를 살펴보면 되겠죠?
에라토스테네스의 체 구현은 문제에서 주어진 방법과 같이
소수를 찾고, 그 소수의 배수를 모두 지워나가는 식으로 진행하면 됩니다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int cnt = 0;
int isPrime[1001]; // 0이면 소수, 1이면 합성수
int primeSieve(int n, int k)
{
for (int i = 2; i<= n; i++)
{
if (isPrime[i]==0)
{
cnt++;
if (cnt == k)
return i;
for (int j = i * i; j <= n; j += i)
{
if (isPrime[j] == 0) {
isPrime[j] = 1;
cnt++;
if (cnt == k)
return j;
}
}
}
}
}
int main()
{
int N, K;
scanf("%d%d", &N, &K);
printf("%d\n", primeSieve(N, K));
return 0;
}
저는 위의 코드와 같이 isPrime이라는 배열을 사용하여,
index에 해당하는 수가 소수인지 합성수인 지 구분하였습니다.
원래 에라토스테네스의 체는 실행속도를 줄이기 위해
바깥 for문의 탐색 범위를 2부터 sqrt(N)까지 설정하는 경우가 많습니다.
하지만 이 문제는 소수를 지우는 경우도 고려해야 하기 때문에 2부터 N까지로 설정해 주었습니다.
.
컴퓨터에서 소수는 암호 시스템이나 데이터베이스, 파일 압축 등 다양한 분야에서 사용되고 있습니다.
또한 해시 함수를 설계할 때 충돌을 방지하기 위해 해시 테이블의 크기로 소수를 사용하기도 합니다 !