[Algorithm][BOJ][1654] 소수 구하기

소수 구하기

1. 요구사항 분석
2. 알고리즘 선택
3. 풀이 분석
4. 최적화

요구사항 분석

총 N개의 숫자가 입력됩니다.
이 N개의 숫자들 중 소수를 판별하여 총 개수를 출력합니다.

올라가기

알고리즘 선택

제한된 범위에서 소수를 판별하는데 도움이 되는 에라토스테네스의 체를 사용해보겠습니다.
에라토스테네스의 체를 만드는 방법은 다음과 같습니다.

1. 컨테이너를 제한된 범위만큼 공간을 확보합니다. (인덱스를 사용할 수 있는 컨테이너를 추천)
2. 컨테이너에 인덱스 값과 똑같은 값을 대입합니다.
3. 컨테이너를 순환하면서 해당 값의 배수 인덱스에 접근하면서 0을 대입합니다.
4. 0인 값을 만나면 다음 값으로 넘어갑니다.
   

이렇게 완성된 컨테이너는 소수에 해당하는 인덱스에 접근하면 0이 아닌 값을 저장하고 있습니다.
따라서 주어진 N개의 값을 이 컨테이너 인덱스로 사용해 값이 0인지 아닌지 확인합니다.

올라가기

풀이 분석

#include <iostream>

int main() {
	int* prime = new int[1001];

	prime[1] = 0;
	for (int i = 2; i <= 1'000; ++i) prime[i] = i;
	for (int i = 2; i <= 1'000; ++i) {
		if (prime[i] == 0) continue;
		for (int j = i + i; j <= 1'000; j += i) prime[j] = 0;
	}

	int N, cnt = 0;
	std::cin >> N;
	for (int i = 0, temp; i < N; ++i) {
		std::cin >> temp;
		if (prime[temp]) cnt += 1;
	}

	printf("%d", cnt);
}  

올라가기

최적화

소수를 판별하는데 에라토스테네스의 체를 항상 사용하기에는 문제점들이 있습니다.
먼저 사용하지 않는 소수를 구해야하며, 소수 판별 대상의 숫자가 큰 경우
컨테이너의 크기 또한 매우 커져 손해입니다.
따라서 에라토스테네스의 체가 아닌 다른 방법을 사용하면 더 좋은 성능을 발휘합니다.
대표적으로는

1. 페르마 소수판별법
2. 솔로바이-스트라센 소수판별법
3. 밀러-라빈 소수판별법
   위 외에 여러 방법들이 존재합니다.
   

올라가기