파이썬(Python) - 소수 찾기 알고리즘 구현하기(Prime Number)

코딩테스트를 공부하거나 준비하다보면 특정 숫자가 소수(Prime Number)인지 아닌지를 판단해야할 때가 있다.

소수는 1과 자기자신을 제외하면 자연수 중에서 어떤 숫자로도 나누어 떨어지지 않는 숫자를 말한다.

예를들면, 3, 5, 7 같이 말이다. (1은 소수에 포함되지 않는다)

 

일단 특정 숫자 x가 소수인지 확인하는 가장 간단한 방법은

2에서부터 x-1 까지 모든 숫자를 x에 나눠보고 나눠떨어지는게 있는지 없는지를 확인하는 방법이다.

# 특정 숫자 x가 소수인지 판별하는 가장 기본적인 알고리즘
def primenumber(x):
    for i in range(2, x):	# 2부터 x-1까지의 모든 숫자
    	if x % i == 0:		# 나눠떨어지는게 하나라도 있으면 False
        	return False
    return True				# 전부 나눠떨어지지 않으면 True

위처럼 코드를 작성하면 손쉽게 소수를 찾을 수 있다.

다만, 이 경우는 확인하려는 숫자가 커지면 커질수록 굉장히 비효율적이다.

 

 

더 빠르고 효과적인 방법

---

 

그렇다면 더 빠르게 소수를 판별하는 방법은 무엇일까?

바로 자연수의 약수에 존재하는 원리를 사용하면 된다.

 

예를 들어서 설명하자면,

25의 약수는 1, 5, 25이다.

이는 다음과 같이 앞뒤로 짝을 지을 수가 있다.

1 x 25 = 25

5 x 5 = 25

25 x 1 = 25

1과 자기자신을 제외한 약수가 존재하는지 확인하려면, 자기자신의 제곱근(루트)까지만 확인하면 된다는 뜻이다.

어차피 약수들이 대칭적으로 짝을 이루기 때문에.

그러므로 25의 절반인 즉 루트25인 5까지만 나눠떨어지는지 확인하면 해당 숫자가 소수인지 아닌지를 알 수 있다.

 

이해를 돕기 위해서 다른 예를 살펴보자.

8의 약수는 1, 2, 4, 8 이다.

이는 다음과 같이 앞뒤로 짝을 지을 수가 있다.

1 x 8 = 8

2 x 4 = 8

4 x 2 = 8

8 x 1 = 8

앞서 말했듯, 1과 자기자신을 제외한 약수가 존재하는지 확인하려면, 자기자신의 제곱근(루트)까지만 확인하면 된다.

어차피 약수들이 대칭적으로 짝을 이뤄서 8을 완성하기 때문이다.

루트8은 약 2.8정도이므로 자연수 2까지만 확인해서 8에 나눠떨어지는지 확인하면 된다.

 

자연수 25와 8은 자기자신의 제곱근(루트)에 해당하는 숫자 혹은 미만의 가장 가까운 숫자가 나눠 떨어지므로 소수가 아닌 것이다.

해당 알고리즘은 다음과 같이 코드로 작성 할 수 있다.

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				# 전부 나눠떨어지지 않는다면 소수임

위와 같이 코드를 작성하면 훨씬 더 빠르게 해당 숫자가 소수인지 아닌지를 판별할 수 있다.

 

---

이제 소수를 찾는 방법을 알았으니 안심했다면 아직 남아있는 문턱이 하나 있다.

지금 우리가 공부한 방법으로는 특정 숫자 1개가 소수인지 아닌지를 판별할 수 있다.

그런데 만약 일정 범위안에 있는 숫자들 중에서 소수를 전부 찾으라고 한다면,

범위 내에 존재하는 숫자들을 대상으로 전부 계산하려고하면 너무 많은 시간이 소모된다.

 

이렇게 특정 범위에 존재하는 여러개의 숫자들을 한번에 소수판별하는 방법 또한 존재한다.

글이 길어졌으므로 이번 글을 여기까지 적도록 하고

다음번 포스팅에서 이걸 해결하는 알고리즘을 소개하도록 하겠다.