列出小于1000的素数,对于这样的算法好多人都会,但对于编程人员,要对这样的算法做优化,会有不同的算法了,以下为我自己的两种算法做比较:
算法一,大众算法。用两个循环法。
public class Test {
public static void main(String[] args) {
long start = System.currentTimeMillis();
for (int i = 2; i < 100000; i++) {
if(prime(i))
System.out.println(i);
}
System.out.println("take times : " + (System.currentTimeMillis() - start));
}
private static boolean prime(int n){
for (int i = 2; i < n; i++) {
if(n % i == 0)
return false;
}
return true;
}
}
算法二,优化后的算法
public class Test2 {
public static void main(String[] args) {
long start = System.currentTimeMillis();
for (int i = 2; i < 100000; i++) {
if(prime(i))
System.out.println(i);
}
System.out.println("take times : " + (System.currentTimeMillis() - start));
}
private static boolean prime(int n){
if(n % 2 == 0)
return n == 2;
for (int i = 3; i*i <= n; i = i + 2) {
if(n % i == 0)
return false;
}
return true;
}
}
以上两个算法比较(数据量越大结果对比越明显):
elipse下运行计算 |
算法一耗时(ms) |
算法二耗时(ms) |
小于1000 |
7 |
5 |
小于100000 |
4590 |
237 |
分享到:
相关推荐
Python 计算从1-N(N可以任何数)内的素数(并行计算、多线程优化计算)
并行计算求素数个数包括java、OpenMP、MPI、.NET、MFC、Windows Api等方法 并行计算求素数个数包括java、OpenMP、MPI、.NET、MFC、Windows Api等方法
暴力法 | 暴力法优化(取中间数)|暴力法优化(取平方根)|埃氏筛法|未知算法。五种算法的效率依次递增。在同一个Prime.java文件中都可以测试。
计算10^18素数筛法, 目前这个是国内最快的筛法程序(如果你有比我还快的, 个人给你500元奖励 * 快的倍数),比国外primesieve略慢20%, , 使用非常方便, 输入两个数得到素数个数, 共计3000行C++代码。采用10多...
判断是否为质数,最优化的运行效率,减少性能损耗。测试计算机的运算速度。java学习的入门基础,最优化计算时间
数学建模学习资料 数学建模大赛赛题、解决方案资料,供备赛者学习参考!数学建模大赛赛题、解决方案资料,供备赛者学习参考!数学建模大赛赛题、解决方案资料,供备赛者学习参考!数学建模大赛赛题、解决方案资料...
matlab算法,适合毕业设计、课程设计作业,所有源码均经过严格测试,可以直接运行,可以放心下载使用。
判断一个数字是素数还是合数的算法——aks算法,具有较强的优化性和较低的计算复杂度。方便、快捷、准确。
miller-rabin算法是目前主流的基于概率的素数测试算法,在构建密码安全体系中占据重要的位置。南开大学机器人与信息自动化研究所,通过比较...通过对miller-rabin算法底层运算的优化,可以取得较以往实现更好的性能。
但是为了计算的有效性,检查了随机银间隔中素数的分布,根据天主教信息证明,相同随机银间隔中素数的密度在统计上是恒定的。 下面,在引言中,我们将定义“信息论” [1]的“天主教信息”概念,并定义为仅使用集
树的优化算法 拓扑排序(邻接阵形式) 最佳边割集 最佳顶点割集 最小边割集 最小顶点割集 最小路径覆盖 图论_最短路径\ 最短路径(单源bellman_ford邻接阵形式) 最短路径(单源dijkstra邻接阵形式) 最短路径...
树的优化算法 拓扑排序(邻接阵形式) 最佳边割集 最佳顶点割集 最小边割集 最小顶点割集 最小路径覆盖 图论_最短路径\ 最短路径(单源bellman_ford邻接阵形式) 最短路径(单源dijkstra邻接阵形式) 最短路径...
③ 在关键算法上做进一步优化,例如在寻找素数时,素数测试使用更快速的算法;还有3.3节提到的,在用私有密钥进行幂模运算时使用中国余数定理等。 ④ 对C++核心类库进行重点优化,使其运算效率尽可能提高。其中包括...
9.6.7 编译时计算的游戏 283 9.7 小结 286 第10章 调试 287 10.1 assert及程序错误的提前发现 288 10.1.1 崩溃的程序不说谎 289 10.1.2 为软件维护多个版本 291 10.1.3 前置条件和后置条件 292 10.1.4 自己实现一个...
ampclib是一个易于使用的,独立于平台的C ++库,可用于带... ampclib由三类组成:+整数(多精度整数)+理性(使用Integer类的多精度有理数)+素数(素数计算和无符号32位整数的数论函数)最新版本包含优化和错误修复。
秒来计算素数。 最后,GraalVM Ruby在我的笔记本电脑上需要不到150 毫秒。 JavaScript 当然,如今最优化的动态语言运行时是针对 JavaScript 的,所以我们不应该重写我们的代码以使其更快吗? 是的,我们可以试试: $...
然后对关键模块流程图、详细的接口文档进行阐述,并给出关键的实现代码,最后对应用程序进行测试,对测试结果进行分析研究,进而对应用程序进行改进,对关键算法进行尽可能的优化,最终得到一个在windows运行的可以...
unix下通过创建多线程计算质数的优化算法
leetcode 融资完成编码面试 ...非常适合密码学,因为素数允许计算唯一的哈希 对于那些考虑人工智能的人来说很有趣 最适合那些对 Hacking 感兴趣的人,对解析器进行段错误通常是利用程序的最佳方式 排序数组中
部: 生成大量 1024 位和 2048 位。...在开始计算算法之前,通过丢弃 [3, 5, 7, 9, 11, 13, 15, 19] 的倍数来优化 Rabin-Miller 算法。(提高性能) 并行化 Rabin-Miller 迭代以提高密钥生成性能。