테페리넷

사용자 도구

사이트 도구

현재 위치: 테페리넷 » Problem Solving » 소수 목록 구하기
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)이라고 봐도 무방하다.
    • 시간복잡도의 대략적은 증명은 여기.
  • 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는 조금씩 변형해서 다양한 정수론적 함수들을 계산하는데에 사용할수 있다. 사실 이것이 가장 핵심.

그 외의 방법

  • 소수의 목록을 구하는 다른 방법들은 별 신경 쓸 필요 없는것 같다.

코드

토론

댓글을 입력하세요:
Y F​ V M I
 
ps/소수_목록_구하기.txt · 마지막으로 수정됨: 2023/08/09 06:51 저자 teferi