azaka9541   3년 전

근데 s와 d를 구하는 방식은 이해를 못하겠어요. n-1을 어떻게 n -1 = 2^s * d로 분해하는건가요?

j213h   3년 전

n이 홀수인 소수라고 가정했을 때, n - 1은 무조건 짝수가 됩니다. n - 1은 짝수이므로 n - 1 = 2 ** s * d 의 형태로 표현이 됩니다.

저는 밀러-라빈으로 문제를 풀지않아서 코드의 흐름을 모르지만 형태를 만족하는 s, d를 찾기 위한 과정이 아닐까하는 생각이 듭니다.

zenith82114   3년 전

이 코드에는 반례가 있습니다.

n=37
[o] s=2, d=9
[x] s=1, d=18

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