求质数的文章: [原创]求质数(C语言描述) 【问题描述】:
试编写一个程序,找出2->N之间的所有质数。希望用尽可能快的方法实现。
【问题分析】:
这个问题可以有两种解法:一种是用“筛子法”,另一种是从2->N检查,找出质数。
先来简单介绍一下“筛法”,求2~20的质数,它的做法是先把2~20这些数一字排开:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
先取出数组中最小的数,是2,则判断2是质数,把后面2的倍数全部删掉。
2 | 3 5 7 9 11 13 15 17 19
接下来的最小数是3,取出,再删掉3的倍数
2 3 | 5 7 11 13 17 19
一直这样下去,直到结束。
筛法求质数的问题时,非质数的数据有很多是重复的。例如,如果有一个数3×7×17×23,那么在删除3的倍数时会删到它,删7、17、23时同样也会删到它。有一种“线性筛法”,可以安排删除的次序,使得每一个非质数都只被删除一次。从而提高效率。因为“筛法”不是我要介绍的重点,所以就不介绍了。
现在我来介绍第二种方法。用这种方法,最先想到的就是让从2~N逐一检查。如果是就显示出来,如果不是,就检查下一个。这是正确的做法,但效率却不高。当然,2是质数,那么2的倍数就不是质数,如果令i从2到N,就很冤枉地测试了4、6、8……这些数?所以第一点改建就是只测试2与所有的奇数就足够了。同理,3是质数,但6、9、12……这些3的倍数却不是,因此,如果能够把2与3的倍数跳过去而不测试,任意连续的6个数中,就只会测试2个而已。以6n,6n+1,6n+2,6n+3,6n+4,6n+5为例,6n,6n+2,6n+4是偶数,又6n+3是3的倍数,所以如果2与3的倍数都不理会,只要测试的数就只留下6n+1和6n+5而已了,因而工作量只是前面想法的2/6=1/3,应该用这个方法编程。
还有个问题,就是如果判断一个数i是否为素数。按素数的定义,也就是只有1与本身可以整除,所以可以用2~i-1去除i,如果都除不尽,i就是素数。观点对,但却与上一点一样的笨拙。当i>2时,有哪一个数可以被i-1除尽的?没有,为什么?如果i不是质数,那么i=a×b,此地a与b既不是i又不是1;正因为a>1,a至少为2,因此b最多也是i/2而已,去除i的数用不着是2~i-1,而用2~i/2就可以了。不但如此,因为i=a×b,a与b不能大于sqrt(i),为什么呢?如果a>sqrt(i),b>sqrt(i),于是a×b>sqrt(i)*sqrt(i)=i,因此就都不能整除i了。如果i不是质数,它的因子最大就是sqrt(i);换言之,用2~sqrt(i)去检验就行了。
但是,用2~sqrt(i)去检验也是浪费。就像前面一样,2除不尽,2的倍数也除不尽;同理,3除不尽,3的倍数也除不尽……最理想的方法就是用质数去除i。
但问题是这些素数从何而来?这比较简单,可以准备一个数组prime[],用来存放找到的素数,一开始它里面有2、3、5。检查的时候,就用prime[]中小于sqrt(i)的数去除i即可,如果都除不尽,i就是素数,把它放如prime[]中,因此prime[]中的素数会越来越多,直到满足个数为止!
不妨用这段说明来编写这个程序,但是程序设计的时候会有两个小问题:
1.如果只检查6n+1和6n+5?不难发现,它们的距离是4、2、4、2……所以,可以先定义一个变量gab=4,然后gab=6-gab;
2.比较是不能用sqrt(i),因为它不精确。举个例子,i=121,在数学上,sqrt(i)自然是11,但计算机里的结果可能是10.9999999,于是去除的数就是2、3、5、7,而不含11,因此121就变成质数了。解决这个问题的方法很简单,不要用开方,用平方即可。例如,如果p*p<=i,则就用p去除i。而且它的效率比开方高。
【程序清单】:
#include <stdio.h>
int creat_prime(int prime[],int n,int total)
{
register int i;
register int j;
register int gab=2;
register int count;
for(i=7;i<=n;i+=gab)
{
count=1;
gab=6-gab;
for(j=0;prime[j]*prime[j]<=i;j++)
{
if(i%prime[j]==0)
{
count=0;
break;
}
}
if(count)
{
prime[total]=i;
total++;
}
}
return total;
}
int main(void)
{
int prime[30000]={2,3,5};
int total=3; //找到素数的个数
int i;
int n=200000; //要查找的范围(>=6)
total=creat_prime(prime,n,total);
for(i=0;i<total;i++)
{
printf("%d ",prime[i]);
if(i && !(i%10))
putchar('\n');
}
putchar('\n');
}
分享到:
相关推荐
使用AKS算法检测素数和生成素数. 提供了AKS的6个步骤的方法 绝对原创
PrimeNumber 素数生成器 V6.0.0.3 18.4KB 可快速生成指定范围内的所有素数,并可格式化输出;还可对单个自然数快速因数分解。 HugeCalc V6.x 以上版本现已提供该程序相应导出接口,欢迎使用。 若借助算法库 ...
而后编制主函数,任意输入一个大于4的偶数d,找出满足d=d1+d2的所有数对,其中要求d1与d2均为素数(通过调用prime来判断素数)。如偶数18可以分解为11+7以及13+5;而偶数80可以分解为:43+37、61+19、67+13、73+7。...
编制具有如下原型的函数prime,用来判断整数n是否为素数:bool prime(int n); 而后编制主函数,任意输入一个大于4的偶数d,找出满足d=d1+d2的所有数对,其中要求d1与d2均为素数(通过调用prime来判断素数)。如偶数...
PrimeNumber 素数生成器 V7.0.0.0 18.7 KB 可快速生成指定范围内的所有素数,并可格式化输出;还可对单个自然数快速因数分解。 HugeCalc V6.x 以上版本现已提供该程序相应导出接口,欢迎使用。 若借助算法库 ...
另外Prime95还是利用分布式计算搜索梅森素数(有译为梅森质数)的GIMPS客户 端程序。GIMPS的全称是 The Great Internet Mersenne Prime Search.翻译过来的意思是互联网梅森素数大搜索。GIMPS成立于1996年1月目的就是...
C语言项目:查找四位可逆素数、可逆质数、可逆prime数 小功能分类(在对应头文件中): 对整数进行逆序输出:四种实现方式---nixu_zong4.h 判断是否为素数、质数、prime数:prime.h
经典算法,求素数(PrimeNumber),使用C#实现
prime函数判定素数.c
使用Miller rabbin方法实现对素数的快速判定 输入为一个整数,若为素数输出Yes,否则输出NO
总理筛 primesieve是一个命令行程序和C / C ++库,用于快速生成素数。 它具有非常高的缓存效率,它可以检测CPU的L1和L2缓存大小并相应地分配其主要数据结构。 默认情况下,它也是多线程的,它尽可能使用所有可用的...
PYTHON 求给定范围内质数和 代码。 def get_primes(n): numbers = set(range(n, 1, -1)) primes = [] while numbers: p = numbers.pop() primes.append(p) numbers.difference_update(set(range(p*2, n+1, p))...
Prime Numbers - The Most Mysterious Figures in Math
素数(prime number)又称质数,有无限个。除了1和它本身外,不能被其他自然数整除。换句话说就是该数除了1和它本身以外不再有其他的因数的数。 注意:最小的素数是2。 话不多说,上代码! prime=[] #用一个列表来存储...
资源名:MATLAB寻找素数的源程序代码_prime_number_素数_素数寻找_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者...
而后编制主函数,任意输入一个大于4的偶数d,找出满足d=d1+d2的所有数对,其中要求d1与d2均为素数(通过调用prime来判断素数)。如偶数18可以分解为11+7以及13+5;而偶数80可以分解为:43+37、61+19、67+13、73+7。...
出2100的所有素数,将求出的素数分别送到文文件 prime.txt和二进制文件prime.dat中。送到文本文件中的结果,要求以表格形式输出,每一行输出5个素数,每一个数占用10个字符宽度。 用文本编辑器产生一个包含若实数的...
primenumber找质数代码
50000000(五千万)以内质数(素数)3001134(约三百万)个,普通pc演算(i7处理器)#质数#素数#合数
效果和Prime95一样,不同的是去掉了Prime95联网计算功能(分布式计算寻找梅森素数) 操作界面比Prime95方便且人性化. 另外如果你的系统里面安装了MBM5这个软件,在测试中直接通过SP2000的调取 就可以随时的知道测试时CPU...