24小时热门版块排行榜

返回列表

zyj8119

木虫 (著名写手)

模拟EPI: 10
应助: 65 (初中生)
贵宾: 0.003
金币: 915.1
散金: 1440
红花: 35
帖子: 2936
在线: 1329.4小时
虫号: 664177
注册: 2008-11-29
性别: GG
专业: 理论和计算化学

[交流] 【转帖】素数测试（蒙特卡罗算法）已有1人参与

CODE:

//素数测试的蒙特卡罗算法

/*

使用素数判定必要条件的费马小定理及二次探测定理

*/

#include 

#include 

#include "utils.cpp"

#include "random.hpp"

void power(unsigned int a,unsigned int p,unsigned int n,unsigned int &result,bool &composite)

{

    unsigned int x;

    if(p==0) 

        result=1;

    else{

        power(a,p/2,n,x,composite);    //递归计算

        result=mod(x*x,n);

        if((result==1) &&(x!=1) && (x!=n-1))  //x^2=1(mod n) x!=1 && x!=n-1,则n为合数

            composite=true;

        if((p%2)==1)

            result=(result*a)%n;

    }

}

bool Prime(unsigned int n)

{// 素数测试的蒙特卡罗算法

   RandomNumber rnd;

   unsigned int a, result;

   bool composite=false;

   a=rnd.Random(n-3)+2;

   power(a,n-1,n,result,composite);

   if (composite||(result!=1)) 

       return false;

   else 

       return true;

}

bool PrimeMC(unsigned int n,unsigned int k){//分析素数的过程

    RandomNumber rnd;

    unsigned int a,result;

    bool composite=false;

    for(unsigned int i=1;i<=k;i++){

        a=rnd.Random(n-3)+2; //a<-[2:n-2]

        power(a,n-1,n,result,composite);

        if(composite || (result!=1))

            return false;

    }

    return true;

}

int main(){

    char *addr="gdgzzch.blog.163.com";

    printf("本程序来自:%s\n",addr);

    FILE *fp=fopen("prime_input.txt","r");//输入流文件

    if(fp==NULL){

        printf("输入文件不存在!\n");

    }

    int num;    //测试的素数个数

    fscanf(fp,"%d",&num);

    int n;

    bool isprime;

    for(int i=1;i<=num;i++){

        fscanf(fp,"%d",&n);

        isprime=PrimeMC(n,6);

        printf("%d: ",n);

        if(isprime)

            printf("素数\n");

        else

            printf("合数\n");

    }

    return 1;

}