[C++] 소수(Prime Number) 효율적으로 구하기

 

소수(Prime Number)

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 

소수 (수론) - 위키백과, 우리 모두의 백과사전

 

소수 판별하기 알고리즘

• 어느 수까지 판별하는 수를 나눠서 나머지가 0이 안나오면 소수로 인정
• 소수를 판별하는 가장 효율적인 방법은 해당 숫자의 √N 까지 확인하는하는 것

 

// num가 소수인지 판별
 
// 1) i의 제곱근으로 판단
bool prime_number(int num) {
    bool isDisimal = true;
    for(int i = 2; i*i <= num; i++) {
        if(num % i == 0) {
            // not prime_number
            isDisimal = false;
            break;
        }
    }
 
    return isDisimal;
}
 
// 2) sqrt 함수 사용
#include <cmath>
bool prime_number(int num) {
    bool isDisimal = true;
    for(int i = 2; i <= sqrt(num); i++) {
        if(num % i == 0) {
            // not prime_number
            isDisimal = false;
            break;
        }
    }
    return isDisimal;
}

 

동일한 결과이므로 편한 방식으로 사용하면 됩니다.

for(int i = 2; i*i <= num; i++)
for(int i = 2; i <= sqrt(num); i++)