====== 소수 목록 구하기 ======

  * 기본적으로 에라토스테네스의 체를 사용한다.
  * 시간복잡도상으로는 O(n)의 Linear sieve가 O(nloglogn)의 에라토스테네스의 체보다 더 빠르지만, 실제 구현은 에라토스테네스의 체가 더 빨리 돈다.
  * 관련 문제에서 시간 복잡도를 표기할때도 O(nloglogn)으로 쓰겠다..
  * 실질적으로 돌릴수 있는 한계는 n=10^7 정도라고 생각하면 된다. 이것을 초과하는 N에 체를 돌려야 한다면, 그 방법은 정해가 아닐 가능성이 높다..

===== 에라토스테네스의 체 (Sieve of Eratosthenes) ======
  * [[wp>Sieve of Eratosthenes]] 참고. 가장 기초적이면서 가장 효율적이다
  * 시간복잡도는 O(nloglogn). 공간복잡도는 O(n)이다
    * 64bit 정수 범위에서 loglogn<4 이다 (자연로그). 사실상 loglogn은 거의 상수 취급하고 그냥 O(n)이라고 봐도 무방하다.
    * 시간복잡도의 대략적은 증명은 [[https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html|여기]].
      * [[ps:소수|n이하 소수들의 역수의 합은 O(lnln(n))]] 라는 사실을 알고 있다면 당연하다   
  * [[wp>Wheel factorization]] 기법으로 속도를 늘릴수 있다. 파이썬에서 테스트해본 결과, 2휠은 효과가 있었지만, 2,3,5휠은 2휠에 비해서 n<10^6 범위에서는 별 차이 없고, 10^7범위에서 가서야 약간 더 빨라졌다. 그 이상의 휠은 거의 효율이 없어보였다. => 
    * 위의 문장을 적고서 한참 뒤에 2,3 휠의 다른 구현체를 구하게 되어 테스트해봤는데, 2휠에 비해서 빠르게 돌았다 (메모리도 적게 먹고). teflib의 구현은 2,3휠을 사용하기로 했다
    * 참고한 구현체는 [[ps:problems:boj:1644]]를 가장 빠르게 푼 hanjoondev 의 [[https://www.acmicpc.net/source/43383779|코드]]이다.
    * [[ps:problems:boj:1644]]를 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를 여기에서는 사용할수 없다는 부분에서 상수값이 커진다.
  * 코드
    * <dkpr py>
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
</dkpr>
  * 최소인수만을 찾는 경우에는 그냥 바깥루트 범위를 n/3까지만 돌려버리면 조금더 상수최적화를 시킬수 있다.(그 이상은 어차피 i*p>n 에서 바로 걸려서 중단되므로). 이렇게까지 하면 에라토스테네스체를 이용한것보다 좀더 빠르다
  * 코드
    * <dkpr py>
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 
</dkpr>
  * 그리고 무엇보다도, Linear Sieve는 조금씩 변형해서 다양한 정수론적 함수들을 계산하는데에 사용할수 있다. 사실 이것이 가장 핵심.

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

==== 코드 ====
  * 에라토스테네스의 체를, 2,3-wheel을 적용해서 최적화한 버전.
  * [[ps:teflib:numtheory#prime_list|teflib.numtheory.prime_list]]