关于go语言素数相乘取余的信息

谁能找到三个素数相乘以得到的数，可以是一个素数

这样的数是不存在的，因为三个素数相乘后，至少还可以分解成这个素数与它的平方的乘积，就不是素数了。

创新互联公司是一家专业提供昆山企业网站建设,专注与成都网站设计、网站建设、html5、小程序制作等业务。10年已为昆山众多企业、政府机构等服务。创新互联专业的建站公司优惠进行中。

怎样知道一个数是否是素数？？

拿那个数分别去除以2,3,5,7.如果都有余数则这个数一定是一个素数.以下vfp程序将计算出长度小于20位的所有素数并将其结果逐行逐列存入一个有10列的素数表中.

SELECT 1

SET ESCAPE on

USE 素数表.dbf

INSERT blank

DIMENSION a(1)

a=1

f=1

DO while a99999999999999999999

b=MOD(a,2)

c=MOD(a,3)

d=MOD(a,5)

e=MOD(a,7)

IF b#0.and.c#0.and.d#0.and.e#0.and.a#1.or.a=2.or.a=3.or.a=5.or.a=7

DO case

CASE f=1

g="一"

CASE f=2

g="二"

CASE f=3

g="三"

CASE f=4

g="四"

CASE f=5

g="五"

CASE f=6

g="六"

CASE f=7

g="七"

CASE f=8

g="八"

CASE f=9

g="九"

CASE f=10

g="十"

ENDCASE

GO bott

command1="gather from a"+" fields "+g

command1

f=f+1

IF f10

f=1

INSERT blank

ENDIF

ENDIF

a=a+1

ENDDO

=messagebox("长度20位以下(含)的所有素数运算完毕！",0+64+0,"运算完成")

USE

CLOSE all

素数表.dbf结构从略.

1024位素数相乘之后的结果最大位数多少？

1024位素数*1024位素数=2047~2048位合数，

2047~2048位合数=两个1024位素数的乘积，程序应该好编，但是计算可能电脑吃不消，

首先1024位素数表就很难造出，

然后找出其中两个素数的积等于已知的合数，虽然只要单循环，但是循环次数达到10^1024，电脑很困难，

10^1024这个数字太大了，关键不是计算这么大的数据，这么大的数据，计算若干次不是问题，但是计算次数要达到这么多，关键是循环的次数太大，就算计算机的计算能力，每秒钟 1亿亿 次，那也只是 10^16，需要时间10^1024/10^16=10^1008秒，10^16也就是个零头，

当然小于等于n的素数的个数~n/lnn，n 越大，素数越稀疏，

粗略估算 1024位素数的个数，

10^1024/ln(10^1024)-10^1023/ln(10^1023)

=10^1024/(1024*ln10)-10^1023/(1023*ln10)

=(10^1021-10^1020)/2.3

=3.9*10^1920

就算开一下平方再除以2，10^960 循环次数也不得了啊，

关于素数

素数

素数，又称质数，是只有两个正因数（1和自己）的自然数。 比1大但不是素数的数称之为合数，而1和0既非素数也非合数。素数的属性称为素性，素数在数论中有着非常重要的地位。

关于素数

最小的素数是2，而最大的素数并不存在，这一点欧几里德已在其《几何原本》中证明。 围绕素数存在很多的数学问题、数学猜想、数学定理，较为著名的有孪生素数猜想、哥德巴赫猜想等等。 素数序列的开头是这样：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，101，103，107，109，113。

在抽象代数的一个分支－环论中，素元素有特殊的含义，在这个含义下，任何素数的加法的逆转也是素数。换句话说，将整数Z的集合看成是一个环，-7是一个素元素。不管怎样，数学领域内，提到素数通常是指正素数。 算术基本定理说明每个正整数都可以写成素数的乘积，因此素数也被称为自然数的“建筑的基石”。

素数的数目

