[알고리즘] 소수 판별 알고리즘, 에라토스테네스의 체 알고리즘 파이썬 구현

자료 출처: https://youtu.be/cswJ1h-How0

알고리즘 천민에게 한 줄기의 빛 같은 동빈님의 강의를 요약해서 정리하고 있다. 열심히 정리하고 학습한 후에는 오직 문제풀이 맹연습뿐.... 알고리즘 양반까지는 힘들더라도 중인까지는 올라가보도록 노력을 거듭해보자 홧팅홧팅

1. 소수 판별 알고리즘

• 약수의 성질을 이용하면 더 쉽게 풀 수 있다.
• 약수의 성질이란? 모든 양수는 가운데 약수를 기준으로 대칭이라는 것
• 따라서 특정 자연수의 모든 약수를 찾을 때, 가운데 약수(제곱근)까지만 확인하면 됨
• 시간 복잡도: O(N^1/2)

2. 소수 판별 알고리즘 파이썬 구현

import math

def is_prime_number(n):
    for i in range(2, int(math.sqrt(n)) + 1): # 1을 더해줌으로써 제곱근까지 확인해준다.
        if n % i == 0:
            return False
    return True

3. 다수의 소수 판별

에라토스테네스의 체 알고리즘: N보다 작거나 같은 모든 소수를 찾을 때 사용하는 알고리즘

• 2부터 N까지의 모든 자연수를 나열한다.
• 남은 수 중 아직 처리하지 않은 가장 작은 수 i를 찾는다
• 남은 수 중 i의 배수를 모두 제거한다(i는 제거하지 않음).
• 더이상 반복할 수 없을 때까지 위의 2, 3번 과정을 반복한다.
• 시간 복잡도: 선형 시간에 가까울 정도로 매우 빠르나, 메모리가 많이 필요하다. O(NloglogN)

4. 에라토스테네스의 체 알고리즘 파이썬 구현

import math

n = 1000
arr = [True for _ in range(n + 1)]

for i in range(2, int(math.sqrt(n)) + 1): # 약수의 성질을 이용하는 것은 동일
    if arr[i] == True: # i가 소수인 경우(남은 수인 경우) - 소수가 아닌 경우는 아래의 코드에서 False 처리해줌
    
        # i를 제외한 모든 i의 배수를 찾는 것이므로, 2부터 차례로 1씩 증가시켜가며 i에 곱해줌
        j = 2
        while i * j <= n: # n보다 작은 모든 i의 배수에 대하여
            arr[i * j] = False # 해당 i의 배수는 False 처리하여 제거함
            j += 1 # i의 다음 배수를 찾기 위해 j += 1을 해줌(i의 배수가 n보다 커지기 직전까지)
            
for i in range(2, n + 1):
    if arr[i]:
        print(i, end = " ")