<알고리즘> 에라토스테네스의 체

에라토스테네스의 체는 소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르게 구하는 방법이다.

1번으로 bool 배열로 처리하면 개수만큼 늘어나서 1000만을 넘게 되면 쓰기가 힘들다. 그래서 2번으로 해주기도 한다.

 

 

1. bool 배열로 처리

---

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool che[50];

void print(vector<int> vec)
{
	for (int it : vec)
		cout << it << " ";
	cout << endl;
}

vector<int> era(int mx_n)
{
	vector<int> v;
	for(int i = 2; i <=mx_n; i++)
	{
		if(che[i]) continue;
		// 1로 곱해지는 것을 제외한 모든 것들을 빼버림
		for(int j = 2*i; j < mx_n; j += i)
			che[j] = 1;
	}
	for (int i = 2; i < mx_n; i++) if(che[i] == 0) v.push_back(i);
	return v;
}

int main()
{
	print(era(50));
	return 0;
}

/*
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
*/

 

 

 

2. 일일히 소수 판별 처리

---

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;


bool check(int n)
{
	if (n == 2)
		return true;

	if (n <= 1 || n % 2 == 0)
		return false;

	for (int i = 2; i * i <= n; i++)
		if (n % i == 0) return false;

	return true;
}


int main()
{
	for (int i = 0; i < 50; i++)
		cout << i << " " << boolalpha << check(i) << endl;
	return 0;
}