[알고리즘] cpp 소수를 찾는 방법 에라토네스 체

 

	#include <iostream>
	#include <cstring>
	#define MAX 1000000
	using namespace std;
	bool isPrime[MAX + 1];
	int num, t, T;
	void Eratosthenes(int n) {
	memset(isPrime, 1, sizeof(isPrime)); //init
	for (int i = 2; i * i <= n; i++) {
	if (!isPrime[i]) continue;
	for (int j = i + i; j <= n; j += i) {
	isPrime[j] = 0;
	}
	}
	}
	int main() {
	Eratosthenes(MAX);
	cin >> t;
	while (t--) {
	T++;
	cin >> num;
	cout << "Case #" << T << "\n";
	if (isPrime[num]) {
	cout << "YES" << "\n";
	} else {
	cout << "NO" << "\n";
	}
	}
	return 0;
	}

view raw main.cpp hosted with ❤ by GitHub