[Python/코테] 소수 판별, 에라토스테네스의 체

소수 판별 알고리즘

2 이상의 자연수에 대해 소수인지 아닌지를 판별하는 함수

def is_prime_number(x):
    for i in range(2, x):
        if x % i == 0:		# x가 i로 나누어 떨어진다면 
            return False	# 소수가 아님
        return True		# 소수

• 2부터 N-1까지의 모든 자연수에 대해 연산을 수행하므로 시간복잡도는 $O(N)$ 이다.

약수의 성질

• 모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
• 따라서 특정한 자연수의 모든 약수를 찾을 때, 가운데 약수(제곱근)까지만 확인하면 된다. → 시간 복잡도를 $O(\sqrt N)$ 줄여준다.

16의 약수

def is_prime_number(x):
    for i in range(2, x**(1/2) + 1):	# 2부터 x의 제곱근까지 모든 수를 확인
        if x % i == 0:	# x가 해당 수로 나누어 떨어진다면
            return False	# 소수가 아님
        return True

에라토스테네스의 체

다수의 소수 판별, 즉 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할 때 에라토스테네스의 체 알고리즘을 사용할 수 있다. 

* 동작:

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2, 3번을 반복한다.

source: 위키피디아

n = 1000    # 2부터 n까지의 모든 수에 대해 소수 판별

array = [True for i in range(n+1)]

for i in range(2, n**(1/2) + 1):
    if array[i] == True:
        j = 2
        while i * j <= n:
            array[i*j] = False	# i를 제외한 i의 모든 배수 지우기
            j += 1

# 모든 소수 출력
for i in range(2, n+1):
    if array[i]:
        print(i, end=' ')

• 시간 복잡도는 $O(loglogN)$ 소요된다. 선형 시간에 가까울 정도로 매우 빠르다.
• 그러나, 각 자연수에 대한 소수 여부를 테이블에 기록하므로 메모리가 많이 필요하다. 

 

---

출처: https://youtu.be/CyINCmJPjfM?si=JZ1kYidV8Uq4YkT3

https://youtu.be/9rLFFKmKzno?si=tGSm9omaFM7mn2Sh