정수가 모두 1 인 경우 이진수 나누기를 확인할 수있는 방법이 있습니까? 혼란 제목의

Question

종류 그래서 나는 더 나은 자신을 설명하려고합니다 : 을 나는 수는 다음 식 사용하여 소수 여부를 확인할 수 있다는 것을 내가 찾은 파스칼의 삼각형을 사용 : 그러나

boolean isPrime= (2^(x) -2) % x == 0; 

는,이 동작하기 때문에 그러나 계산하기 전에,

boolean isPrime = (2^(x-1) -1) % x==0; 

이 많이 변경되지 않습니다 2의 거듭 제곱에, 그것은 내가 X> 2 다음 식을 사용할 수 있다는 것을 발견 주위에 조정의 조금 후에, 매우 빠르게 매우 큰됩니다 mod x 2 진수는 모두 1입니다 (x = 7, 63 또는 11111). 1 이진수)

이제 내 질문에이 간단한 방법을 사용하여 숫자가 소수인지 여부를 결정하는 정확한 함수를 만들 수 있습니다.

Answer 1

아니요, 정확한 소수 테스트를 작성하기 위해 알아 차린 관계를 활용하는 간단한 방법은 없습니다. = 3 17 N = 561, 함수를 잘못 N가 소수 보고서 예를 들어

.

너는 Fermat's Little Theorem과 Carmichael numbers 및 Miller-Rabin 소수 검사를보고 싶을 것이다.