소수

소수는 약수가 자기 자신과 1밖에 없는 수.

소수 구해보기 #1

N이 소수이려면, 2 <= x <= N-1인 x로 나누어 떨어지면 안됨.

bool getIsPrime(int x) {
    if(x < 2) return false;

    for(int divider = 2; divider < x; divider += 1) {
        if(x % divider == 0) {
            return false;
        }
    }
    return true;
}

소수 구해보기 #2

N이 소수가 되려면, 2 <= x <= N/2인 자연수로 나누어 떨어지면 안된다. 이유는 N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같ㄹ기 때문이다.

N = a*b인데, a가 작을수록 b는 크다. 가능한 a중에서 가장 작은 값은 2이기 때문에 b는 N/2를 넘지 않는다.

bool getIsPrime(int x) {
    if(x < 2) return false;

    for(int divider = 2; divider <= x/2; divider += 1) {
        if(x % divider == 0) {
            return false;
        }
    }
    return true;
}