素数是无穷多的，对这个论断，现在所已知的最古老的检验方法是欧几里德在他的几何原本中提出来的。他的检验方法可以简单地总结如下：取有限个数的素数，因为要做自变量我们假设全部的素数都存在，将这些素数相乘然后加1，得到的数是不会被这些素数中的任何一个整除的，因为无论除哪个总会余1。因此这个数要么本身就是个素数，要么存在不在这个有限集合内的约数。因此我们开始用的集合不包含所有的素数。 别的数学家也给出了他们自己的证明。欧拉证明了全部素数的倒数和发散到无穷的。恩斯特·库默的证明尤其简洁，Furstenberg用一般拓扑证明。 尽管整个素数是无穷的，仍然有人会问“100000以下有多少个素数?”，“一个随机的100位数多大可能是素数?”。素数定理可以此问题。

寻找素数

寻找在给定限度内的素数排列，埃拉托斯特尼筛法法是个很好的方法。然而在实际中，我们往往是想知道一个给定数是否是素数，而不是生成一个素数排列。进而，知道答案是很高的概率就是已经很满意的了，用素性测试迅速地检查一个给定数（例如，有几千位数的长度）是否是素数是可能的。典型的方法是随机选取一个数，然后围绕着这个数和可能的素数N检查一些方程式。几个整数后，它宣布这个数是明显的和数或者可能是素数。这种方法是不完美的，一些测试，不论是否选取一个随机数都有可能将一些合数判断成可能的素数，这就引出了另一种数伪素数。 目前最大的已知素数是2^-1（此数字位长度是7,816,230），它是在2005年2月18日由GIMPS计划发现。这计划也在2004年5月15日发现了第二大的已知素数2^-1（此数字位长度是7,235,733）。 数学家一直努力找寻产生素数的公式，但截至目前为止，并没有一个函数或是多项式可以正确产生所有的素数。历史上有许多试验的例子：17世纪初法国数学家梅森(Mersenne)在他的一个著作当中讨论了这样一种我们现在称之为梅森素数的素数，Mp=2^p-1，本来以为只要p是一个素数，n=2^-1就会是一个素数，这在p=3，p=5，p=7都是正确的，但是p=11时 2^-1=2047=23\times 89就不是素数了。

检验素数

检查一个正整数N是否为素数，最简单的方法就是试除法，将该数N用小于等于\sqrt的所有素数去试除，若均无法整除，则N为素数。

未解之谜

- 哥德巴赫猜想：是否每个大於2的双数均可写成两个质数之和？

- 孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？

- 斐波那契数列是否存在无穷多的素数？

- 是否存在无穷多梅森素数？

- 在n^2与(n+1)^2之间每隔n就有一个素数？

- 是否存在无穷个形式如n^2+1的素数？

- 黎曼猜想

- 是否存在不定长的素数算术级数？

素数的应用

素数近来被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入素数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找素数的过程（分解质因数）过久而无法解读信息。

素数与素数相乘，积是什么？

合数。一个数除了1和它本身就没有别的因数的数是质数(素数)，既然有两个数相乘，就相当于至少有一个因数，加上1和它本身就是3个因数，就是合数。

C语言取余的原理是怎么回事？ 比如 int X，Y X-X/Y*Y=x%y

取余实际上就是模运算

基本理论

基本概念：

给定一个正整数p，任意一个整数n，一定存在等式 n = kp + r ；

其中k、r是整数，且 0 ≤ r p，称呼k为n除以p的商，r为n除以p的余数。

对于正整数p和整数a,b，定义如下运算：

取模运算：a % p（或a mod p），表示a除以p的余数。

模p加法：(a + b) % p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则(a + b) % p = r。

模p减法：(a-b) % p ，其结果是a-b算术差除以p的余数。

模p乘法：(a * b) % p，其结果是 a * b算术乘法除以p的余数。

说明：

1. 同余式：正整数a，b对p取模，它们的余数相同，记做 a ≡ b % p或者a ≡ b (mod p)。

