A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

©   /  2013-12-29 14:00  /  2832 人查看  /  5 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

你是想要优化求素数的代码吧??
回复 使用道具 举报
基本上,大多数2,3,5的倍数可以直接过滤,难点在于素数积的那些合数比如判断11413 = 101 * 113
1. 偶数
2 * n: x & 1 == 0
2. 5整除 (尾数0被偶数过滤)
5 * n: x % 10 == 5
3. 3整除
3 * n: x % 3 == 0
以上没有难度容易判断,剩下就是重点部分。
单纯步长加1循环性能会随数字范围增大而严重下降,这里先提一个概念:孪生素数。可以查一下新闻,好像前段时间一个华裔数学家给出了证明:素数往往相伴而生,间隔为2,比如11-13、41-43、101-103……另外有个证明,素数之间的间隔为6,比如11-17、41-47,可以在网上搜到该论文。第三,合数如果有最大质数因子,不会大于其平方根。至此,基于现有的前提条件可以优化循环过程。


------以上资源来源与网络------

评分

参与人数 1技术分 +1 收起 理由
FFF + 1 以上技术分来自网络+1

查看全部评分

回复 使用道具 举报 1 0
您需要登录后才可以回帖 登录 | 加入黑马