[소수 알고리즘]에라스토테네스의 체.

특정 수가 소수인가를 구하는 문제에서는 좋지 않지만 특정 수까지의 소수를 구하라를 구할때 사용하는 알고리즘이다.

원리는 간단하다. 2부터 시작해서 그 배수를 없애 나가면 된다.

처음을 보자. 2 4 6 8 10~ 순으로 특정수까지 줄여나간다. 

이를 표현하면 for (int i=x*x; i<=N(특정수); i+=x). 마찬가지로 3의 경우도 그 제곱 후에 3씩 더해 없애 나가면 된다.

하지만 이럴 경우 특정 배열을 재방문할수 있으니 bool 배열으로 방문여부를 체크한다. 이를 표현하면

for (int i=x*x; i<=N(특정수); i+=x){

      Map_check[i]=false;

}

이와 같이 실행하는데 실행범위는 위 예시의 경우 11까지다. 왜냐하면 이건 소수의 규칙에서 알수 있는데 소수란 자기자신과 1로만 나눠지는 수이고 우리가 염두해야 할 부분은 소수의 제곱으로 소수가 나탈날수 있다는 것이다. 즉 11의 제곱121은 1,11,121로 나눠지는 수이고 이 경우만 제외해 둔다면 2,3,5..같은 수로 소수 판별이 가능하다.

이걸 적용해보면 

vector check;
	for (int i = 2; i*i <= n; i++) {
		if (!check[i]) continue;
		for (int j = i * i; j <= n; j+=i) {
			check[j] = false;
		}
	}

와 같은 형태로 소수를 구할수 있다.