⑴ 素性测试的随机算法
费马测试 利用费马小定理来测试。 Miller-Rabin 质数测试 欧拉-雅科比测试 对于N，挑选任意的M，测试（M/N）≡M^[(N-1)/2]。如果不成立，则N为合数。否则N有一半的机率是质数。
上下素性判定法
首先，本文英文字母都表示整数，上半部B 》3N 》W，下半部B 》W 》3N。大于3的素数只有6N-1和6N+1两种形式，我们只需判定这两种数是素数还是合数即可。命题 1 对于B=36N+1 形数而言。若不定方程（3N）^2+N-（B-1）/36=W^2 有整数解，则 6（3N-W）+1 是小因子数；6（3N+W）+1 是大因子数。若不定方程 （3N）^2-N-（B-1）/36=W^2 有整数解，则 6（3N-W）-1 是小因子数；6（3N+W）-1 是大因子数。两式都无解，是素数。命题 2对于B=36N+7 形数而言。若不定方 （3N）^2+4N-（B-7）/36=W^2+W 有整数解，则 6（3N-W）+1 是小因子数，6（3N+W+1）+1 是大因子数。若不定方程 （3N+2）^2+2N+2-（B+29）/36=W^2+W 有整数解，则 6（3N+2-W）-1 是小因子数，6（3N+W+3）-1 是大因子数。两式都无解，是素数。命题 3对于B=36N+13 形数而言。若不定方程 （3N+1）^2+N-（B-13）/36=W^2 有整数解，则 6（3N+1-W）+1 是小因子数，6（3N+1+W）+1是大因子数。若不定方程 （3N+2）^2-N-（B+23）/36=W2 有整数解，则 6（3N+2-W）-1 是小因子数，6（3N+2+W）-1是大因子数。两式都无解，是素数。命题 4 对于B=36N+19 形数而言。若不定方程（3N+1）^2+4N+1-（B-19）/36=W^2 +W 有整数解，则 6（3N+1-W）+1 是小因子数；6（3N+2+W）+1 是大因子数。若不定方程 （3N+1）^2+2N+1-（B+17）/36=W^2 +W 有整数解，则 6（3N+1-W）-1 是小因子数；6（3N+2+W）-1 是大因子数。两式都无解，是素数。命题 5 对于B=36N+25 形数而言。若不定方 （3N+2）^2+N-（B-25）/36=W^2有整数解，则 6（3N+2-W）+1 是小因子数，6（3N+2+W）+1 是大因子数。若不定方程 （3N+1）^2-N-（B+11）/36=W^2有整数解，则 6（3N+1-W）-1 是小因子数，6（3N+1+W）-1 是大因子数。两式都无解，是素数。命题 6 对于B=36N+31 形数而言。若不定方程 （3N+2）^2+4N+2-（B-31）/36=W^2 +W 有整数解，则 6（3N+2-W）+1 是小因子数，6（3N+3+W）+1是大因子数。若不定方程 （3N+1）^2-4N-1-（B+5）/36=W^2+W有整数解，则 6（3N-W）-1 是小因子数，6（3N+1+W）-1是大因子数。两式都无解，是素数。命题 7对于B=36N-1 形数而言。若不定方程（3N）^2-N+（B-1）/36=W^2 有整数解，则 6（3N-W）+1 是小因子数；6（3N+W）-1 是大因子数。若不定方程 （3N）^2+N+（B-1）/36=W^2 有整数解，则 6（W-3N）-1 是小因子数；6（W+3N）+1 是大因子数。两式都无解，是素数。命题 8对于B=36N+5 形数而言。若不定方 （3N）^2+2N+（B-5）/36=W^2+W 有整数解，则 6（W-3N）+1 是小因子数，6（W+3N+1）-1 是大因子数。若不定方程 （3N+2）^2+4N+2+（B+31）/36=W^2+W 有整数解，则 6（W-3N-2）-1 是小因子数，6（W+3N+3）+1 是大因子数。两式都无解，是素数。命题 9对于B=36N+11 形数而言。若不定方程 （3N+1）^2-N+（B-11）/36=W^2 有整数解，则 6（W-3N-1）+1 是小因子数，6（W+3N+1）-1是大因子数。若不定方程 （3N+2）^2+N+(B+25）/36=W2 有整数解，则 6(W-3N-2）-1 是小因子数，6（W+3N+2）+1是大因子数。两式都无解，是素数。命题 10 对于B=36N+17 形数而言。若不定方程（3N+1）^2+2N+1+（B-17）/36=W^2 +W 有整数解，则 6（W-3N-1）+1 是小因子数；6（W+3N+2）-1 是大因子数。若不定方程 （3N+1）^2+4N+1+（B+19）/36=W^2 +W 有整数解，则 6（W-3N-1）-1 是小因子数；6（W+3N+2）+1 是大因子数。两式都无解，是素数。命题 11 对于B=36N+23 形数而言。若不定方 （3N+2）^2-N+（B-23）/36=W^2有整数解，则 6（W-3N-2）+1 是小因子数，6（W+3N+2）+1 是大因子数。若不定方程 （3N+1）^2+N+（B+13）/36=W^2有整数解，则 6（W-3N-1）-1 是小因子数，6（W+3N+1）+1 是大因子数。两式都无解，是素数。命题 12 对于B=36N+31 形数而言。若不定方程 （3N+2）^2+2N+2+（B-29）/36=W^2 +W 有整数解，则 6（W-3N-2）+1 是小因子数，6（W+3N+3）-1是大因子数。若不定方程 （3N）^2-4N+（B+7）/36=W^2+W有整数解，则 6（W-3N）-1 是小因子数，6（W+3N+1）+1是大因子数。两式都无解，是素数。
⑵ 判断一个数是否为素数的算法
找质数的方法：写出这个数的因数。再判断这个数是质数还是合数。
1、一个数除了1和本身，不再有别的约数，这样的数叫做质数或者素数。例如：2，3，5，7，11，13，17，19，23，29等等。
2、一个数，除了1和本身，还的别的因数，这样的数叫做合数。例如4、8、8、9等等。例如：2的所有因数是1和2两个，所以2是质数。例如6的所有因数是：1，2，3，6。一共是4个，所以6是合数。
找因12的因数：
1×12=12 2×6=12 3×4=12 所以12的因数有：1，2，3，4，6，12。共6个。
找因数的方法可以把这个数分成两个因数相乘的积。从一开始比较容易找，写的时候最好能从小到大写出来。重复的只能写一个。例如9的因数：1×9=9 3×3=9 9的因数是：1，3，9共3个。（重复的3只能写一个。）
⑶ 我们知道整数13是素数,求解13是素数的算法有多种方法,第一种方法用穷举法测试
素数定义：只能被1和自身整除的自然数。
13/1=13
13/2=6.5
13/3=
13/4=
13/5=
13/12=
13/13=1
发现除了1和13 能够整除，其他不行。因此是13是素数。
凡是除数是偶数的可以不用试验。因为 素数必须是奇数。奇数除偶数不是自然数。
这样就可以只试验 3，5，7，9，11，能否整除13
(3)素数测试算法扩展阅读
整数a除以整数b （ b≠0 ） ，除得的商正好是整数而没有余数我们就说a能被b整除（也可以说b能整除a ）除尽的意义甲数除以乙数，所得的商是整数或有限小数而余数也为0时，我们就说甲数能被乙数除尽， （或者说乙数能除尽甲数）这里的甲数、乙数可以是自然数，也可以是小数（乙数不能为0）。
1、能被2整除的数的特征：个位上是0、2、4、6、8。
2、能被5整除的数的特征：个位上是0或5。
3、能被3整除的数的特征： 一个数的各个数位上的数之和能被3整除，这个数就能被3整除。
⑷ Miller Rabin算法的简介
Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时， Miller-Rain算法是完成素数测试的最佳选择。通过对Miller-Rabin 算 法底层运算的优化，可以取得较以往实现更好的性能。随着信息技术的发展、网络的普及和电子商务的开展， 信息安全逐步显示出了其重要性。信息的泄密、伪造、篡改 等问题会给信息的合法拥有者带来重大的损失。在计算机中构建密码安全体系可以提供4种最基本的保护信息安全的服 务：保密性、数据完整性、鉴别、抗抵赖性，从而可以很大 程度上保护用户的数据安全。在密码安全体系中，公开密钥 算法在密钥交换、密钥管理、身份认证等问题的处理上极其有效，因此在整个体系中占有重要的地位。目前的公开密钥 算法大部分基于大整数分解、有限域上的离散对数问题和椭 圆曲线上的离散对数问题，这些数学难题的构建大部分都需 要生成一种超大的素数，尤其在经典的RSA算法中，生成的素数的质量对系统的安全性有很大的影响。目前大素数的生 成，尤其是随机大素数的生成主要是使用素数测试算法，本 文主要针对目前主流的Miller-Rabin 算法进行全面系统的分析 和研究，并对其实现进行了优化。
⑸ 判断100位的整数为素数的算法
与1到根号这个数+1相除，都不能整除就为素数
⑹ 判断一个数是否是素数的最简便算法
追求效率的话
最高的是 miller_rabin
算法
最好有一定的数论知识再去看
另一个简单方法是
可以o(n)
求出素数
然后再判断就行了
多个素数判断时效率较高
⑺ 求判断一个数是否为素数的最简单算法
追求效率的话 最高的是 Miller_Rabin 算法 最好有一定的数论知识再去看
另一个简单方法是 可以O(n) 求出素数 然后再判断就行了 多个素数判断时效率较高
⑻ 判断一个正整数是否是素数的常用算法是 A，排序法 B，回溯法 C，递归法 D，穷举法
摘要
您好，判断一个正整数是否是素数的常用算法是D穷举法
⑼ c语言求素数的算法
根据素数的性质，代码设计如下：
设计一：判断n是否能被1~n-1整除，不能整除为素数
#include<stdio.h>
int main()
{
int i, n;
scanf("%d", &n);
for (i = 2; i < n ; i++)
{
if (n%i == 0)
break;
}
if (i < n) printf("This is not a prime.");
else printf("This is a prime.");
return 0;
}
设计二：判断n是否能被2~√n间的整数整除，不能整除为素数
#include<stdio.h>
#include<math.h>
int main()
{
int n,i;
double k;
scanf("%d", &n);
k = sqrt(n);
for (i = 2; i <= k;i++)
{
if (n%i == 0) break;
}
if (i <=k) printf("This is not a prime.");
else printf("This is a prime");
return 0;
}
(9)素数测试算法扩展阅读：
1.素数的定义是只能被1和他本身整除,1不是素数.因此要判断一个数是否为素数.就要判断它能不能被比他小的所有素数整除,这是一个算法.(写到算法时,我只能写出用它除以比他小的所有数,造成运算速度低下)
2.如果一个质数大于根号n，而n可以除尽它，那么n必然也可以除尽一个更小的质数。由此可以得到一个法2较快的素数判断算法
