legoha2011   11달 전

제가 정수론을 몰라서 질문이 있습니다

소수 판별법에 대해 알아보는 중 밀러-라빈 소수 판별법의 정확도는 100%가 아니라고 되어있는데
테스트 횟수가 높을수록 정확도가 높다는건 이해했습니다
비교 테스트값은 다음과 같이 7bases로 했는데

2, 325, 9375, 28178, 450775, 9780504, 1795265022

이 테스트 값이 달라지면 테스트 횟수가 같아도 정확도가 달라지는건가요?

zenith82114   11달 전

아무런 제한이 없을 때의 밀러-라빈 판정법은 매번 base를 독립 랜덤으로 뽑아서 사용하는 것이 기본이고 100% 성공을 보장하지 않습니다. 하지만 판정하려는 수가 특정 값 이하 등 추가 조건이 있으면 특정 base 값들만 시도해 봐도 충분하고 그런 base 값의 목록들이 많이 알려져 있습니다.

cf) https://en.wikipedia.org/wiki/...

pia0121   10달 전

문제에서 제시하는 숫자 입력범위인 4*10^9은 c언어 기준 int 범위 내이며, 판별식에 2,7,61 3가지 숫자만 돌리면 100% 성공률이 보장됩니다.

zenith82114   10달 전

@pia0121 C에서는 unsigned int를 사용해야 합니다.

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