我的Java开发学习之旅------>求N内所有的素数
2024-09-07 00:58:03
一、素数的概念
二、算法
算法1.
开根号法:如果一个数(>2),对这个数求平方根,如果这个数能被这个数的平方根到2之间的任何一个(只要有一个就行)整除说明就不是质数,如果不能就说明是质数!
原理:假如一个数N是合数,它有一个约数a,a×b=N,则a、b两个数中必有一个大于或等于根号N,一个小于或等于根号N。因此,只要小于或等于根号N的数(1除外)不能整除N,则N一定是素数。
public void zhishu(int num) {
int i, j, k;
for (i = 2; i < num; i++) {
k = (int) Math.sqrt(i);
for (j = 2; j <= k; j++) {
if(i%j==0){
break;
}
}
if (j>k) {
System.out.println("素数: "+i);
}
}
}
算法2.埃拉托斯特尼素数筛选法
要得到自然数n以内的全部素数,必须把不大于
的所有素数的倍数剔除,剩下的就是素数。
给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去......。
步骤
详细列出算法如下:
- 列出2以后的所有序列:
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 标出序列中的第一个素数,也就是2,序列变成:
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 将剩下序列中,划掉2的倍数,序列变成:
- 2 3 5 7 9 11 13 15 17 19 21 23 25
- 如果现在这个序列中最大数小于最后一个标出的素数的平方,那么剩下的序列中所有的数都是素数,否则回到第二步。
- 本例中,因为25大于2的平方,我们返回第二步:
- 剩下的序列中第一个素数是3,将主序列中3的倍数划掉,主序列变成:
- 2 3 5 7 11 13 17 19 23 25
- 我们得到的素数有:2,3
- 25仍然大于3的平方,所以我们还要返回第二步:
- 现在序列中第一个素数是5,同样将序列中5的倍数划掉,主序列成了:
- 2 3 5 7 11 13 17 19 23
- 我们得到的素数有:2,3,5 。
- 因为23小于5的平方,跳出循环.
结论:2到25之间的素数是:2 3 5 7 11 13 17 19 23。
下面代码摘自网络
public static void getPrimes(int n) {
if (n < 2 || n > 9999999) // 之所以限制最大值为9999999万,是因为JVM内存限制,当然有其他灵活方案可以绕过(比如位图法)
throw new IllegalArgumentException("输入参数n错误!"); int[] array = new int[n]; // 假设初始所有数都是素数,且某个数是素数,则其值为0;比如第一个数为素数那么array[0]为0
array[0] = 1; // 0不是素数
array[1] = 1; // 1不是素数
// 下面是筛选核心过程
for (int i = 2; i < Math.sqrt(n); i++) { // 从最小素数2开始
if (array[i] == 0) {
for (int j = i * i; j < n; j += i) {
array[j] = 1; // 标识该位置为非素数
}
}
} // 打印n以内的所有素数,每排10个输出
System.out.println(n + "以内的素数如下: ");
int count = 0; // 当前已经输出的素数个数
int rowLength = 10; // 每行输出的素数个数
for (int i = 0; i < array.length; i++) {
if (array[i] == 0) {
if (count % rowLength == 0 && count != 0) {
System.out.println();
}
count++; System.out.print(i + "\t");
}
}
}
用以上两个算法求9999999的所有素数
开根号法用时:21507毫秒
埃拉托斯特尼素数筛选法用时: 6658毫秒
关于算法,以下几个用C实现的先mark下来。
==================================================================================================
作者:欧阳鹏 欢迎转载,与人分享是进步的源泉!
转载请保留原文地址:http://blog.csdn.net/ouyang_peng
==================================================================================================
最新文章
- Struts2 internationalization(国际化)
- assign more memory to Gradle
- Hadoop 大数据第一天
- C# WebService输出JSON 实现二
- UVA 572 油田连通块-并查集解决
- GCC的gcc和g++区别
- 下拉列表select显示ng-options
- 【Ural】【1519】Formula 1
- HTML5 动画引擎 小记
- VS2008 未找到编译器可执行文件 csc.exe【当网上其他方法试玩了之后不起作用的时候再用这个方法】
- 跨终端Web之Hybrid App
- powerpc e500系列,linux初始化的tlb汇编,添加人肉代码注释
- iOS- 利用AFNetworking(AFN) - 实现文件断点下载
- windows 创建共享文件夹
- jQuery插件初级练习4
- linux zip命令
- 使用WebViewJavascriptBridge与UIWebView交互
- 微信小程序横版日历,tab栏
- SQLSERVER 子查询中使用ORDER BY
- js的垃圾回收机制
热门文章
- Java 8 Lambda表达式的使用
- iOS申请证书,Certificates, Identifiers &;Profiles 简介 - 申请证书
- Android Gradle 经验总结
- Android内存泄露自动检测神器LeakCanary
- ylb:SQL 存储过程(Procedure)
- 2017.2.20 activiti实战--第二章--搭建Activiti开发环境及简单示例(二)简单示例
- js 数组去重复
- 我是如何通过一个 XSS 探测搜狐内网扫描内网并且蠕动前台到最后被发现的
- INSTALL_FAILED_UID_CHANGED解决的方法
- Failed to fetch URL https://dl-ssl.google.com/android/repository/addons_list-2.xml, reason: Connect