2. n % p得到结果的正负由被除数n决定,与p无关。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。

!--[if !supportLineBreakNewLine]--

!--[endif]--

基本性质

（1）若p|(a-b)，则a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)

（2）(a % p)=(b % p)意味a≡b (% p)

（3）对称性：a≡b (% p)等价于b≡a (% p)

（4）传递性：若a≡b (% p)且b≡c (% p) ，则a≡c (% p)

运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

(a + b) % p = (a % p + b % p) % p （1）

(a - b) % p = (a % p - b % p) % p （2）

(a * b) % p = (a % p * b % p) % p （3）

ab % p = ((a % p)b) % p （4）

结合率： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5）

((a*b) % p * c)% p = (a * (b*c) % p) % p （6）

交换率： (a + b) % p = (b+a) % p （7）

(a * b) % p = (b * a) % p （8）

分配率： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）

重要定理：若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）

若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11）

若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，

(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）

若a≡b (% p)，则对于任意的c，都有ac≡ bc (%p)； （13）

编辑本段

基本应用

1.判别奇偶数

奇偶数的判别是模运算最基本的应用，也非常简单。易知一个整数n对2取模，如果余数为0，则表示n为偶数，否则n为奇数。

C++实现功能函数：

/*

函数名：IsEven

函数功能：判别整数n的奇偶性。能被2整除为偶数，否则为奇数

输入值：int n，整数n

返回值：bool，若整数n是偶数，返回true，否则返回false

*/

bool IsEven(int n)

{

return (n % 2 == 0);

}

2.判别素数

一个数，如果只有1和它本身两个因数，这样的数叫做质数（或素数）。例如 2，3，5，7 是质数，而 4，6，8，9 则不是，后者称为合成数或合数。

判断某个自然数是否是素数最常用的方法就是试除法：用比该自然数的平方根小的正整数去除这个自然数，若该自然数能被整除，则说明其非素数。

C++实现功能函数：

/*

函数名：IsPrime

函数功能：判别自然数n是否为素数。

输入值：int n，自然数n

返回值：bool，若自然数n是素数，返回true，否则返回false

*/

bool IsPrime(unsigned int n)

{

unsigned maxFactor = sqrt(n); //n的最大因子

for (unsigned int i=2; i=maxFactor; i++)

{

if (n % i == 0) //n能被i整除，则说明n非素数

{

return false;

}

}

return true;

}

3. 最大公约数

求最大公约数最常见的方法是欧几里德算法（又称辗转相除法），其计算原理依赖于定理：gcd(a,b) = gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b

假设d是a,b的一个公约数，则有d|a, d|b，而r = a - kb，因此d|r

因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则d | b , d |r ，但是a = kb +r

因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。

C++实现功能函数：

/*

函数功能：利用欧几里德算法，采用递归方式，求两个自然数的最大公约数

函数名：Gcd

输入值：unsigned int a，自然数a

unsigned int b，自然数b

返回值：unsigned int，两个自然数的最大公约数

*/

unsigned int Gcd(unsigned int a, unsigned int b)

{

if (b == 0)

return a;

return Gcd(b, a % b);

}

/*

函数功能：利用欧几里德算法，采用迭代方式，求两个自然数的最大公约数 函数名：Gcd

输入值：unsigned int a，自然数a

unsigned int b，自然数b

返回值：unsigned int，两个自然数的最大公约数

*/

unsigned int Gcd(unsigned int a, unsigned int b)

{

unsigned int temp;

while (b != 0)

{

temp = a % b;

a = b;

b = temp;

}

return a;

}

4．模幂运算

利用模运算的运算规则，我们可以使某些计算得到简化。例如，我们想知道3333^5555的末位是什么。很明显不可能直接把3333^5555的结果计算出来，那样太大了。但我们想要确定的是3333^5555（%10），所以问题就简化了。

根据运算规则（4）ab % p = ((a % p)b) % p ，我们知道3333^5555（%10）= 3^5555（%10）。由于3^4 = 81，所以3^4（%10）= 1。

根据运算规则（3） (a * b) % p = (a % p * b % p) % p ，由于5555 = 4 * 1388 + 3，我们得到3^5555（%10）=（3^(4*1388) * 3^3）（%10）=（（3^(4*1388)（%10）* 3^3（%10））（%10）

=（1 * 7）（%10）= 7。

计算完毕。

利用这些规则我们可以有效地计算X^N(% P)。简单的算法是将result初始化为1，然后重复将result乘以X，每次乘法之后应用%运算符（这样使得result的值变小，以免溢出），执行N次相乘后，result就是我们要找的答案。

这样对于较小的N值来说，实现是合理的，但是当N的值很大时，需要计算很长时间，是不切实际的。下面的结论可以得到一种更好的算法。

如果N是偶数，那么X^N =（X*X）^[N/2]；

如果N是奇数，那么X^N = X*X^(N-1) = X *（X*X）^[N/2]；

其中[N]是指小于或等于N的最大整数。

C++实现功能函数：

/*

函数功能：利用模运算规则，采用递归方式，计算X^N(% P)

函数名：PowerMod

输入值：unsigned int x，底数x

unsigned int n，指数n

unsigned int p，模p

返回值：unsigned int，X^N(% P)的结果

*/

unsigned int PowerMod(unsigned int x, unsigned int n, unsigned int p)

{

if (n == 0)

{

return 1;

}

unsigned int temp = PowerMod((x * x)%p, n/2, p); //递归计算（X*X）^[N/2]

if ((n 1) != 0) //判断n的奇偶性

{

temp = (temp * x) % p;

}

return temp;

}

5.《孙子问题(中国剩余定理)》

在我国古代算书《孙子算经》中有这样一个问题：

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”意思是，“一个数除以3余2，除以5余3，除以7余2.求适合这个条件的最小数。”

这个问题称为“孙子问题”.关于孙子问题的一般解法，国际上称为“中国剩余定理”.

我国古代学者早就研究过这个问题。例如我国明朝数学家程大位在他著的《算法统宗》（1593年）中就用四句很通俗的口诀暗示了此题的解法：

三人同行七十稀，五树梅花甘一枝，七子团圆正半月，除百零五便得知。

"正半月"暗指15。"除百零五"的原意是，当所得的数比105大时，就105、105地往下减，使之小于105；这相当于用105去除，求出余数。

这四句口诀暗示的意思是：当除数分别是3、5、7时，用70乘以用3除的余数，用21乘以用5除的余数，用15乘以用7除的余数，然后把这三个乘积相加。加得的结果如果比105大，就除以105，所得的余数就是满足题目要求的最小正整数解。

根据剩余定理，我把此种解法推广到有n(n为自然数）个除数对应n个余数，求最小被除数的情况。输入n个除数（除数不能互相整除）和对应的余数，计算机将输出最小被除数。

C++实现功能函数：

/*

函数名：ResidueTheorem

函数功能：运用剩余定理，解决推广了的孙子问题。通过给定n个除数（除数不能互相整除）和对应的余数，返回最小被除数

输入值：unsigned int devisor[]，存储了n个除数的数组

unsigned int remainder[]，存储了n个余数的数组

int length，数组的长度

返回值：unsigned int， 最小被除数

*/

unsigned int ResidueTheorem(const unsigned int devisor[], const unsigned int remainder[], int length)

{

unsigned int product = 1; //所有除数之乘积

for (int i=0; ilength; i++)//计算所有除数之乘积

{

product *= devisor[i];

}

//公倍数数组，表示除该元素（除数）之外其他除数的公倍数

unsigned int *commonMultiple = new unsigned int(length);

for (int i=0; ilength; i++)//计算除该元素（除数）之外其他除数的公倍数

{

commonMultiple[i] = product / devisor[i];

}

unsigned int dividend = 0; //被除数，就是函数要返回的值

for (int i=0; ilength; i++)//计算被除数，但此时得到的不是最小被除数

{

unsigned int tempMul = commonMultiple[i];

//按照剩余理论计算合适的公倍数，使得tempMul % devisor[i] == 1

while (tempMul % devisor[i] != 1)

{

tempMul += commonMultiple[i];

}

dividend += tempMul * remainder[i]; //用本除数得到的余数乘以其他除数的公倍数

}

delete []commonMultiple;

return (dividend % product); //返回最小被除数

}

6. 凯撒密码

凯撒密码（caeser）是罗马扩张时期朱利斯o凯撒（Julius Caesar）创造的，用于加密通过信使传递的作战命令。

它将字母表中的字母移动一定位置而实现加密。注意26个字母循环使用，z的后面可以堪称是a。

例如，当密匙为k = 3，即向后移动3位时，若明文为”How are you!”，则密文为”Krz duh btx!”。

凯撒密码的加密算法极其简单。其加密过程如下：

在这里，我们做此约定：明文记为m，密文记为c，加密变换记为E(key1,m)（其中key1为密钥），

解密变换记为D(key2,m)（key2为解密密钥）（在这里key1=key2,不妨记为key）。

凯撒密码的加密过程可记为如下一个变换：c≡m+key (mod n） （其中n为基本字符个数）

同样，解密过程可表示为：m≡c+key (mod n） （其中n为基本字符个数）

C++实现功能函数：

/*

函数功能：使用凯撒密码原理，对明文进行加密，返回密文 函数名：Encrypt

输入值：const char proclaimedInWriting[]，存储了明文的字符串

char cryptograph[]，用来存储密文的字符串

int keyey，加密密匙，正数表示后移，负数表示前移

返回值：无返回值，但是要将新的密文字符串返回

*/

void Encrypt(const char proclaimedInWriting[], char cryptograph[], int key)

{

const int NUM = 26; //字母个数

int len = strlen(proclaimedInWriting);

for (int i=0; ilen; i++)

{

if (proclaimedInWriting[i] = 'a' proclaimedInWriting[i] = 'z')

{//明码是大写字母，则密码也为大写字母

cryptograph[i] = (proclaimedInWriting[i] - 'a' + key) % NUM + 'a';

}

else if (proclaimedInWriting[i] = 'A' proclaimedInWriting[i] = 'Z')

{//明码是小写字母，则密码也为小写字母

cryptograph[i] = (proclaimedInWriting[i] - 'A' + key) % NUM + 'A';

}

else

{//明码不是字母，则密码与明码相同

cryptograph[i] = proclaimedInWriting[i];

}

}

cryptograph[len] = '\0';

}

/*

函数功能：使用凯撒密码原理，对密文进行解密，返回明文 函数名：Decode

输入值：char proclaimedInWriting[]，用来存储明文的字符串

const char cryptograph[]，存储了密文的字符串

int keyey，解密密匙，正数表示前移，负数表示后移（与加密相反）

返回值：无返回值，但是要将新的明文字符串返回

*/

void Decode(const char cryptograph[], char proclaimedInWriting[], int key)

{

const int NUM = 26; //字母个数

int len = strlen(cryptograph);

for (int i=0; ilen; i++)

{

if (cryptograph[i] = 'a' cryptograph[i] = 'z')

{//密码是大写字母，则明码也为大写字母，为防止出现负数，转换时要加个NUM

proclaimedInWriting[i] = (cryptograph[i] - 'a' - key + NUM) % NUM + 'a';

}

else if (cryptograph[i] = 'A' cryptograph[i] = 'Z')

{//密码是小写字母，则明码也为小写字母

proclaimedInWriting[i] = (cryptograph[i] - 'A' - key + NUM) % NUM + 'A';

}

else

{//密码不是字母，则明码与明密相同

proclaimedInWriting[i] = cryptograph[i];

}

}

proclaimedInWriting[len] = '\0';

}