파이썬 소수판별 프로그램

목차

없음

본문내용

소수란 무엇인가? 그리고 컴퓨터에서 어떻게 구현하면 효율적인가에 대한 내용(파이썬을 이용)으로 소수 판별하는 프로그램을 파이썬에서 만들어보고 좀 더 효율적 방안을 소개한다.

소수의 정의 : 1보다 큰 수 정수 중에서 자기자신과 1로만 나누어 떨어지는 수(예 : 2, 3, 5, 7, 11, 13, 17, 19 ...)

방법1. 위 정의에 입각하여 파이썬으로 간단하게 수학적 정의를 바탕으로 소수를 판별하는 함수를 만들어보자.

def is_prime(n):
if n == 1:
return False
for d in range(2, n, 1): # in range(2, n)과 같다. 2부터 n-1까지 1씩 증가시킨다는 뜻이다.
if n % d == 0:
return False
return True

위 함수를 테스트 해보자

for n in range(1, 10000): # 1만까지 소수가 여부를 True, False로 표시
print(n, is_prime(n))

프로그램을 돌려보면 위 함수는 동작을 잘 한다.
얼마나 효율적인지 시간을 재보자.

방법 2. 이제는 좀 똑똑한 방법으로 찾아보자.
예를 들어 n = 18인 경우, 위 1.번 방법대로 나눈다면
2 * 9
3 * 6
(4는 18을 나누었을 때 정수가 안되므로 넘어감)

참고 자료

없음