判断质数的算法

Ⅰ 任意给定一个正整数n，设计出判断n是否为质数的一个算法

首先，基本的方法就是用这个数除以小于它的所有质数看余数
但n太大的话，这需要很大的质数表
因此n太大的情况下，基本都是用分布式运算找质数的
即每个数让终端上的一个人去验证，有结果了再提交上来
通常编程，所输入的质数不能太大

Ⅱ 判断一个数是否是质数

判断一个数是否是质数
最暴力的解法
利用质数的性质：设i为质数，则i只能被 1 和 i整除。
因此对于i，我们可以令 2..i-1 依次除以i，如果均不能被整除，则说明是质数。
代码如下
private static boolean isPrime1(int nr) {
for (int i = 2; i < nr; i++) {
if (nr % i == 0) return false;
}
return true;
}123456123456

稍微暴力的方法
同样利用其性质，但我们可以注意到，当 x > i / 2 时，则 x 肯定不能被 i 整除。
对于i，我们可以令 2..x 依次除以i，其中x为sqrt(i)
代码如下
private static boolean isPrime2(int nr) {
for (int i = 2; i*i <= nr; i++) {
if (nr % i == 0) return false;
}
return true;
}123456123456

效率更高的算法
提供一个数组 nums = {2, 3, 4, 5,... 17}
我们知道 nums[0] 为质数，将nums中所有能被nums[0]整除的数移除，此时数组为 nus = {2, 3, 5, 7, 9, 11, 13, 15, 17}
接着将所有能被 3 整除的数移除。此时为 nums = {2, 3, 5, 7, 11, 13, 17}
接下来的数是 5，因为 5*5 > 17，所以移除过程结束。此时的nums值为输入nums中的所有素数。
上面的步骤之所以正确是因为：合数必定可以由质数相乘得到，则对任意质数i，如果其不能被sqrt(i)前的所有质数整除，则其必定为质数（小于 sqrt(i) 的合数必定可以被小于 sqrt(i) 的质数合成）。
代码如下
private static void primeList(List<Integer> nums) {
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i)*nums.get(i) <= nums.get(nums.size()-1)) {
for (int j = i+1; j < nums.size(); j++) {
if (nums.get(j) % nums.get(i) == 0) nums.remove(j);
}
} else {
return ;
}
}
}12345678910111234567891011

此算法存在的问题也很明显，说它是判断一个数是否是质数获取不太准确，其作用应该是 “打印出小于等于某值的所有质数”
使用素数表
上面的算法有一个缺陷，它对输入数组要求较高，要求包含了数组最大值之前的所有素数，且是已排序的。也就是说它不能用来直接判断一个数是否是素数。
通常情况下，我们会使用一个素数表。接着用来整除的元素便可以从这个素数表中获取
这种算法的局限在于素数表是有限的，对于超出素数表最大值平方的数则需要加上上述方法二的步骤才能判断（尽管这种情况不多）。
算法实现同上，只是此时直接从素数表获取素数即可
http://blog.csdn.net/lingeors/article/details/56288375?locationNum=13&fps=1

Ⅲ 任意给定一个正整数n，设计出判断n是否为质数的一个算法．

（1）当n=1时，n既不是质数，也不是合数；
（2）当n=2时，n是质数；
（3）当n≥3时，从2到n-1依次判断是否存在n的因数（因数1除外），若存在，则n是合数；若不存在，则n是质数．

Ⅳ 设计一个算法判断一个数是不是质数

算法分析：（1）根据质数的定义，可以这样判断：依次用2—6除7，如果它们中有一个能整除7，则7不是质数，否则7是质数.
算法如下：（1）第一步，用2除7，得到余数1.因为余数不为0，所以2不能整除7.
第二步，用3除7，得到余数1.因为余数不为0，所以3不能整除7.
第三步，用4除7，得到余数3.因为余数不为0，所以4不能整除7.
第四步，用5除7，得到余数2.因为余数不为0，所以5不能整除7.
第五步，用6除7，得到余数1.因为余数不为0，所以6不能整除7.因此，7是质数.
（2）类似地，可写出“判断35是否为质数”的算法：第一步，用2除35，得到余数1.因为余数不为0，所以2不能整除35.
第二步，用3除35，得到余数2.因为余数不为0，所以3不能整除35.
第三步，用4除35，得到余数3.因为余数不为0，所以4不能整除35.
第四步，用5除35，得到余数0.因为余数为0，所以5能整除35.因此，35不是质数.
点评：上述算法有很大的局限性，用上述算法判断35是否为质数还可以，如果判断1997是否为质数就麻烦了，因此，我们需要寻找普适性的算法步骤.

Ⅳ 求质数方法

筛法求质数：

用筛法求质数的基本思想是：把从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

(5)判断质数的算法扩展阅读：

质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中，将会因为找质数的过程过久，使即使取得信息也会无意义。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。。

参考资料：

网络--筛法求素数

Ⅵ python求质数的算法

很早 的一个 函数

Ⅶ 请写出判断n(n＞2)是否为质数的算法.

算法如下： 第一步，给定大于2的整数n. 第二步，令i=2. 第三步，用i除n,得到余数r. 第四步，判断“r=0”是否成立.若是，则n不是质数，结束算法；否则，将i的值增加1，仍用i表示. 第五步，判断“i＞（n-1）”是否成立.若是，则n是质数，结束算法；否则，返回第三步. 分析：对于任意的整数n(n＞2)，若用i表示2—(n-1)中的任意整数，则“判断n是否为质数”的算法包含下面的重复操作：用i除n,得到余数r.判断余数r是否为0，若是，则不是质数；否则，将i的值增加1，再执行同样的操作. 这个操作一直要进行到i的值等于(n-1)为止.

Ⅷ 如何求一个数组中的数是否为质数

根据质数的定义，在判断一个数n是否是质数时，只要用1至n-1去除n，看看能否整除即可。
还有更好的办法：先找一个数m，使m的平方大于n，再用小于等于m的质数去除n（n为被除数），如果都不能整除，则n必然是质数。如我们要判断1993是不是质数，50*50>1993，那么只要用1993除以<50的质数看是否能整除，若不能即为质数。100以内的质数有25个，还是比较好记的，只要记熟100以内质数，就可以快速判断10000以内的数是不是质数。
100以内的质数有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，在100内共有25个质数。

只有1和它本身两个因数的自然数，叫质数（或称素数）。（如：由2÷1=2，2÷2=1，可知2的因数只有1和它本身2这两个约数，所以2就是质数。与之相对立的是合数：“除了1和它本身两个因数外，还有其它因数的数，叫合数。”如：4÷1=4，4÷2=2，4÷4=1，很显然，4的因数除了1和它本身4这两个因数以外，还有因数2，所以4是合数。）

Ⅸ 寻找质数的算法

没有什么好的办法,如果用程序,就计算n除以2到根号n最接近的整数,如果都不能整除,n就是质数
比如101,要计算19除以2,3,4,5直到10,如果都不能整除,就是质数.
如果你要手动计算,就挨个写,2,3,5,7,11,13,如果数字足够大,不需要像程序一样挨个除,只需要除以比它小的质数就可以了.

Ⅹ 判断一个数是否为素数的算法

找质数的方法：写出这个数的因数。再判断这个数是质数还是合数。
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只能写一个。）