[C++] 소수 판별하기

숫자 n 을 소수로 판별하는 방법

n 을 2 부터 n-1 까지의 모든 수로 나눴을 때 나누어 떨어지지 않으면 소수로 판정

처음부터 끝까지 for문으로 돌려서 확인하는 방법을 떠올리기 쉽지만 이는 시간 복잡도 O(N) 으로 비효율적인 방법

대안: 해당 숫자의 √N 까지 확인

✏️ 약수의 중심을 구하는 방법

for(int i=2; i*i<=num; i++){
            if(num % i == 0) return false;
}

약수의 중간값까지만 나머지를 확인해서 소수를 판별
시간 복잡도: O(√N)