(파이썬) 소수판정

 

 

import math

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

if __name__ == "__main__":
	yn = "y"
	while yn == "y" or yn == "Y":
		n=input("소수인지 확인하고 싶은 수는? ")
		if primecheck(int(n)):
			print("%d는(은) 소수입니다." % int(n))
		else:
			print("%d는(은) 합성수입니다." % int(n))
		yn = input("계속 확인하시겠습니까?(y/n)")

일단 $1$ 은 소수가 아니고 $2$ 와 $3$은 소수임을 알려 준다.

$2$ 를 제외한 모든 소수는 홀수 이므로 $2$ 의 배수는 소수가 아님을 알려 준다.

$2$ 의 배수가 아닌 수 $n$ 에 대해서는 $3$ 부터 $\left [ \sqrt{n} \right ]$  까지의 수 중 홀수들로 $n$ 을  나누어 보아 나누어 떨어지는 것이 있으면 $n$ 은 소수가 아닌 것으로, 나누어 떨어지는 것이 없으면 $n$ 은 소수로 판정한다. (단, $[x]$ 는 $x$ 보다 크지 않은 최대 정수를 나타낸다.)

$\left [ \sqrt{n} \right ]$ 보다 큰 수 중 나누어 떨어지는 것이 있다는 것은 그 몫이 반드시 $\sqrt{n}$ 보다 작은 쪽에 있을 것이기 때문에, $\left [ \sqrt{n} \right ]$ 보다 큰 수에 대해서는 생각할 필요가 없다.