알고리즘 정리 - 소수 판정[에라토스테네스의 체]

기존의 내가 사용했던 소수 판정 방법
=> N을 N의 제곱근까지의 수로 나눠서 나눠진다면 break 하는 방식
=> 하지만 숫자가 커질 경우 나눠야하는 경우가 많이 증가함

위 단점을 극복하기 위해 소수 판정을 위한 "에라토스테네스의 체"에 대해 학습

에라토스테네스의 체

출처 : 위키 백과

알고리즘 구현

[1] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열
[2] 2는 소수이므로 따로 표시, 그 후 자기 자신을 제외한 모든 2의 배수 제거
[3] 3은 소수이므로 따로 표시, 그 후 자기 자신을 제외한 모든 3의 배수 제거

해당 과정 반복하기

코드

def prime_list(n):
	sieve = [True] * n
    
    m = int(n ** 0.5)
    for i in range(2, m+1):
    	if sieve[i]:
        	for j in range(i+i, n, i):
            	sieve[j] = False
    return [i for i in range(2, n) if sieve[i] == True]

예시 문제
백준 6588

정답 코드

num = []
while True:
    n = int(input())
    if not n:
        break
    num.append(n)
n = max(num)
nums = [True] * (n+1)
for i in range(2, int(n**0.5)+1):
    if nums[i]:
        for j in range(2*i, n+1, i):
            nums[j] = False
for n in num:
    for i in range(3, n, 2):
        if nums[i] and nums[n-i]:
            print(f"{n} = {i} + {n-i}")
            break
    else:
        print("Goldbach's conjecture is wrong.")