인프런 커뮤니티 질문&답변

안녕하세요 대기업님 ㅎㅎ

bool check(int n) { 
    if(n <= 1) return 0;
    if(n == 2) return 1; 
    if(n % 2 == 0) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

앞의 코드를 말씀하시는 건데요.

저 for 반복문은 배수인 것, 즉 소수가 아님을 찾아 0을 반환하는 반복문입니다.

제 생각에는 왜 i * i 를 하냐 이부분이 궁금하신 것 같은데요.

예를 들어 18이라는 숫자는 2 * 9로 되어있습니다. 2의 배수이면 소수가 아니죠.

이 때 9까지 갈 필요도 없습니다. 9 * 2 네? 하면서 소수가 아니네 라고 할 필요도 없이

이미 2에서 2 * 9로 소수가 아님이 증명되기 때문에 9까지는 안가고 2에서 배수임을 판독할 수 있습니다.

이것을 일반화를 시켜볼게요.

어떠한 수 n = i * k라고 해보죠.

케이스는 3가지로 나눠지게 됩니다.

k > i

이 때는 i의 배수임을 확인하면 되기 때문에 k까지 갈 필요가 없습니다. i에서 모듈러 해서 배수면 return 0이 되죠.

k == i

이 경우가 가장 많이 for반복문이 작동되는 순간입니다. 예를 들어 121을 예로 들어보면, 121 = 11 * 11이라는 값을 가집니다. 즉, 11까지 가야 11의 배수임을 확인할 수 있습니다. 그리고 그 다음 숫자인 12는 확인할 필요가 없습니다. 이미 배수임을 확인하고 return 0을 하게 됩니다.

k < i

이 경우에는 i를 탐색하기 전에 k를 탐색하기 때문에 그 전에 return 0을 탐색하고 끝이 납니다.

그렇기 때문에 i * i <= n 만으로 "배수"임을 확인할 수 있게 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.