사용자 도구

사이트 도구


ps:소수

소수 (Prime number)

  • 관련된 몇가지 성질들
    • 소수정리 (Prime number theorem)
      • n이하의 소수의 갯수는 대략 n/ln(n)개이다. 바꿔쓰면, n번째 소수의 값은 대략 n*ln(n)이다
    • 메르텐스의 제 2정리 Mertens' theorems
      • n이하 소수들의 역수의 합은 O(lnln(n))

n보다 작은 소수의 목록

  • 에라토스테네스의 체(Sieve of Eratosthenes)가 가장 기초적이지만 가장 효율적.
    • 시간복잡도는 O(nloglogn). 공간복잡도는 O(n)이다
      • n이 2^64일때에도, loglogn<4 이다 (자연로그). 사실상 loglogn은 거의 상수 취급하고 그냥 O(n)이라고 봐도 무방하다.
      • 시간복잡도의 대략적은 증명은 여기.
        • n이하 소수들의 역수의 합은 O(lnln(n)) 라는 사실을 알고 있다면 다ㅏㅇ연하다
    • 구현할때는 Wheel factorization 기법으로 속도를 늘릴수 있다. 파이썬에서 테스트해본 결과, 2휠은 효과가 있었지만, 2,3,5휠은 2휠에 비해서 n<10^6 범위에서는 별 차이 없고, 10^7범위에서 가서야 약간 더 빨라졌다. 그 이상의 휠은 거의 효율이 없어보였다.
    • 구현을 조금만 바꾸면, 길이 n짜리 배열을 소수/합성수에 따라서 True/False로만 채울 것이 아니라, 가장 작은 약수, 또는 소인수의 갯수로 채울수도 있다. 모든 k에 대해서 가장 작은 약수를 안다면, k를 O(logk)에 소인수분해할 수 있다.
  • 소수의 목록을 구하는 다른 방법들도 있긴 하지만 신경 쓸 필요 없다.
  • 그나마 알아두면 유용할 수 있을 다른 방법으로 Linear sieve 이 있다. 이 방법은 O(n)에 소수목록과 더불어 1~n까지 모든 수의 가장 작은 약수를 찾아준다.
    • https://ahgus89.github.io/algorithm/Linear-sieve/에 따르면 에라토스테네스의 체보다 유의미하게 빠르다고 한다. 파이썬에서도 정말 빠른지 테스트는 안해봤다..
    • lp = [0] * (n + 1)
      primes = []
      for i in range(2, n + 1):
          if lp[i] == 0:
              lp[i] = i
              primes.append(i)
          for prime in primes:
              if prime > lp[i] or i * prime > n:
                  break
              lp[i * prime] = prime
      return lp, primes

코드

n보다 작은 소수의 갯수

토론

댓글을 입력하세요:
Q V O L P
 
ps/소수.txt · 마지막으로 수정됨: 2021/02/16 13:31 저자 teferi