소수 목록 구하기

기본적으로 에라토스테네스의 체를 사용한다.
시간복잡도상으로는 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휠을 사용하기로 했다
- 참고한 구현체는 소수의 연속합를 가장 빠르게 푼 hanjoondev 의 코드이다.
- 소수의 연속합를 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는 조금씩 변형해서 다양한 정수론적 함수들을 계산하는데에 사용할수 있다. 사실 이것이 가장 핵심.

그 외의 방법

소수의 목록을 구하는 다른 방법들은 별 신경 쓸 필요 없는것 같다.
- Sieve of Sundaram은 O(nlogn)이라고 하고, Sieve of Atkin은 O(n)이라고 하지만 실제로는 에라토스테네스의 체보다 느리다고 하다. (링크)
  - https://site.thekipa.com/nta-2019/week4.pdf 에 따르면 10^8 까지도 에라토스테네스의 체가 Atkin보다 빠르고, 10^9 정도면 Atkin이 빨라진다고 한다. (물론 파이썬에서는 다르겠지만)

코드

에라토스테네스의 체를, 2,3-wheel을 적용해서 최적화한 버전.
teflib.numtheory.prime_list

목차

소수 목록 구하기

에라토스테네스의 체 (Sieve of Eratosthenes)

Linear Sieve

그 외의 방법

코드