用筛法求之N内的素数。(Java)
2023-03-31 10:40:35 时间
解题思路:
-
申请一个数组,从1-N初始化
-
从第二个数开始,(2是素数),并且用循环把该数的倍数的数置为0
-
然后访问下一个不是1的数(一定为素数),重复上面一个步骤
-
在循环中把不是0的数输出
import java.util.*;
//用筛法求之N内的素数。
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
FindP(N);
}
public static void FindP(int num) {
int[] nums = new int[num];
//将num到1的值赋给数组
for(int i = 1; i < num; i++) {
nums[i] = i + 1;
}
// 从第二个数开始,(2是素数),并且用循环把该数的倍数的数置为0
// 然后访问下一个不是0的数(一定为素数),重复上面一个步骤
for(int i = 1; i < num; i++) {
if(nums[i] != 0) {
System.out.println(nums[i]);//输出这个非0的数(这一定是素数)
//将该素数的倍数赋值为0
for(int j = i+1; j< num; j++) {
if(nums[j]%nums[i] == 0) {
nums[j] = 0;
}
}
}
}
}
}
- 用筛法求素数大体思路:
将某一范围内的正整数从小到大顺序排序,然后在所有数中选取最小的素数,比如为2时,然后去掉2的整数倍的数,取完之后,在选取剩下的最小的素数重复刚刚的步骤。依次类推,直到筛子为空时结束,剩下的这些数就是素数。
相关文章
- Java核心技术卷I基础知识3.10.7 不规则数组
- Java核心技术卷I基础知识导读
- 大数据与机器学习:实践方法与行业案例.3.5 本章小结
- Java集合细节(一):请为集合指定初始容量
- C#与java的异同
- oracle table-lock的5种模式
- 介绍下XRuby项目
- Processing编程学习指南2.8 “运行”按钮
- Erlang入门(二)—并发编程
- Java中4大基本加密算法解析
- 找程序员女神要QQ号码,结果……
- JAVA 异常对于性能的影响
- 程序员是怎样一群人
- 程序员要有持续产出
- 程序员如何更快的适应新工作
- Java查询大文本文件的处理方法
- 各种 Java 的序列化库的性能比较测试结果
- 企业级Java应用最重要的4个性能指标
- 聊一下C#开发者如何过渡到JAVA 开发者
- 让程序员跳槽的非钱原因