백준 1929 : 소수 구하기

★★☆☆☆

기존에 알고 있는 소수의 정의에 따라 코드를 짜면 되는 문제

<나의 풀이>

#include <iostream>
#define MAXSIZE 1000001
using namespace std;

int main() {
	int m, n;
	cin >> m;
	cin >> n;

	int array[MAXSIZE] = { 0, };

	for (int i = 2; i <= n; i++) {
		for (int j = 1; i*j <= n; j++) {
			array[i*j]++;
			//cout << i * j << " : " << array[i*j]<<"\n";
		}
	}

	//cout << "결과 ----------" << "\n";
	for (int i = m; i <= n; i++) {
		if (array[i]==1) cout << i<<"\n";
	}
}

소수는 1과 자기 자신으로밖에 나누어지지 않는 숫자이므로 나눈다고 생각하기 쉽지만,
나누어서 접근할 경우 매 숫자마다 계속해서 나누어주어야 하므로 비효율적이다.
따라서, 역으로 2부터 배수에 해당하는 숫자들을 제외하는 방식으로 풀었다.
(메모리를 많이 먹게 되므로, 상황에 따라서는 나누는 방식도 써야할 것이다)

2부터 배수를 체크했을 때, 소수는 1과 자기 자신만을 약수로 가지므로, 배수의 값은 1이어야 한다.
따라서 출력 시에 1인 경우만 측정하여 출력한다.(1은 소수가 아니므로, 0인 경우는 포함되면 안된다)

다른 사람의 풀이

https://cryptosalamander.tistory.com/28

에라토스테네스의 체를 활용하여 문제를 풀었다.
에라토스테네스의 체는, 그 숫자의 제곱근값까지의 배수 값을 제외하다보면 소수만이 남는다는 것이다.

배열 또한 나처럼 int값이 아닌 bool 값을 사용하였기 때문에 더 효율적이다.