에라토스테네스의 체

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> arr(40);
	for(int i = 0;i<arr.size();i++)
	{
		arr[i]=1;
	}
	for(int i = 2;i<arr.size();i++)
	{
		for(int j =i*i;j<arr.size();j=j+i)
		{
			
			arr[j] = 0;
		}
	}
	for(int i = 2;i<arr.size();i++)
	{
		if(arr[i]==1)
		{
			cout << i;
		}
	}
}

 

소수를 판별할떄 에라토스테네스의 체 방식을 사용하지않으면 대부분의 코테 문제가 시간초과가 발생한다...

소수판별은 무조건 이 알고리즘을 사용하자