有沒有一種方法來檢查二進制除法當整數是所有的？

Question

一種混亂的標題，所以我會試着更好地解釋一下： 使用楊輝三角我發現我可以檢查一個數是否是使用下列公式黃金：

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

然而，因爲這個工作對2的冪，就變得非常大非常快，有點扭捏左右，我發現我可以用X> 2以下公式後：

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

這不是改變了很多，但是在計算前mod x中的二進制數是全1（對於x = 7，它將是63或11111 1在二進制）

現在我的問題是如果有一個簡單的方法來利用這一點，並創建一個準確的函數來確定一個數字是否是一個素數。

Answer 1

不，沒有簡單的方法利用您注意到的關係來創建準確的素性測試。

例如，對於ñ = 561 = 3 17，你的函數錯誤地報告ñ是素數。

你會想看看Fermat's Little Theorem和Carmichael numbers和Miller-Rabin素數測試。