사용자 도구

사이트 도구


ps:소수_판별

소수 판별 (Primality Test)

특정 수가 소수인지 판별

Trial division

  • 작성중
  • def is_prime_small(n):
      return n >= 2 and all(n % i != 0 for i in range(2, math.isqrt(n) + 1))

밀러-라빈 알고리즘

  • 작성중
  • 기본적으로는 확률적인 알고리즘이다. 그래서 판별여부가 잘못될 확률이 0는 아닌데, 여러개의 base로 테스트해볼수록 잘못될 확률이 작아진다
    • 이론적으로는 2ln(n^2) 이하의 모든 수를 base로 해서 테스트하면 정확한 결과를 얻는다고 한다.
    • 실용적으로는
      • 32bit 범위의 정수들은 2, 7, 61 만을 base로 해서 테스트해도 100% 정확한 결과를 준다
      • 64bit 범위의 정수들은 2, 325, 9375, 28178, 450775, 9780504, 1795265022 를 base로 테스트하는게 가장 최소의 base를 사용하는 방법이다

토론

댓글을 입력하세요:
S V J M A
 
ps/소수_판별.txt · 마지막으로 수정됨: 2022/06/02 08:23 저자 teferi