费马小定理程序（费马小定理的推论）

今天给各位分享费马小定理程序的知识，其中也会对费马小定理的推论进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

微信号：cloud7591
如需了解更多，欢迎添加客服微信咨询。
复制微信号

本文目录一览：

• 1、求C语言中 判断素数的 代码!!!!!
• 2、费马小定理是什么
• 3、大数组合取模,Lucas定理,费马小定理的运用

求C语言中 判断素数的 代码!!!!!

基本思想：把m作为被除数，将2—INT（ ）作为除数，如果都除不尽，m就是素数，否则就不是。

可用以下程序段实现：

void main()

{ int m,i,k;

printf("please input a number:\n");

scanf("%d",m);

k=sqrt(m);

for(i=2;ik;i++)

if(m%i==0) break;

if(i=k)

printf("该数是素数");

else

printf("该数不是素数");

}

将其写成一函数,若为素数返回1，不是则返回0

int prime( m%)

{int i,k;

k=sqrt(m);

for(i=2;ik;i++)

if(m%i==0) return 0;

return 1;

}

扩展资料：

筛法求素数

一、基本思想

用筛法求素数的基本思想是：

把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

如有：

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

1不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是：

3 5 7 9 11 13 15 17 19 21 23 25 27 29

剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为：

2 3 5 7 11 13 17 19 23 29

二、C++实现

1、算法一：令A为素数，则A*N（N1;N为自然数）都不是素数。

#define range 2000

bool

IsPrime[range+1];

/*set函数确定i是否为素数，结果储存在IsPrime[i]中，此函数在DEV

C++中测试通过*/

void set(bool IsPrime[])

{

int i,j;

for(i=0;i=range;++i)

IsPrime[i]=true;

IsPrime[0]=IsPrime[1]=false;

for(i=2;i=range;++i)

{

if(

IsPrime[i])

{

for(j=2*i;j=range;j+=i)

IsPrime[j]=false;}}}

2、

说明：解决这个问题的诀窍是如何安排删除的次序，使得每一个非质数都只被删除一次。 中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。

例如，16=2^4，18=2 * 3^2，691488=2^5 * 3^2 * 7^4等。如果把因式分解中最小质数写在最左边，有16=2^4，18=2*9,691488=2^5 * 21609,；

换句话说，把合数N写成N=p^k * q，此时q当然是大于p的，因为p是因式分解中最小的质数。由于因式分解的唯一性，任何一个合数N，写成N=p^k * q;的方式也是唯一的。

由于q=p的关系，因此在删除非质数时，如果已知p是质数，可以先删除p^2,p^3,p^4,... ，再删除pq,p^2*q,p^3*q,...,（q是比p大而没有被删除的数），一直到pqN为止。

因为每个非质数都只被删除一次，可想而知，这个程序的速度一定相当快。依据Gries与Misra的文章，线性的时间，也就是与N成正比的时间就足够了（此时要找出2N的质数）。

代码如下：

#includeiostream

#includecmath

using namespace std;

int main()

{

int N; cinN;

int *Location=new int[N+1];

for(int i=0;i!=N+1;++i)

Location[i]=i;

Location[1]=0; //筛除部分

int p,q,end;

end=sqrt((double)N)+1;

for(p=2;p!=end;++p)

{

if(Location[p])

{

for(q=p;p*q=N;++q)

{

for(int k=p*q;k=N;k*=p)

Location[k]=0;

}

}

}

int m=0;

for(int i=1;i!=N+1;++i)

{

if(Location[i]!=0)

{

coutLocation[i]" ";

++m;

}

if(m%10==0) coutendl;

}

coutendlmendl;

return 0;

}

该代码在Visual Studio 2010 环境下测试通过。

以上两种算法在小数据下速度几乎相同。

参考资料：百度百科-筛法求素数

费马小定理是什么

[编辑本段]费马小定理

费马小定理是数论中的一个重要定理,其内容为:

假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）

[编辑本段]费马小定理的历史

皮埃尔•德•费马于1636年发现了这个定理，在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个质数的要求，但是这个要求实际上是不存在的。与费马小定理相关的有一个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当2^(p-1)≡1(mod p)，p是一个质数。

假如p是一个质数的话，则2^(p-1)≡1(mod p)成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如2^(p-1)≡1(mod p)成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。因此整个来说这个猜想是错误的。一般认为中国数学家在费马前2000年的时候就已经认识中国猜测了，但也有人认为实际上中国猜测是1872年提出的，认为它早就为人所知是出于一个误解。

[编辑本段]费马小定理的证明

一、准备知识：

引理1．剩余系定理2

若a,b,c为任意3个整数，m为正整数，且(m,c)=1,则当ac≡bc(modm)时，有a≡b(modm)

证明：ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质，c可以约去，a–b≡0(mod m)可得a≡b(mod m)

引理2．剩余系定理5

若m为整数且m1,a[1],a[2],a[3],a[4],…a[m]为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。

