求N范围内的所有素数
发布时间
阅读量：
阅读量
筛法求N范围内的所有素数
问题引入
给定一个正整数N,求N范围内的所有素数
解法一 枚举
思路就是从2开始,枚举所有小于N的数,判断是否是素数
for(int i = 2; i < N ; i++){
if(isPrime(i)){
System.out.print(i+" ");
}
}注意isPrime(i)的设计很重要
一般我们容易想到的是:
for(int j = 2; j<i ; j ++){
if(i % j == 0){
reutrn false;
}
}
return true;那么其实我们无需枚举过多的j值, 最大值仅为Math.ceil(\sqrt{i})。那么我们可以运用反证法进行验证：假设i不是素数,则必定存在一个整数b使得b乘以j等于i。若b和j均大于\sqrt{i}时，则有b \times j > i，这与b \times j = i矛盾。
所以正确的代码应该是
int l = (int)Math.ceil(Math.sqrt(i));
for(int j = 2; j < l ; j++){
if(i % j == 0){
reutrn false;
}
}
return true;解法二 筛法
其实其原理非常基础，在算法运行之前我们假设所有小于给定参数N的整数值均为素数值随后通过一系列筛选步骤逐步排除非素数值的过程最终能够准确地确定所有满足条件的真实素数值. 具体来说我们可以创建一个长度为N+1的boolean数组isNotPrime并将其中每个元素初始化为false. 然后从数字2开始遍历每一个位置并将其所有倍数值设为true因为这些倍数值必定是非素数值. 经过上述筛选过程后在数组中仍标记为false的位置即为我们筛选出的所有素数值.
boolean isNotPrime[] = new boolean[N+1];
for(int i = 2;i < N+1 ; i++){
if(!isNotPrime[i]){
System.out.print(i+" ");
for(int j = i*i,j < N+1 ; j += i){
isNotPrime[j] = true;
}
}
}这也算用内存换时间的一种
全部评论 (0)
还没有任何评论哟~