开发者社区> 老朱教授> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

筛素数法小结

简介:
+关注继续查看

筛选素数方法小结:

  最简单的筛素数法方法就是从2开始,将所以2的倍数去掉,然后从3开始,将3的倍数去掉,依次进行下去即可。根据这样很容易写出代码,下面代码就是是筛素数法得到100以内的素数并保存到primes[]数组中。

复制代码
复制代码
 1 const int MAXN = 100;
 2 bool flag[MAXN];
 3 int primes[MAXN / 3], pi;
 4 void GetPrime_1()
 5 {
 6     int i, j;
 7     pi = 0;
 8     memset(flag, false, sizeof(flag));
 9     for (i = 2; i < MAXN; i++)
10         if (!flag[i])
11         {
12             primes[pi++] = i;
13             for (j = i; j < MAXN; j += i)  //剔除待考察数据j的倍数,并置其flag位为true
14                 flag[j] = true;
15         }
16 }
复制代码
复制代码

  可以看出这种会有很多重复访问,如在访问flag[2]和flag[5]时会各访问flag[10]一次。因此最好想方法来减少这种重复访问,让flag[]数组的每个元素只被访问一次。可以这样考虑——简单的筛素数法是利用一个素数的倍数必须不是素数,同样任何一个数与其它所有素数的乘积必然也不是素数(这是因为每个合数必有一个最小素因子)。

      为了试验这种想法,先用2到10之间的数来验证下。

      2,3,4,5,6,7,8,9,10      初始时所以flag都是无标记的。

  第一步 访问2,flag[2]无标记所以将2加入素数表中,然后将2与素数表中的所有数相乘得到的数必定不是素数,2*2=4因此标记flag[4]。

   2,3,4,5,6,7,8,9,10

  第二步 访问3,flag[3]无标记所以将3加入素数表中,将3与素数表中的所有数相乘得到的数必定不是素数,3*2=6,3*3=9因此标记flag[6]和flag[9]。

   2,3,4,5,6,7,8,9,10

  第三步 访问4,flag[4]有标记所以4不加入素数表中,将4与素数表中的所有数相乘得到的数必定不是素数, 4*2=8,4*3=12因此标记flag[8]。

   2,3,4,5,6,7,8,9,10

  第四步 访问5,flag[5]无标记所以将5加入素数表中,将5与素数表中的所有数相乘得到的数必定不是素数,5*2=10,5*3=15因此标记flag[10]。

   2,3,4,5,6,7,8,9,10

  第五步 访问6,flag[6]有标记所以6不加入素数表中,将6与素数表中的所有数相乘得到的数必定不是素数, 6*2=12,6*3=18,6*5=30。

   2,3,4,5,6,7,8,9,10

    后面几步类似,具体代码如下:

复制代码
复制代码
 1 const int MAXN = 100;
 2 bool flag[MAXN];
 3 int primes[MAXN / 3], pi;
 4 void GetPrime_2()
 5 {
 6     int i, j;
 7     pi = 0;
 8     memset(flag, false, sizeof(flag));
 9     for (i = 2; i < MAXN; i++)
10     {
11         if (!flag[i])
12             primes[pi++] = i;  //flag未标记为true,将其加入到素数表中
13         for (j = 0; (j < pi)  && (i * primes[j] < MAXN); j++)  //依次剔除待考察数据与素数表中数据的乘积,并置其flag位为true
14             flag[i * primes[j]] = true;
15     }
16 }
复制代码
复制代码

  这份代码对不对呢?仔细回顾下分析过程,可以发现有些数据还是被访问了多次,这当然不是我们希望的结果,我们的要求是让每个合数仅被它的最小素因子筛去一次。比如12,它的最小素因子是2,所以就只应该被在计算6*2时去访问,而且不应该在计算4*3时去访问,同理18也只应该被在计算9*2时去访问,而且不应该在计算6*3时去访问。

    找到原因后,再来思考如何解决。6*3不行而9*2可以了,是因为6是2的倍数,所以在计算6*2之后就不能再将6与比2大的素数相乘,这些相乘的结果必定会导致重复计算。因此对于任何数来说,如果它是该素数的倍数那么它就不能再与素数表中该素数之后的素数相乘了,如9是3的倍数,所以在9*3之后就不能再去用计算9*5了。因此在代码中再增加一行判断语句:

复制代码
复制代码
 1 const int MAXN = 100;
 2 bool flag[MAXN];
 3 int primes[MAXN / 3], pi;
 4 void GetPrime_2()
 5 {
 6     int i, j;
 7     pi = 0;
 8     memset(flag, false, sizeof(flag));
 9     for (i = 2; i < MAXN; i++)
10     {
11         if (!flag[i])
12             primes[pi++] = i;
13         for (j = 0; (j < pi)  && (i * primes[j] < MAXN); j++)
14         {
15             flag[i * primes[j]] = true;
16             if (i % primes[j] == 0) //这句保证每个非素数只被筛去一次
17                 break;
18 }
19     }
20 }
复制代码
复制代码

  想知道这二种筛素数法方法的区别吗?现在对求2到1亿之间的素数进行测试,看看区别到底会有多大,测试代码如下:

