怎麼用程式寫公式來判斷質數?

Question

請問怎麼用程式證明下面ㄉ式子?
可以用C或VB寫出來...利用\"下面的公式\"寫入程式來\"判斷\"質數~
請各位大大幫忙一下

米勒-拉賓檢驗

到目前為止，實際運用上最常使用的質數檢驗法為米勒-拉賓(Miller-Rabin)檢驗，其依循的是當p為質數時，X2≡1 (mod p)只有兩個解X≡±1 (mod p)。利用這個觀念，米勒-拉賓檢驗在計算an-1 (mod n)的過程中，隨時檢查是否有X2≡1 (mod n)，但是X不等於±1 (mod n)的情形發生，如果有此種X，則n為合數。同樣的也挑選t次不同的a值進行檢查，使得產生偽質數的機率降低。有理論可以證明每挑選一次a值進行檢查，結果是偽質數的機率小於或等於1/4，經過t次之後我們就可以把錯誤率降到1/4t，達到可以接受的範圍之內。

[米勒-拉賓檢驗]
for i = 1 to t do
隨機挑選a，a介於2和n-2之間
計算r = an-1 (mod n)，過程中
if $ X2≡1 (mod n) but X¹ ±1 (mod n) then output “合數”
if r ¹ 1 then output “合數”
output “質數”


我只會寫下面的程式~不過還是被老師退回了
int main()

printf(\"請輸入數字：\");
scanf(\"%d\",&n);
if (n==1) goto next;
for(i=2;i<=sqrt(n);i++)
{
if(n%i==0)
break;
}
if (i<=sqrt(n) )
printf(\"%d不是質數\\n\",n);
else
printf(\"%d是質數\\n\",n);
next:if(n==1)
printf(\"%d不是質數\\n\",n);

如果不是質數的話...必定會有1與本身以外的因數...
這個非1以及本身的因數...最小是2,最大是此數的正平方根
所以用迴圈從2跑到這個數的正平方根,若其中有任何一個數可以整除此數(也就是餘數為0)
就表示不是質數..跳離迴圈
如果是有因數所以跳離迴圈時i值最大不會超過n的平方根,我就以此判斷是不是質數

我這個程式只判斷了大於等於1的正整數...不過還是被退回了><

Answer 1

公開金鑰加密?
RSA?

Answer 2

#include
#include

using namespace std;

int main(int argc, char *argv[])
{
int m,n,i,flag=1;
while(1) //一整數n，必有一質因數小於 sqrt n
{
cout<<"Please input to be bigger than 1 positive integer(Input -1 to exit): ";
cin>>n; //由鍵盤輸入一個大於1的正整數做植樹的判斷
if(n==-1) break; //-1離開程式
for(i=1;i<=n;i++)
{
if(i*i>=n) //求m=sqrt n
{
m=i;
break;
}
}
for(i=2;i<=m;i++) //判斷整數 n，是否有一質因數小於 sqrt n
{
if(n%i==0)
{
flag=0;
break;
}
else flag=1;
}
if(flag==1)
cout< else
cout< }
system("PAUSE");
return EXIT_SUCCESS;
}

=============================================================
這是用C++寫的，不知道你能不能接受~~
不過演算法大概就是醬，語言差別不大~~
希望對你有幫助!!