에라토스테네스의 체, 소수 판별 알고리즘
소수 판별 알고리즘
1과 자기 자신으로만 나누어 떨어지는 숫자를 소수라고 한다.
X가 소수인지 판별하기 위해서 X를 2부터 X-1까지 나눠서 확인해야 한다.
하지만 이러면 시간복잡도는 이므로 X의 크기가 커지면 커질수록 효율적이지 못하다.
시간복잡도를 개선하기 위해서 2부터 X-1까지 확인하는 대신에 2부터 까지 확인한다.
예를 들어서 36의 약수는 다음과 같다.
- (1, 2, 3, 4, 6, 9, 12, 18, 36)
36의 약수 중에서 가운데 수 6을 기준으로 대칭적으로 곱을 통하여 36을 만들 수 있으므로, 결과적으로 까지만 확인하면 소수 판별이 가능하다.
이렇게 개선된 알고리즘의 시간복잡도는 이다.
import math
def prime_number(x):
for i in range(2, int(math.sqrt(x)) + 1):
if x % i == 0:
return False
return True
에라토스테네스의 체
개선된 소수 판별 알고리즘을 쓰더라도 여러 수에 대한 소수 판별에는 여전히 비효율적일 수 있다.
따라서 이러한 경우에는 에라토스테네스의 체
라는 방법을 사용한다.
에라토스테네스의 체를 구하는 방법은 아래와 같다.
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
- 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 x를 찾는다.
- i를 제외한 i의 배수를 모두 제거한다.
- 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복한다.
def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정 (True이면 소수)
sieve = [True] * n
# n의 최대 약수가 sqrt(n) 이하이므로 i = sqrt(n) 까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True: # i가 소수이면
for j in range(i + i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False
# 소수 목록 산출
return [i for i in range(2, n) if sieve[i] == True]
- 결과:
prime_list(10)
# [2, 3, 5, 7]
prime_list(20)
# [2, 3, 5, 7, 11, 13, 17, 19]
max(prime_list(1000000)
# 999983
에라토스테네스의 체는 시간복잡도가 이기 때문에 선형 시간에 동작할 정도로 빠르다.
하지만 N의 크기 만큼 메모리를 저장하고 기억하므로 주의해야 한다.
Author And Source
이 문제에 관하여(에라토스테네스의 체, 소수 판별 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hn04147/에라토스테네스의-체-소수-판별-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)