소수 판별법

• 한 숫자만 검증
  • 기본 최적화
  • $1\sim \sqrt{n}$까지 곱셉 비교 i * i <= n

bool is_prime(int n){
	if ( n <= 1 ) return false;
	if ( n == 2) return true;
	for (int i = 2; i * i <= n; i += 2){
		if (n % i == 0)
			return false;
	}
	return true;
}

• 여러 숫자 검증
  • 에라토스테네스의 체
    • 특정 범위까지 2의 배수... n의 배수 false 판별한 brutal force 배열을 사용