Sieve of Eratosthenes

✔️ 에라토스테네스의 체

◾ 숫자들을 순차적으로 접근하면서, 각 숫자의 배수에 해당하는 숫자들을 걸러냄으로서 소수를 찾아내는 방법이다.  

◾ 참고로 에라토스 테네스의 체 시간복잡도는 O(n log log n) 이다. (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)

에라토스테네스의 체

💾 소스

#include<cmath>
#include<vector>
using namespace std;
const int MAX = 1000;

int main() {
	vector<int> prime;
	bool isPrime[MAX + 1];
	memset(isPrime, true, sizeof(isPrime));

	for (int i = 2; i <= MAX; i++) {
		if (isPrime[i]) prime.push_back(i);

		for (int j = i * 2; j <= MAX; j += i) {
			isPrime[j] = false;
		}
		
	}

	for (int i = 0; i < prime.size(); i++) {
		printf("%4d", prime[i]);
	}

}

---

✔️ 소수 구하는 함수 1

◾️ O(N) 시간에 소수를 판별할 수 있다. 

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

bool isPrime(int num) {
	if (num == 1 || num == 0) return false;

	for (int i = 2; i < num; i++) {
		cout << i << endl;
		if (num % i == 0) return false;
	}

	return true;
}

int main() {
	
	if (isPrime(997))
		cout << "소수 입니다.";
	else
		cout << "소수가 아닙니다.";

	return 0;
}

---

✔️ 소수 구하는 함수 2

◾️ O(√N) 시간에 소수를 판별할 수 있다.

◾️ 루트 N보다 큰 약수가 존재하면, 루트 N보다 작은 약수가 존재한다. (귀류법)

◾️ N이 소수가 아니라면 어떤 a,b에 대해서 N = a x b 관계가 성립할 것이다.

◾️ a, b 두 수중 하나의 수가 루트 N이상이면, 다른 하나의 수는 루트 N이하여야 두 수의 곱이 N이 될 수 있다.

◾️ 따라서 우리는 루트 N이하의 수까지만 나누어 떨어지는지 확인하면 된다. 

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

bool isPrime(int num) {
	if (num == 1 || num == 0) return false;

	for (int i = 2; i <= sqrt(num); i++) {
		cout << i << endl;
		if (num % i == 0) return false;
	}

	return true;
}

int main() {
	
	if (isPrime(997))
		cout << "소수 입니다.";
	else
		cout << "소수가 아닙니다.";

	return 0;
}

 

소수 구하는 함수 2 결과