소수판별 → 제곱근까지만 판별하면 된다.★★

#소수인지 판별
def isPrime(x):
    if x ==1: return False
    for i in range(2, int(math.sqrt(x))+1):         #만약에 x가 2라면 for i in range(2,2)가 된다. 그냥 지나감 
        if x % i ==0:
            return False
    else:                         #else는 for문을 정상적으로 다 돌은 경우를 의미한다. 
        return True

 

문제)

검사하려는 숫자가 소수인지여부를 판단하는 방법으로 제곱근(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까지 나누어 떨어지지 않으면 소수가 아니라는 의미이며 큰 수도 몇번의 계산으로 확인가능하다는 장점이 있습니다.

 

출처를 밝힙니다. 

https://www.it-note.kr/308

소수 여부 판단하는 알고리즘 (제곱근 범위 나누기법)