[Python example] 소수 구하기

소수는 1과 자신 이외의 약수를 갖지 않는 정수를 이야기 합니다.
정수를 입력 받아 그 수가 소수인지 아닌지 검사하는 프로그램을 짜 봅시다.

다음과 같이 소수의 정의대로 2에서부터 입력받은 n-1까지 순회하며 나누어 떨어지는지 아닌지 검사하면 간단히 해결됩니다.

import sys
import math

def isPrime(n):
    bPrime = True
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            bPrime = False
            break
    return bPrime

if __name__=="__main__":
    print( sys.version )
    N = input("input a number : ")
    if isPrime(int(N)):
        print("prime number")
    else:
        print("not prime number")
    input("press any key")

실행해 보면 다음과 같이 동작하는 것을 알 수 있습니다.

3.0 (r30:67507, Dec  3 2008, 20:14:27) [MSC v.1500 32 bit (Intel)]
input a number : 30
not prime number
press any key

3.0 (r30:67507, Dec  3 2008, 20:14:27) [MSC v.1500 32 bit (Intel)]
input a number : 13
prime number
press any key

그러나 이 예제에는 약간 비효율적인 면이 있는데요.
소수검사는 2에서부터 n-1까지 할 필요가 없습니다. 2에서부터 sqrt(n)까지만 하면 충분하죠.
즉 아래와 같이 isPrime 함수를 변경하면 속도가 약간 더 빠르게 됩니다.

import math

def isPrime(n):
    bPrime = True
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            bPrime = False
            break
    return bPrime