소수 판별 알고리즘

- 우선 2를 제외한 모든 짝수들은 소수가 아니다라는 점

- 만약 N이 합성수라면 N = a * b형태이므로(a > 1 && b > 1), a와 b 둘 중 하나는 sqrt(N)보다 작거나 같음을 알 수 있다.

그러므로 N을 2부터 sqrt(N)까지 나눠보아 나누어지지 않으면 N은 소수가 된다. 

다음은 2부터 N까지 소수를 구하여 prime이라는 배열에 반영하는 코드의 핵심 함수이다.

void check_prime(int number){
    for (int i = 2; i <= number; i++){
        if (i % 2 == 0 && i != 2){
            prime[i] = 0;
            continue;
        }
        bool isPrime = true;
        for (int j = 2; j*j <= i; j++){
            if (i % j == 0){
                isPrime = false;
                break;
            }
        }
        if (isPrime) prime[i] = 1;
    }
}