复制代码
复制代码
 1 /*
 2 *描述:筛素数法(倍数剔除、最小素因子筛选)对比
 3 *分析:倍数剔除:一个素数的倍数必须不是素数,即从2开始,将所以2的倍数去掉,然后从3开始,将3的倍数去掉,依次进行下去即可
 4 *       最小素因子筛选:简单的筛素数法(倍数剔除)是利用一个素数的倍数必须不是素数,同样任何一个数与其它所有素数的乘积必然也不是素数(这是因为每个合数必有一个最小素因子)。
 5                        要求是让每个合数仅被它的最小素因子筛去一次;即如果它是该素数的倍数那么它就不能再与素数表中该素数之后的素数相乘了。
 6 *
 7 *
 8 */
 9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <memory.h>
12 #include <time.h>
13 #include <math.h>
14 const int MAXN = 100000000;
15 bool flag[MAXN];
16 int primes[MAXN / 3], pi;
17 // 利用对每个素数的倍数必定不是素数来筛选
18 void GetPrime_1()
19 {
20     int i, j;
21     pi = 0;
22     memset(flag, false, sizeof(flag));
23     for (i = 2; i < MAXN; i++)
24         if (!flag[i])
25         {
26             primes[pi++] = i;
27             for (j = i; j < MAXN; j += i)
28                 flag[j] = true;
29         }
30 }
31 // 利用了每个合数必有一个最小素因子来筛选
32 void GetPrime_2()
33 {
34     int i, j;
35     pi = 0;
36     memset(flag, false, sizeof(flag));
37     for (i = 2; i < MAXN; i++)
38     {
39         if (!flag[i])
40             primes[pi++] = i;
41         for (j = 0; (j < pi)  && (i * primes[j] < MAXN); j++)
42         {
43             flag[i * primes[j]] = true;
44             if (i % primes[j] == 0)
45                 break;
46         }
47     }
48 }
49 int main()
50 {
51     printf(" 在%d的数据量下普通的筛素数方法与改进之后的效率对比\n", MAXN);
52     clock_t clockBegin, clockEnd;
53     
54     clockBegin = clock();
55     GetPrime_1();
56     clockEnd = clock();
57     printf("普通的筛素数方法\t%d毫秒\n", clockEnd - clockBegin);
58     
59     clockBegin = clock();
60     GetPrime_2();
61     clockEnd = clock();
62     printf("改进的筛素数方法\t%d毫秒\n", clockEnd - clockBegin);
63     system("pause");
64     return 0;
65 }


本文转自我爱物联网博客园博客,原文链接:http://www.cnblogs.com/yydcdut/p/3876195.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
密码学系列之:在线证书状态协议OCSP详解
我们在进行网页访问的时候会跟各种各样的证书打交道,比如在访问https网页的时候,需要检测https网站的证书有效性。 OCSP就是一种校验协议,用于获取X.509数字证书的撤销状态。它是为了替换CRL而出现的。 本文将会详细介绍OCSP的实现和优点。
0 0
试用阿里云搭建MySQL心得
本人因初学MySQL,要运用阿里云服务器建库来增进学习深度。在大学期间学习JAVA时,也发现随着学习的深入,要使用的编程技术愈来愈多,而使用阿里云无疑是为了高级编程垫好平台。在熟悉sql语句和JDBC、JavaWeb以及Mybatis过程中,云服务给我提供了莫大的帮助!
0 0
【Java】SpringBoot 引入fastjson库进行json格式数据返回实例
fastjson fastjson是阿里巴巴开源的json操作库,功能强大,使用方便。 https://github.com/alibaba/fastjson 放入pom.
1202 0
5个人如何1年交付了120+项目?分享我在阿里云做交付的工作手记
谨以此文,分享一些我加入阿里云后,我和我所在团队的成长经历。这里既有我个人如何从程序员成长为一个技术经理,也有我的团队如何把事情越做越大的过程和思考,希望能够帮到有需要的人。
0 0
一文梳理Code Review方法论与实践总结
作为卓越工程文化的一部分,Code Review其实一直在进行中,只是各团队根据自身情况张驰有度,松紧可能也不一,这里简单梳理一下CR的方法和团队实践。
0 0
我理解的测试开发与实践总结——新人篇
写这篇文章的目的是为了能够更好的帮助刚入职的新人了解这个岗位和自己的工作,也想谈谈自己工作一年来对这个领域的了解程度,做一个小小总结吧~
0 0
轻松使用阿里达摩院开源在魔搭社区上的CLUE语义匹配模型
本文将介绍达摩院NLP团队在魔搭社区(ModelScope)上开源的语义匹配模型及其使用方法。
0 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载