에라토스테네스의 체

소수를 찾는 아주 기가막힌 알고리즘

에라토스테네스의 체!

#include <iostream>
using namespace std;

int n = 1000;
bool a[1000];
void PrimeNumber()
{
	for (int i = 2; i < n; i++)
		a[i] = true;

	for (int i = 2; i < n; i++)
	{
		if (a[i] == false) continue;
		for (int j = i * 2; j < n; j += i)
			a[j] = false;
	}
	for (int i = 2; i < n; i++)
		if (a[i]) cout << i << " ";
}
int main()
{
	PrimeNumber();
	return 0;
}

소수를 찾는 기가막힌 방법!

1. 배열을 true로 초기화 한다! ( 0, 1 제외 )

2. 2부터 시작해서 모든 배수에 false 값을 넣는다!

3. true값을 가지고 있는 애들이 전부 소수!

 

끝!