求任意自然数内的素数
作者:mike 来源:163UED 时间:2009-10-15 12:21:00
用6N±1法求素数
任何一个自然数,总可以表示成为如下的形式之一:
6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)
显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数)。
根据上述分析,我们可以构造另一面筛子,只对形如6 N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。
以下代码需要自然数大于10
function fn(num){
var arr = [];
arr.push(2);
arr.push(3);
arr.push(5);
arr.push(7);
var t = 0;
for (var i = 3; t < num; i = i + 3) {
for (var j = 0; j < 2; j++) {
t = 2 * (i + j) - 1;
if (t < num && (t % 5 == 0 ? false : t % 7 == 0 ? false : true)) {
arr.push(t);
}
}
}
return arr.join(” “);
}
document.write(fn(1000));
各位大侠有没有更高效的方法或以上代码有不对的地方,请指出。
标签:素数,自然数,算法
0
投稿
猜你喜欢
解析array splice的移除数组中指定键的值,返回一个新的数组
2023-11-18 09:51:28
Python彻底删除文件夹及其子文件方式
2022-07-27 04:18:53
mysql 8.0.15 winx64解压版图文安装教程
2024-01-16 08:22:32
Python判断一个文件夹内哪些文件是图片的实例
2023-08-18 01:22:44
15个网页排版例子赏析
2008-01-06 16:38:00
Oracle数据库的备份及恢复策略研究
2010-07-16 12:54:00
详解golang中的闭包与defer
2024-04-26 17:32:58
JavaScript判断对象是否为数组
2024-04-22 22:42:14
Asp 编码互转的研究和实现代码
2011-03-30 10:44:00
JavaScript设计模式之模板方法模式原理与用法示例
2024-02-24 02:17:20
用SQL语句解决mysql导入大数据文件的问题
2024-01-13 05:52:23
python实现用户答题功能
2022-01-05 21:38:02
对TensorFlow中的variables_to_restore函数详解
2022-09-11 00:49:19
Mysql DDL常见操作汇总
2024-01-22 05:30:09
详解MySQL数据类型int(M)中M的含义
2024-01-14 03:07:05
浅谈Python在pycharm中的调试(debug)
2023-05-04 15:33:20
Oracle数据库TNS常见错误的解决方法汇总
2024-01-21 04:45:34
Python 分析Nginx访问日志并保存到MySQL数据库实例
2024-01-22 08:43:23
python 的列表遍历删除实现代码
2023-07-15 11:44:35
详解Java使用sqlite 数据库如何生成db文件
2024-01-17 17:07:47