jilseojigi   3년 전

안녕하세요.

52744385번 소스 코드처럼 밀러-라빈 소수 판별법으로 a가 2 또는 3일 때만 확인하면 1373653보다 작은 자연수만 소수인지 판별할 수 있습니다.

합성수 1373653=829×1657는 밑이 2인 가짜소수이면서 밑이 3인 가짜소수입니다. 가짜소수 몇 가지를 테스트 케이스에 추가해 주셨으면 좋겠습니다.

  • if n < 2,047, it is enough to test a = 2;
  • if n < 1,373,653, it is enough to test a = 2 and 3;
  • if n < 9,080,191, it is enough to test a = 31 and 73;
  • if n < 25,326,001, it is enough to test a = 2, 3, and 5;

참고: https://en.wikipedia.org/wiki/...

startlink   2년 전

재채점했습니다.

댓글을 작성하려면 로그인해야 합니다.