证明：构造m的完全剩余系（0,1,2,…m-1），所有的整数必然这些整数中的1个对模m同余。取r[1]=0,r[2]=1,r[3]=2,r[4]=3,…r=i-1,1i=m。令(1)：a[1]≡r[1](mod m),a[2]≡r[2](mod m),a≡r(mod m)(顺序可以不同),因为只有在这种情况下才能保证集合{a1,a2,a3,a4,…am}中的任意2个数不同余，否则必然有2个数同余。由式(1)自然得到集合{a1,a2,a3,a4,…am}对m构成完全剩余系。

引理3．剩余系定理7

设m是一个整数，且m1，b是一个整数且(m,b)=1。如果a1,a2,a3,a4,…am是模m的一个完全剩余系，则ba[1],ba[2],ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系。

证明：若存在2个整数ba和ba[j]同余即ba≡ba[j](mod m)，根据引理2则有a≡a[j](mod m)。根据完全剩余系的定义和引理4（完全剩余系中任意2个数之间不同余，易证明）可知这是不可能的，因此不存在2个整数ba和ba[j]同余。由引理5可知ba[1],ba[2],ba[3],ba[4],…ba[m]构成模m的一个完全剩余系。

引理4．同余定理6

如果a,b,c,d是四个整数，且a≡b(mod m),c≡d(mod m),则有ac≡bd(mod m)

证明：由题设得ac≡bc(mod m),bc≡bd(mod m)，由模运算的传递性可得ac≡bc(mod m)

二、证明过程：

构造素数p的完全剩余系P={1,2,3,4…(p-1)}，因为(a,p)=1，由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一个完全剩余系。令W=1*2*3*4…*(p-1)，显然W≡W(mod p)。令Y=a*2a*3a*4a*…(p-1)a,因为{a,2a,3a,4a,…(p-1)a}是p的完全剩余系，由引理2可知A中所有元素必然满足a≡1(mod p),2a≡2(modp),…(p-1)a≡p–1(mod p)。由引理4可得a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(mod p)即W*a^(p-1)≡W(modp)。易知(W,p)=1，由引理1可知a^(p-1)≡1(modp)

[编辑本段]费马小定理在数论中的地位

费马小定理是数论四大定理（威尔逊定理，欧拉定理(数论中的欧拉定理，即欧拉函数)，中国剩余定理和费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况（见于词条“欧拉函数”）。

[编辑本段]费马小定理的实际应用

如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。

对于中国猜测稍作改动，即得到判断一个数是否为质数的一个方法：

如果对于任意满足1 b p的b下式都成立：

b^(p-1)≡1(mod p)

则p必定是一个质数。

实际上，没有必要测试所有的小于p的自然数，只要测试所有的小于p的质数就可以了。

这个算法的缺点是它非常慢，运算率高；但是它很适合在计算机上面运行程序进行验算一个数是否是质数。

大数组合取模,Lucas定理,费马小定理的运用

从一个例题：【HDU 3037】 Saving Beans 来开始Lucas定理的应用。

题目大意为：松鼠要从n棵树上摘一共m个豆子，结果的方案数对素数p（不大于1e5）取模，求解。

思路：

可以理解为m个豆子分为n份，求分的方法个数。

由插板法来对m个数进行划分，由于可能某棵树没有摘豆子，可以理解为：x1+x2+x3+……+xn=m的解的个数，即为C(m+n-1,n-1)。（将m颗豆子加上n-1个板子的位置，得到的序列再从中取n-1个板子的位置）=C(m+n-1,m)。

由于m的值取0~m，那么就得sum=C(n-1,0)+C(n,1)+C(n+1,2)+C(n+2,3)+……+C(m+n-1,m)。

利用公式C（n，r）=C（n-1，r）+C（n-1，r-1）=C（n-1，r）+C（n-2，r-1）+C（n-3，r-2）……

sum=C（n+m，m）。

也就是说，接下来的算法变成了C（n+m，m）%p。

然后就是Lucas定理的运用：

Lucas（m，n，p）=C（m%p，n%p，p）✲Lucas（m/p，n/p，p）。

Lucas（x，0，p）=1。

这里可以采用的方法是递归求解。

简单的理解就是：

以求解n! % p 为例，把n分段，每p个一段，每一段求得结果是一样的。但是需要单独处理每一段的末尾p,2p,...,把p提取出来，会发现剩下的数正好又是(n/p)! ，相当于划归了一个子问题，这样递归求解即可。

这个是单独处理n！的情况，当然C(n,m)就是n！/(m! *（n－m）！），每一个阶乘都用上面的方法处理的话，就是Lucas定理了.

Lucas最大的数据处理能力是p在10^5左右。

而C(a,b) =a! / ( b! ✲ (a-b)! ) mod p

其实就是求 ( a! / (a-b)!) ✲ ( b! )^(p-2) mod p

上面这一步变换是根据费马小定理：假如p是质数，且a,p互质，那么a的（p-1）次方除以p的余数恒为1,

那么a和a^(p-2)互为乘法逆元，则（b / a) = (b * a^(p-2) ) mod p)

b!与b! (p-2)互为乘法逆元，即b!✲b! (p-2)=1，那么，

//快速幂a^b % k

//求C(n, m)%p p最大为10^5 n, m可以很大！

用下面的Lucas定理程序实现就能得出结果，实现过程中要注意乘法时的强制转换

关于费马小定理程序和费马小定理的推论的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。