㈠ 判斷一個整數是不是素數的演算法
建立一個素數表（一般不大於此整數的算術平方根即可）進行試除，或者利用一些常見素數性質，以及被素數整除的性質來判斷
㈡ C語言 設計並實現一種大素數隨機生成方法； 實現一種快速判定任意一個大數是否是素數方法 跪求啊
Rabin -Miller演算法是典型的驗證一個數字是否為素數的方法。判斷素數的方法是Rabin-Miller概率測試，那麼他具體的流程是什麼呢。假設我們要判斷n是不是素數，首先我們必須保證n 是個奇數，那麼我們就可以把n 表示為 n = (2^r)*s+1,注意s 也必須是一個奇數。然後我們就要選擇一個隨機的整數a (1<=a<=n-1)，接下來我們就是要判斷 a^s=1 (mod n) 或a^((2^j)*s)= -1（mod n）(0<=j如果任意一式成立，我們就說n通過了測試，但是有可能不是素數也能通過測試。所以我們通常要做多次這樣的測試，以確保我們得到的是一個素數。（DDS的標準是要經過50次測試）
採用Rabin-Miller演算法進行驗算
首先選擇一個代測的隨機數p，計算b，b是2整除p-1的次數。然後計算m，使得n=1+(2^b)m。
（1） 選擇一個小於p的隨機數a。
（2） 設j=0且z=a^m mod p
（3） 如果z=1或z=p-1，那麽p通過測試，可能使素數
（4） 如果j>0且z=1, 那麽p不是素數
（5） 設j=j+1。如果j且z<>p-1,設z=z^2 mod p，然後回到(4)。如果z=p-1，那麽p通過測試，可能為素數。
（6） 如果j=b 且z<>p-1，不是素數
#include<iostream.h>
#include<time.h>
#include<stdlib.h>
//隨機數產生器
//產生m~n之間的一個隨機數
unsigned long random(unsigned long m,unsigned long n)
{
srand((unsigned long)time(NULL));
return(unsigned long)(m+rand()%n);
}
//模冪函數
//返回X^YmodN
long PowMod(long x,long y,long n)
{
long s,t,u;
s=1;t=x;u=y;
while(u){
if(u&1)s=(s*t)%n;
u>>=1;
t=(t*t)%n;
}
return s;
}
//Rabin-Miller素數測試，通過測試返回1，否則返回0。
//n是待測素數。
//注意：通過測試並不一定就是素數，非素數通過測試的概率是1/4
int RabinMillerKnl(unsigned long n)
{
unsigned long b,m,j,v,i;
//先計算出m、j，使得n-1=m*2^j，其中m是正奇數，j是非負整數
m=n-1;
j=0;
while(!(m&1))
{
++j;
m>>=1;
}
//隨機取一個b，2<=b<n-1
b=random(2,m);
//計算v=b^mmodn
v=PowMod(b,m,n);
//如果v==1，通過測試
if(v==1)
{
return 1;
}
i=1;
//如果v=n-1，通過測試
while(v!=n-1)
{
//如果i==l，非素數，結束
if(i==j)
{
return 0;
}
//v=v^2modn，i=i+1
v=PowMod(v,2,n);
i++;
}
return 1;
}
intmain()
{
unsigned long p;
int count=0;
cout<<"請輸入一個數字"<<endl;
cin>>p;
for(int temp=0;temp<5;temp++)
{
if(RabinMillerKnl(p))
{
count++;
}
else
break;
}
if(count==5)
cout<<"一共通過5次測試，是素數！"<<endl;
else
cout<<"不是素數"<<endl;
return 0;
}
㈢ 判斷素數的演算法用流程圖表示對一個大於或等於100的正整數判斷它是不是一個素
開始
申請工作變數i，b，x
輸入x
i賦值2，b賦值1
A：條件判斷x%2是否等於0，是b賦值0,跳轉到B
i自加1
條件判斷i是否小於等於x整除2，是跳轉到A
B：條件判斷b是否等於1，如果條件成立則輸出: x是素數，否則輸出: x不是素數
結束