밀러-라빈 소수판별법을 사용하여 입력한 수가 소수인지 판별합니다. 수를 입력받을 때 94906266 이하의 수만 허용하는 이유는 정수 자료형이 저장할 수 있는 수의 한계 때문입니다. 스크래치에서 9007199254740992(2의 53제곱)보다 큰 수를 계산하면 부동소수점 자료형으로 자료형을 바꾸기 때문에, 나머지 연산을 할 때는 부정확한 결과가 나올 수 있습니다. 이 프로젝트에서는 수를 제곱하는 경우도 있기 때문에 2^53의 제곱근보다 작은 수만 사용하도록 제한했습니다. 밀러-라빈 소수판별법에서는 2 이상 n-2 이하에서 임의의 수 a를 선택해 계산합니다. 이때 일정 범위 내의 모든 수에 대해서는 a에 몇 가지의 수만 대입해 알아보면 된다는 것이 확인되어 있습니다. 결정론적으로 계산하겠냐는 질문에 "예"라고 대답하면 적은 개수의 숫자만으로도 입력한 수가 소수인지 확실하게 판별할 수 있습니다. 짝수를 입력할 경우 소수판별법을 사용하지 않고 바로 합성수(2이면 소수)라고 알려줍니다. k의 값은 a를 임의의 수로 설정할 횟수를 나타냅니다.
위키백과 문서를 참고했습니다. 영어 위키백과의 문서: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test 한국어 위키백과의 문서: https://ko.wikipedia.org/wiki/%EB%B0%80%EB%9F%AC-%EB%9D%BC%EB%B9%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95
