소수는 1보다 큰 자연수중에서 1과 자기자신을 제외한 자연수로는 나누어떨어지지 않는 수.

소수 판별을 위해서 2부터 x-1까지의 모든 수를 통해 나누어지는지 확인해보는 방법도 있지만

약수의 성질을 이용하면 시간복잡도를 반으로 줄일 수 있다

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸.

• 그러므로 가운데 약수(제곱근)까지만 수행하면 됨.

• 예) 16을 확인할때, 8로 나누어떨어지려면 2로 나누어 떨어져야 하기 때문

  

import math

def is_prime(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x % i ==0:
            return False
    return True

print(is_prime(3631))