[알고리즘] 백준 1929번: 소수 구하기 (C++), 에라토스테네스의 체

알고리즘 문제에서 소수에 관한 문제를 보면 1차적으로 에라토스테네스의 체를 떠올리게 된다.

허나, 에라토스테네스의 체를 잘못 알고 있었기 때문에 블로그의 정리를 해두려한다.

(이름 외우는게 젤 어려워.. 아리토스테네스 아레스토테네스...)

 

기존에 잘못 알고있었던 건

어떤 정수 N이 있을 때 2부터 N까지 소수를 구하려면

2부터 N의 제곱근까지 범위를 주면된다.

이까지만 알고 범위 안에서 뭘 하는지 생각하지 않고 있었다.

물론 소수를 구할 때 N의 제곱근까지만 범위를 준다는게 시간을 조금이라도 줄여주는 것은 존재하는 내용이다.

---

에라토스테네스의 체

2~정수 N까지의 소수를 구한다고 했을 때

에라토스테네스의 체를 몰랐다면 2~N 사이의 값 i를 i 이하 수들로 나누어보며 소수인지 아닌지 판별했을 것이다.

이런 알고리즘은 에라토스테네스의 체에 비해 상당히 긴 시간을 잡아먹는다.

에라토스테네스의 체의 원리는 이렇다.

N = 50일 때

4부터 2를 제외한 2의 배수를 지워준다.

2는 1과 자신으로만 나누어지는 소수이기 때문이다.

그리고, 어떤 수가 다른 어떤 수(1을 제외)의 배수라는 것은 소수가 아니기 때문이다.

마찬가지로 3을 제외한 3의 배수를 지워준다.

4는 지워졌으니 5로 넘어간다.

이 반복을 어디까지 하냐고 생각했을 때 'N이 50이니 50까지 해야하는 것인가'라고 생각할 수 있다.

특정한 수의 제곱근으로도 충분히 구할 수 있기 때문에 50까지 할 필요 없고, 50의 제곱근까지 범위를 잡고 50의 제곱근의 배수들을 지워내면 된다.

최종적으로 50의 제곱근까지 했을 때 남아있는 소수들이다.

허나, 아직 1이 남아있는데 1은 합성수도 소수도 아닌 수이기 때문에

문제를 풀 때 범위 안에 1을 포함시키지 않거나 기저 사례로 1을 잡아주어야 한다.

이렇게 남아있는 수들이 50 범위 안에 있는 소수가 된다.

---

문제 풀이

#아래 코드는 C++로 작성되었다.

void isPrime(int m, int n) {
	vector<int> num;
	for (int i = 0; i <= n; i++) {
		num.push_back(i);
	}
	
    // 소수가 아닌 배수들에 0을 넣음으로써 없앰
	for (int i = 2; i <= sqrt(n); i++) {// n의 제곱근까지만 배수들을 확인
		if (num[i] == 0) {
			continue;
		}

		for (int j = i * 2; j <= n; j += i) {
			num[j] = 0;
		}
	}

	if (m <= 1) {// 기저 사례: m이 1일 경우 1은 소수가 아니기 때문에
		m = 2;
	}

	for (int i = m; i <= n; i++) {
		if (num[i] != 0) {
			cout << num[i] << '\n';
		}
	}
}

void를 리턴형으로 두고 바로 cout으로 M~N 범위 내에 소수들을 출력하게 해주었다.