一千万以内共有多少质数
计算1000w以内有多少个质数。
解法
重点就是如何判断一个数是不是质数。
1. 2 到\(\sqrt n\)之间的所有整数去除
如果用 2 到\(\sqrt n\)之间的所有整数去除，均无法整除，则 n 为质数。时间复杂度为 \(O(n^2)\)
public class FindPrimeNumber {
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(findPrimeNumber());
System.out.println("耗时: " + (System.currentTimeMillis() - start));
}
public static int findPrimeNumber() {
int count = 2;
for (int i = 4; i < 10000000; i++) {
if (checkPrimeNumber(i)) {
count++;
}
}
return count;
}
public static boolean checkPrimeNumber(int num) {
// 只与不大于 sqrt(n) 的数相除即可
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}
2. 只整除质数
如果用 2 到\(\sqrt n\)之间的所有整数去除，判断次数有点太多了。一个合数可以分解成多个质数的乘积，所以只要除以比自己小的的质数看看能不能整除即可。
public class FindPrimeNumber {
// 维护已找到的质数
static List<Integer> primeNums = new ArrayList<>();
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(findPrimeNumber());
System.out.println("耗时: " + (System.currentTimeMillis() - start));
}
public static int findPrimeNumber() {
primeNums.add(2);
primeNums.add(3);
int count = 2;
for (int i = 4; i <= 10000000; i++) {
if (checkPrimeNumber(i)) {
primeNums.add(i);
count++;
}
}
return count;
}
public static boolean checkPrimeNumber(int num) {
// 只与不大于 sqrt(n) 的质数相除即可
for (int i = 0; i < primeNums.size() && primeNums.get(i) <= Math.sqrt(num); i++) {
if (num % primeNums.get(i) == 0) {
return false;
}
}
return true;
}
}
运行结果：
一千万以内的质数一共有 664579个
耗时: 946
3. 埃式筛选
埃拉托斯特尼筛法：简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
public class FindPrimeNumber {
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println("一千万以内的质数一共有 " + findPrimeNumber() + "个");
System.out.println("耗时: " + (System.currentTimeMillis() - start));
}
public static int findPrimeNumber() {
boolean[] isPrime = new boolean[10000001];
Arrays.fill(isPrime, true);
// 只需考虑根号 n 以内的数的倍数
for (int i = 2; i <= Math.sqrt(isPrime.length); i++) {
if (isPrime[i]) {
// 剔除 i 的倍数
for (int j = i * i; j < isPrime.length; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i < isPrime.length; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
}
运行结果：
一千万以内的质数一共有 664579个
耗时: 140
可以看到这种解法速度快了很多。
再优化一下：
计算 i 的倍数的过程中需要计算 \(i * 2, i * 3, i * 4, i * 5 ...\)，每一个元素都要计算它的偶数倍，包含很多重复计算。由于大于 2 的偶数一定不是质数，所以可以先把所有大于 2 的偶数剔除掉，只计算每个元素的奇数倍即可。这样可以减少一部分计算时间，但不会很多。
public class FindPrimeNumber {
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println("一千万以内的质数一共有 " + findPrimeNumber() + "个");
System.out.println("耗时: " + (System.currentTimeMillis() - start));
}
public static int findPrimeNumber() {
boolean[] isPrime = new boolean[10000000 + 1];
Arrays.fill(isPrime, true);
// 先将偶数剔除
for (int i = 3; i <= isPrime.length; i++) {
if (i % 2 == 0) {
isPrime[i] = false;
}
}
// 只需考虑根号n以内的数的倍数
for (int i = 2; i <= Math.sqrt(isPrime.length); i++) {
if (isPrime[i]) {
// 只计算奇数倍
for (int j = i * i; j < isPrime.length; j += 2 * i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i < isPrime.length; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
}