[정수론] 에라토스테네스의 체
출처 : [이것이 코딩테스트다] 책
- 에라토스테네스의 체는 O(N x loglogN) time으로 거의 사실상 선형시간에 동작할 정도로 빠르다.
- 이 분은 BC 274년에 태어난 사람이다,, 어떻게 이런걸 떠올렸을까
- 파이썬 코드로 에라토스테네스의 체를 구현해봤다.
소수 판별 (Prime Check)
- 소수 (Prime Number)란 2보다 큰 자연수 중에서, 1과 자기 자신을 제외한 수로 나누어 떨어지지 않는 자연수를 말한다.
- 다음과 같이 코드를 작성하면 O(X^1/2)에 소수를 판별할 수 있다.
X까지 판별하지 않고, X의 제곱근까지만 체크해도 된다.import math def is_prime_number(x): if x == 1 : return False for i in range(2, int(math.sqrt(x))+1): if x % i == 0: return False return True print(is_prime_number(4)) print(is_prime_number(11))
결과 : False / True
에라토스테네스의 체
위의 코드는 O(X^1/2) 시간복잡도로 효율이 뛰어나다. 예를 들어, 판별할 수 가 1,000,000 정도 일때는 1,000 회 이하 연산으로 찾을 수 있는 것이다.
그런데, 하나의 수에 대해서 소수인지 판별해야 하는 경우가 아니라, 수의 범위가 주어졌을때, 그 전체 수의 범위 안에서 존재하는 모든 소수를 찾아야 하는 경우에는 어떨까?
에라토스테네스 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표 알고리즘이다.
- 에라토스테네스의 체 코드
import math n = 100 array = [True for i in range(n+1)] array[0], array[1] = False, False for i in range(2, int(math.sqrt(n))+1): x = 2 while i * x <= n: array[i*x] = False x += 1 for i in range(50,60): print(i,':',array[i])
결과 : 53, 59 에서 True / 나머지에서 False
Author And Source
이 문제에 관하여([정수론] 에라토스테네스의 체), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@heyksw/정수론-에라토스테네스의-체저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)