[Python] 소수 찾기 알고리즘 구현(Prime Number)

소수 : 1과 자기 자신을 제외하고 자연수 중 어떤 숫자로도 나누어 떨어지지 않는 숫자

ex) 2,3,4,7...

 

1. 가장 기본적인 알고리즘

def primenumber(x):
    for i in range(2, x):	# 2부터 x-1까지의 모든 숫자
    	if x % i == 0:		# 나눠떨어지는게 하나라도 있으면 False
        	return False
    return True

 

함수 설명 : 숫자x를 2부터 x-1까지의 숫자로 모두 나누어 나눠 떨어지는게 하나라도 있으면 False를 반환, 나눠 떨어지는 것이 없으면 True 반환

-> 숫자가 커지면 매우 비효율적임

 

 

2. 빠른 알고리즘

자연수의 약수에 존재하는 원리 사용

ex ) 25의 경우, 25의 약수는 1, 5, 25이다. 

- 1 x 25 = 25

- 5 x 5 = 25

- 25 x 1 = 25

1과 자기 자신을 제외한 약수를 확인하려면 제곱근까지만 확인하면 된다. 

약수들이 대칭적으로 짝을 이루기 때문에, 5까지만 나눠떨어지는지 확인하면 소수 인지 판별 가능하다. 

 

import math

def primenumber(x):
    for i in range (2, int(math.sqrt(x) + 1):	# 2부터 x의 제곱근까지의 숫자
    	if x % i == 0:		# 나눠떨어지는 숫자가 있으면 소수가 아님
        	return False
    return True

자기 자신의 제곱근(루트)까지 확인한 뒤, 

나누어 떨어지는 숫자가 존재하면 False, 나누어 떨어지는 숫자가 존재하지 않으면 True 반환

 

-> 코딩 테스트 문제에 자주 출제되는데 시간을 효율적으로 줄일 수 있음