반응형

문제)

검사하려는 숫자가 소수인지여부를 판단하는 방법으로 제곱근(sqrt) 범위 나누기법으로 구현하시오.

 

소수란? 

1과 자신 이외의 숫자로는 나누어지지 않는 자연수 (1은 소수가 아님)

 

제곱근(sqrt) 범위 나누기법이란? 

소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다는 방법으로 검사할 데이터를 제곱근 개 이하로 줄 일 수 있는 방법입니다.

 

예). 18로 예를들면,

18의 약수는 1, 2, 3, 6, 9, 18이며,

18은 1 * 18, 2 * 9, 3 * 6   < √18 >   6 * 3, 9 * 2, 18 * 1입니다.

18  * 18도 18인데, 이 18을 좌우로 곱하기가 대칭이므로 sqrt()값보다 같거나 작은 숫자로 나누어지면 그 이후에 대해서는 대칭이므로 계산을 할 필요가 없다는 원리로 검사하려는 수의 제곱근 값 이하의 수만큼 체크하면 되는 기법입니다. 18의 값은 4.2426... 이므로 4까지 나누어 떨어지지 않으면 소수가 아니라는 의미이며 큰 수도 몇번의 계산으로 확인가능하다는 장점이 있습니다.

 

답은 아래에... ↓


 

 

 

 

 

 

스스로 풀어보시고... ↓

 

 

 

 

 

 

 


 

 

 

아래 답과 비교해보세요. ↓

 

 

 

 

 

#include <math.h>

int is_prime_number(int num)
{
    int    r = 1, sw = 0;
    double sqrt_value = sqrt(num);
    
    do {
        r++;
        if(r > sqrt_value) {
            sw = 1;
        }
    } while(num % r != 0 && sw == 0);
    
    return sw;
}

 

반응형
블로그 이미지

자연&사람

행복한 개발자 programmer since 1995.

,