求质数方法
发布网友
发布时间：2022-04-26 10:03
共5个回答
热心网友
时间：2022-06-27 03:30
筛法求质数：
用筛法求质数的基本思想是：把从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
扩展资料：
质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中，将会因为找质数的过程过久，使即使取得信息也会无意义。
在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。。
参考资料：
百度百科--筛法求素数
热心网友
时间：2022-06-27 03:30
方法一：
i=2;n=0
while i<3000:
j=1; k=0
while j<=i:
if i%j==0:
k+=1
if j==i and k==2:
n+=1
print ("Number %d is: %d"%(n,i))
j+=1
i+=1
方法二：
i = 2;k=0
while(i < 3000):
j = 2
while(j <= (i/j)):
if not(i%j): break
j = j + 1
if (j > i/j) : k=k+1;print ("第%d个素数是%d"%(k,i))
i = i + 1
扩展资料：
通项公式
素数及伪素数通项公式：
把它拓展到实数那么它的切线为:
由切线方程知，素数永远在斜率3的折线上摆动，最大斜率3+ ，最小斜率3- 。
素数的变量n的通项公式：
有以上公式能够确定伪素数及素数，那么通过对其变量n的识别，我们可以写出任意素数或伪素数
先确定伪素数的变量n,用n（x,y）来表示它，变量是个三维变量，公式如下：
n为偶数时：x,y 均自然数
n为奇数时：
满足以上条件时是P（n）为素数。
参考资料：百度百科--质数
热心网友
时间：2022-06-27 03:31
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其它自然数整除的数。换句话说，仅仅有两个正因数（1和自己）的自然数即为素数。
热心网友
时间：2022-06-27 03:31
质数是没有规律的 只有规则！
不过我有简单的算法能够很快算出某个数是不是质数，只是相对简单！
平常我们算一个数是不是质数的时候，通常是用本数除以比1大 比本数小的所有数，看他们是不是能整除！
其实你有没有考虑到有一半以上的数 是没必要相除的
举例吧 比如101
那么我们用51以上的数字相除就完全没有必要，因为肯本除不开的。51以上的数 乘以最小的自然数 就已经大于102了 结论很明显了吧。
这样就省去了一半的计算时间了！ 其实还不止。
我直接说结论吧：
想判断一个数是不是质数， 只需要求出这个数的平方根（仍以101举例）是10多一点点。我们可以把那点点省去 呵呵
之后算出10一下的所有质数 2，3，5，7 剩下的只需用101 除2，3，5，7 就可以了，如果能除开，那么就不是质数，如果不能除开，那么101 就是质数！
最后的结论就是：
判断一个数是不是质数，只需要他能不能被被他平方根小的所有质数除开。
这样的话，当我们判断非常大的数字是不是质数的时候，就能省下很多的计算了！
原因也很简单啊 所有偶数都是质数相乘得出来的！
热心网友
时间：2022-06-27 03:32
求素数的方法有很多种，最简单的方法是根据素数的定义来求。对于一个自然数N，用大于1小于N的各个自然数都去除一下N，如果都除不尽，则N为素数，否则N为合数。
但是，如果用素数定义的方法来编制计算机程序，它的效率一定是非常低的，其中有许多地方都值得改进。
第一，对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数，所以不
必再用其他的数去除。
第二，对于N来说，只需用小于N的素数去除就可以了。例如，如果N能被15整除，实际
上就能被3和5整除，如果N不能被3和5整除，那么N也决不会被15整除。
第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明：
如果N是合数，则一定存在大于1小于N的整数d1和d2，使得N=d1×d2。
如果d1和d2均大于√N，则有：N＝d1×d2>√N×√N＝N。
而这是不可能的，所以，d1和d2中必有一个小于或等于√N。
基于上述分析，设计算法如下：
(1)用2，3，5，7逐个试除N的方法求出100以内的所有素数。
(2)用100以内的所有素数逐个试除的方法求出10000以内的素数。
首先，将2，3，5，7分别存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一个素数，只要不大于100，就依次存放在A数组中的一个单元 中。当我们求100—10000之间的素数时，可依次用a[1]－a[2]的素数去试除N，这个范围内的素数可以不保存，直接打印。
