[C] 백준 2960번 : 에라토스테네스의 체

 

오늘은 소수 구하기 문제를 풀어보았습니다!  ٩꒰｡•◡•｡꒱۶ 

그중 하나는 2960번 에라토스테네스의 체입니다.

 

백준 2960번

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

2960번: 에라토스테네스의 체

 

에라토스테네스의 체 는 정수 범위 내에서 소수를 찾을 때 흔히 사용하는 방법입니다.

여기서 말하는 소수란 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까지로 설정해 주었습니다.

.

컴퓨터에서 소수는 암호 시스템이나 데이터베이스, 파일 압축 등 다양한 분야에서 사용되고 있습니다.

또한 해시 함수를 설계할 때 충돌을 방지하기 위해 해시 테이블의 크기로 소수를 사용하기도 합니다 !