[C++]1929번: 소수 구하기

단순하게 반복문을 돌려서는 시간초과가 난다.

 

시도 1) 나누기 검사 범위를 주어지는 값 a의 절반까지만 수행하기

bool isPrime(int a) {
    if(a == 1) {
        return false;
    } else {
        for(int i = 2; i < a/2; i++) {
            if(a % i == 0) {
                return false;
            }
        }
    }
    return true;
}

어림없지! 시간초과

시도 2) 2의 배수 배제하기

bool isPrime(int a) {
    if(a == 1 || a % 2 == 0) {
        return false;
    } else {
        for(int i = 3; i < a/2; i+=2) {
            if(a % i == 0) {
                return false;
            }
        }
    }
    return true;
}

 1 검사문에 짝수인지도 검사하게끔 했다.

이후 나누기 검사할때도 짝수는 배제할 수 있도록 i값을 +2씩 올렸다.

ㅠㅠ

 

시도 3) 구글링

시도 1에서 나는 a/2로 범위를 제한했었는데, 이를 제곱근 범위로 제한해도 된다. 

a의 제곱근 x a의 제곱근 = a가 되는데, 여기서 a의 제곱근을 넘는 수가 되는 순간부터 확인하는 것이 의미가 없어지기 때문.

bool isPrime(int a) {
    if(a == 1 || a % 2 == 0) {
        return false;
    } else {
        for(int i = 3; i * i < a+1; i+=2) {
            if(a % i == 0) {
                return false;
            }
        }
    }
    return true;
}

범위를 바꿔서 진행하니, 더 이상 시간초과가 뜨지는 않았고, 틀렸습니다가 나옴.

문제는 생각보다 근처에 있었다...생각해보면 당연했군 ㅠㅠ

2도 소수인데

    if(a == 1 || a % 2 == 0) {
        return false;
    }

여기서 소수가 아니라고 하고 넘어가버린다.

    if(a == 1 || a % 2 == 0) {
        if(a == 2) {
            return true;
        }
        return false;
    }

그래서 내부에서 a가 2라면 true를 반환하도록 추가로 코드를 썼다.

이렇게 조건 자꾸 덕지덕지 붙이는거 별로 안좋아하는데 ㅜㅜ 어쩔 수 없는 듯.

 

*) 궁금해서 시도 1의 범위만 제곱근으로 설정하여 다시 돌려봤다.

진짜 제곱근이 문제였나보다.