#include?
#include?
#include?
#include?

bool?witness（int?along?n）
{
????//得到n-1的二進制表示
????int?div=（int）?n;
	int?b[128];
	int?k=0;
	int?i;
	while（div!=0）
	{
????????b[k]=div%2;
		div=div/2;
		k++;
	}
	//計算
	int?x;
	int?d=1;
	for（i=k-1;i>=0;i--）
	{
		x=d;
		d=（d*d）%n;
		if（d==1&&x!=1&&x!=n-1）?
			return?true;
		if（b[i]==1）?
			d=（d*a）%n;
	}
	if（d!=1）??
		return?true;
	else?
		return?false;

}
int?main（）
{
????long?digit;
	int?a;
	int?i=0;
	int?j;
	srand（?（unsigned）time（?NULL?）?）;???//以時間為獲得產生隨機數的種子
	while（1）
	{
		digit=rand（）;
		while（digit%2==0）
			digit=rand（）;???????//隨機產生一個奇數
???????cout<<“the?cow?prime?is?“</*??????i=0;
		while（i		{
			//a為小于digit的隨機數
		a=（int）（digit/（float）RAND_MAX?*?rand（））;
		cout<		//素數測試（Miller_Rabin測試法），返回true表示不是素數
		if（witness（adigit））??break;
		i++;
		}
*/	for（i=2;i<=sqrt（digit）;i++）
	{
		if（digit%i==0）??break;
	}

		cout<<“i=“<
		if（i+1>（int）sqrt（digit））
		{
			cout<<“digit?“<????????	break;
		}
	}
	
	return?0;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????1198??2003-12-04?20:49??prime.cpp

-----------?---------??----------?-----??----

?????????????????1198????????????????????1