JArchive 프로그래밍 일기

문제

소수 찾기 백준 1978번

리뷰

소수는 약수가 1과 자기 자신만 있는 수다.

N이 소수가 되는 조건

2이상이고 루트 N보다 작거나 같은 자연수로 나누어 떨어지는지 확인하면 된다.

N이 소수가 아니라고 가정하자.

소수가 아닌 N은 다음과 같이 표현할 수 있다.

N = a x b ( b는 a보다 큰 어떤 수.)

두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.

따라서 2부터 N까지가 아니라, 2부터 루트 N까지만 검사해보면, 소수인지 여부를 알 수 있다.

a가 루트N보다 크고, b가 루트N보다 크면,

a x b 도 N 보다 크다.

예를 들어 N = 24 이고,  a = 2, b = 12 

2 4 (여기 루트N 자리) 6 8 10 12 14 16 18 20 22 24

루트 24 는 4.xx 와 가까운 수가 될 것이다. 
a와 b 둘 중 하나는 루트 N 보다는 작다. 

코드로 나타내면 다음과 같다.

bool isPrime(int n){

    if(n < 2){
        return false;
    }

    for(int i = 2; i*i <= n; i++){ // 실수는 오차를 발생시킬 수 있으므로, i*i <= N 으로 계산하자.
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

루트i < = N 는 아래와 같다.

i <= N * N

양변을 제곱한다. i의 루트가 사라진다. N은 제곱이 된다.

루트는 실수니까 오차를 발생시킬 수 있으므로 이렇게 제곱을 이용해 실수 사용을 피하는 것이다. 

어떤 수가 소수인지 확인하는데 걸리는 시간 복잡도는 O(루트N) 이다.

코드

#include <iostream> 
using namespace std;

bool isPrime(int n){

    if(n < 2){
        return false;
    }

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

int main(void){

    int CNT = 0;
     int answer = 0;

    cin >> CNT;

    while(CNT--){
        int num = 0;
        cin >> num;
        if(isPrime(num)) answer++;
    }

    cout << answer;
    return 0;    
}