素数问题,费马小定理 费马小定理证明

素数问题关于这个问题其实没有什么好说的,素数大家都知道.素数就是一个数,比1大,而且只有1和它本身两个正因子,那么它就是一个素数.一般在竞赛中很少遇到直接求素数的问题,因为毕竟筛选法求素数也太基本了一点.但是有少部份的题会考关于判断一个数是否为素数.这个时候大多数人都用下面这个程序:
for(int i=2;i<=sqtr(x);i++)if(x%i==0)
这个程序简单,容易理解,可是时间复杂度实在让人无法忍受,遇到一个int64的数据规模,根本不可能在1S内可以出解,现在介绍一种RP素数判断法,也叫MILLER-RABBIN测试,在一些书上都有介绍,可是介绍得太简单,害得我这个脑袋本来就不好使的人调了半天才搞定......MR测试(MILLER-RABBIN测试,以下简称MR)是基于费马小定理的一个测试:N是一个正整数,如果存在一个整数B(0<B<N),且B^(N-1) MODN=1,那么N可能是一个素数,如果不为1,那么一定不是一个素数,这个测试基于这点,用随机算法可以随机取S个数(S可以在20-50左右),如果都满足,那么判断它是一个素数.听起来很考RP,但是如果S在50左右,它是一个素数的概率大得可以近似处理为1,在实际运用中绝对可以信赖.这个程序的瓶颈在于求B^(N-1) MOD N的值,之前我有篇文章,介绍了这种快速取模的方法,完全可以满足需要了.下面把我的程序列在下面,仅供参考:#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#define randomize() srand((unsigned)time(NULL))
long long n;
bool bs;int p(long long x,long long y)
{
long long t;
if(y==1)return x;
else
{
t=p(x,y/2);
if(y%2==1)
returnt*t*x%n;
else
returnt*t%n;
}
}
void mafei(long long n)
{
randomize();
bs=false;
for(int i=1;i<=20;i++)
{

long longs=(rand()%(120-20))+20;
if(p(s,n-1)==1)
素数问题,费马小定理 费马小定理证明
bs=true;
}
}
int main()
{
cin>>n;
mafei(n);
if(bs)
cout<<"Y"<<'n';
else
cout<<"N"<<'n';
}

  

爱华网本文地址 » http://www.413yy.cn/a/25101013/158107.html

更多阅读

网恋前应了解的五大问题,网恋的优点及危害 五大媒体优缺点

网恋前应了解的五大问题,网恋的优点及危害——简介如今科技高度发达,网络铺天盖地,互联网成为现实生活中应用最广泛、最受欢迎的传媒之一。我们在网上干的最多的事情就是聊天,聊的最多的内容就是爱情,因此网恋也逐渐的在整个网络蔓延开来

爱不是对象问题,而是能力问题 length为空或不是对象

我们都向往“一见钟情”到“白头到老”理想爱情。但是这样的完满是有条件的,我们的人格成熟了吗?我们有爱的能力了吗?弗洛姆在《爱的艺术》中指出:爱的烦恼不是对象问题,而是能力问题。爱情是生命的必需品吗?心探索:爱情中人们总是会遭遇

声明:《素数问题,费马小定理 费马小定理证明》为网友爱情不算什么分享!如侵犯到您的合法权益请联系我们删除