파이썬 소수 판별 알고리즘

소수의 판별: 기본적인 알고리즘 성능 분석

• 2부터 𝑋-1까지의 모든 자연수에 대하여 연산을 수행해야 한다
  • 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X) 

---

약수의 성질

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다
  • 예를 들어 16의 약수는 1, 2, 4, 8, 16이다
  • 이때 2 X 8 = 16은 8 X 2 = 16과 대칭이다
• 따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다
  • 예를 들어 16이 2로 나누어떨어진다는 것은 8로도 나누어떨어진다는 것을 의미한다

import math

# 소수 판별 함수
def is_prime_number(x):
	# 1은 소수가 아니므로 예외처리
	if x == 1:
    	return False
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

 

---

에라토스테네스의 체

위의 방법은 특정 범위 내의 모든 소수를 구할 때는 비효율적이다. (실제로 백준 4948번을 위의 방식대로 풀면 시간초과가 난다)

 

효율적으로 소수를 구하기 위해 에라토스테네스는 범위에서 합성수를 모두 지우는 방식을 제안했다.

 

1. 1 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. ... (반복)

에라토스테네스의 체

 

따라서 n까지의 수가 소수인지 아닌지 True, False로 저장해준 뒤 싹 돌리면 된다. 

import math

# 에라토스테네스의 체 방식 사용
def cntPrimeNums(start, end):
    # 1~end까지
    erato = [True] * end

    # 1은 소수가 아니므로 체크
    erato[0] = False

    for i in range(2, int(math.sqrt(end)) + 1):
        if erato[i] == True:
            for i in range(i + i, end, i):
                erato[i] = False
    cnt = 0
    for i in range(start, end):
        if erato[i] == True:
            cnt += 1
    return cnt

 

위 방법은 특정 범위 내에 소수가 몇개 있는지 체크해주는 코드다. 위의 코드는 start 이상 end 미만의 수를 중 소수를 체크한다! 만약 end까지 포함시키고 싶다면 수를 유의해서 넣어주자.