筛法求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( i√ 为什么呢? 我们可以用反证法来验证下: 假设 i不是素数,则必存在有一个数b 使 b*j == i; 如果 b>i√ , j > i√ , 则 b∗j>i 与 b∗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; } } }

这也算用内存换时间的一种