ps:소수_목록_구하기
소수 목록 구하기
- 기본적으로 에라토스테네스의 체를 사용한다.
- 시간복잡도상으로는 O(n)의 Linear sieve가 O(nloglogn)의 에라토스테네스의 체보다 더 빠르지만, 실제 구현은 에라토스테네스의 체가 더 빨리 돈다.
- 관련 문제에서 시간 복잡도를 표기할때도 O(nloglogn)으로 쓰겠다..
- 실질적으로 돌릴수 있는 한계는 n=10^7 정도라고 생각하면 된다. 이것을 초과하는 N에 체를 돌려야 한다면, 그 방법은 정해가 아닐 가능성이 높다..
에라토스테네스의 체 (Sieve of Eratosthenes)
- Sieve of Eratosthenes 참고. 가장 기초적이면서 가장 효율적이다
- 시간복잡도는 O(nloglogn). 공간복잡도는 O(n)이다
- 64bit 정수 범위에서 loglogn<4 이다 (자연로그). 사실상 loglogn은 거의 상수 취급하고 그냥 O(n)이라고 봐도 무방하다.
- 시간복잡도의 대략적은 증명은 여기.
- n이하 소수들의 역수의 합은 O(lnln(n)) 라는 사실을 알고 있다면 당연하다
- Wheel factorization 기법으로 속도를 늘릴수 있다. 파이썬에서 테스트해본 결과, 2휠은 효과가 있었지만, 2,3,5휠은 2휠에 비해서 n<10^6 범위에서는 별 차이 없고, 10^7범위에서 가서야 약간 더 빨라졌다. 그 이상의 휠은 거의 효율이 없어보였다. ⇒
- 위의 문장을 적고서 한참 뒤에 2,3 휠의 다른 구현체를 구하게 되어 테스트해봤는데, 2휠에 비해서 빠르게 돌았다 (메모리도 적게 먹고). teflib의 구현은 2,3휠을 사용하기로 했다
- 소수의 연속합를 2휠 구현에서 2,3휠 구현으로 바꿔서 풀었더니 388ms에서 264ms로 줄어들었다.
- 구현을 조금만 바꾸면, 길이 n짜리 배열을 소수/합성수에 따라서 True/False로만 채울 것이 아니라, 가장 작은 소인수, 또는 소인수의 갯수로 채울수도 있다. 모든 k에 대해서 가장 작은 소인수를 구하는 것은, k이하의 수들을 빠르게 소인수분해하는 것에 사용되기 때문에 중요하다.
Linear Sieve
- 위키피디아에서는 Euler's Sieve 라고 표현하는데, 다른 블로그에서는 Linear sieve 라고 표현하는 곳들이 더 많았다.
- 참고 : https://cp-algorithms.com/algebra/prime-sieve-linear.html, https://ahgus89.github.io/algorithm/Linear-sieve/
- 두 사이트의 구현이 살짝 다른것처럼 보일수도 있다. 소수목록을 순회하면서 p*i의 최소인수를 채워주는 루프를 종료하는 조건이 cp-algorithm은 p >= lpf[i] 일때이고, ahgus89블로그에서는 i % p == 0 일때이다. 근데 두가지는 결국 같은 조건이다.
- 이 방법은 n이하의 수에 대해서 소수 여부와, 가장 작은 소인수를 O(n)에 찾아준다.
- lpf 배열의 각 값을 한번씩만 업데이트한다.
- https://ahgus89.github.io/algorithm/Linear-sieve/에 따르면 에라토스테네스의 체보다 유의미하게 빠르다고 하는데.. 파이썬에서는 훨씬 느렸다.
- 에라토스테네스의 구현에서 속도를 크게 향상시켰던 slice assignment를 여기에서는 사용할수 없다는 부분에서 상수값이 커진다.
- 코드
def linear_sieve(n): lpf = list(range(n + 1)) lpf[2::2] = [2] * (n // 2) primes = [] for i in range(3, n + 1, 2): if lpf[i] == i: primes.append(i) for p in primes: if i * p > n or p > lpf[i]: break lpf[i * p] = p return [2] + primes, lpf
- 최소인수만을 찾는 경우에는 그냥 바깥루트 범위를 n/3까지만 돌려버리면 조금더 상수최적화를 시킬수 있다.(그 이상은 어차피 i*p>n 에서 바로 걸려서 중단되므로). 이렇게까지 하면 에라토스테네스체를 이용한것보다 좀더 빠르다
- 코드
def least_prime_factor(n): lpf = list(range(n + 1)) lpf[2::2] = [2] * (n // 2) primes = [] for i in range(3, n // 3 + 1, 2): if lpf[i] == i: primes.append(i) for p in primes: if i * p > n or p > lpf[i]: break lpf[i * p] = p return lpf
- 그리고 무엇보다도, Linear Sieve는 조금씩 변형해서 다양한 정수론적 함수들을 계산하는데에 사용할수 있다. 사실 이것이 가장 핵심.
그 외의 방법
- 소수의 목록을 구하는 다른 방법들은 별 신경 쓸 필요 없는것 같다.
-
- https://site.thekipa.com/nta-2019/week4.pdf 에 따르면 10^8 까지도 에라토스테네스의 체가 Atkin보다 빠르고, 10^9 정도면 Atkin이 빨라진다고 한다. (물론 파이썬에서는 다르겠지만)
-
코드
- 에라토스테네스의 체를, 2,3-wheel을 적용해서 최적화한 버전.
ps/소수_목록_구하기.txt · 마지막으로 수정됨: 2023/08/09 06:51 저자 teferi
토론