杭州交通信息网西光小学收费标准:一道C语言题目
来源：百度文库 编辑：杭州交通信息网 时间：2024/04/28 00:58:51
#include"stdlib.h"
#include"math.h"
int composite=0;
/*计算a^p mod n ,并在计算过程中实施对n的二次试探*/
int power(int a,int p,int n)
{
int x,result;
if (p==0)
result=1;
else
{
x=power(a,p/2,n);
result=(x*x)%n;
if ((result==1)&&(x!=1)&&(x!=n-1))
composite=1;
if ((p%2)==1)
result=(result*a)%n;
}
return result;
}
/*重复K次调用的Prime的蒙特卡罗算法primeMC
PrimeMC的出错概率不超过(1/4)^K，K越大，正确的概率越高*/
int primeMC(int n,int k)
{
int i,a,result;
composite=0;
for (i=1;i<=k;i++)
{
a=random(n-3)+2;
result=power(a,n-1,n);
if ((composite==1)||(result!=1))
return 0;
}
return 1;
}
void main()
{int n=5;
clrscr();
printf("2\n");
printf("3\n");
while(getch()!=27){
int k=(double)floor(log(n)/log(2));
if (primeMC(n,k)) printf("%d\n",n);
n=n+2;
}
getch();
}
这是我们算法设计的一道作业题，我做不出，求助高手。
我们知道，每个素数都被上述算法输出
但是除了所有素数外，算法可能错误的输出某些合数
说明上述情况不太可能发生，或更精确地，
证明上述算法错误地输出一个合数的概率小于1%
一楼的朋友你到底有没有看我的问题？把问题抄一遍有什么意义？
#include"stdio.h"
#include"stdlib.h"
#include"math.h"
int composite=0;
/*计算a^p mod n ,并在计算过程中实施对n的二次试探*/
int power(int a,int p,int n)
{
int x,result;
if (p==0)
result=1;
else
{
x=power(a,p/2,n);
result=(x*x)%n;
if ((result==1)&&(x!=1)&&(x!=n-1))
composite=1;
if ((p%2)==1)
result=(result*a)%n;
}
return result;
}
/*重复K次调用的Prime的蒙特卡罗算法primeMC
PrimeMC的出错概率不超过(¼)^K，K越大，正确的概率越高*/
int primeMC(int n,int k)
{
int i,a,result;
composite=0;
for (i=1;i<=k;i++)
{
a=random(n-3)+2;
result=power(a,n-1,n);
if ((composite==1)||(result!=1))
return 0;
}
return 1;
}
void main()
{int n=5;
clrscr();
printf("2\n");
printf("3\n");
while(getch()!=27){
int k=(double)floor(log(n)/log(2));
if (primeMC(n,k)) printf("%d\n",n);
n=n+2;
}
getch();
}
#include"stdio.h"
#include"stdlib.h"
#include"math.h"
int composite=0;
/*计算a^p mod n ,并在计算过程中实施对n的二次试探*/
int power(int a,int p,int n)
{
int x,result;
if (p==0)
result=1;
else
{
x=power(a,p/2,n);
result=(x*x)%n;
if ((result==1)&&(x!=1)&&(x!=n-1))
composite=1;
if ((p%2)==1)
result=(result*a)%n;
}
return result;
}
/*重复K次调用的Prime的蒙特卡罗算法primeMC
PrimeMC的出错概率不超过(¼)^K，K越大，正确的概率越高*/
int primeMC(int n,int k)
{
int i,a,result;
composite=0;
for (i=1;i<=k;i++)
{
a=random(n-3)+2;
result=power(a,n-1,n);
if ((composite==1)||(result!=1))
return 0;
}
return 1;
}
void main()
{int n=5;
clrscr();
printf("2\n");
printf("3\n");
while(getch()!=27){
int k=(double)floor(log(n)/log(2));
if (primeMC(n,k)) printf("%d\n",n);
n=n+2;
}
getch();
}