package com.aekc.algorithm;
import java.util.Scanner;
/**
* 求n以内的所有素数
*/
public class PrimeNumber {
/**
* 穷举法，检测所有可能的因子。
* 时间复杂度为：O(n^2)
*/
public void primeNumber1(int n) {
int number = 2;
int count = 0;
while(number <= n) {
boolean isPrime = true;
for(int divisor = 2; divisor <= number / 2; divisor++) {
if(number % divisor == 0) {
isPrime = false;
break;
}
}
if(isPrime) {
count++;
}
number++;
}
System.out.println("\ncount: " + count);
}
/**
* 检测直到√n的因子
* 时间复杂度为：O(n√n)
*/
public void primeNumber2(int n) {
int number = 2;
int count = 0;
while(number <= n) {
boolean isPrime = true;
int squareRoot = (int) Math.sqrt(number);
for(int divisor = 2; divisor <= squareRoot; divisor++) {
if(number % divisor == 0) {
isPrime = false;
break;
}
}
if(isPrime) {
count++;
}
number++;
}
System.out.println("\ncount: " + count);
}
/**
* 检测直到√n的素数因子
* 简易证明：如果i不是素数，那就必须存在一个素数p，满足i=pq且p<=q。
* k也是i的最小因子，这和p是i的最小因子是冲突的。因此，如果i不是素数，
* 那么可以找出2到√i之间的被i整除的素数。
* 时间复杂度为：O(n√n / logn)
*/
public void primeNumber3(int n) {
int number = 2;
int count = 0;
int squareRoot = 1;
int[] primes = new int[n];
while(number <= n) {
boolean isPrime = true;
if(squareRoot * squareRoot < number) {
squareRoot++;
}
for(int k = 0; k < count && primes[k] <= squareRoot; k++) {
if(number % primes[k] == 0) {
isPrime = false;
break;
}
}
if(isPrime) {
primes[count] = number;
count++;
}
number++;
}
System.out.println("\ncount: " + count);
}
/**
* 埃拉托色尼筛选算法
* 利用当前已经找到的素数，从后面的数中筛去当前素数的倍数
* 但是某些数被每个质因子都筛了一遍导致速度减慢，空间开销大
* 时间复杂度为：O(n√n / logn) 接近于 O(n)
*/
public void primeNumber4(int n) {
boolean[] primes = new boolean[n + 1];
for(int i = 0; i < primes.length; i++) {
primes[i] = true;
}
for(int k = 2; k <= n / k; k++) {
if(primes[k]) {
for(int i = k; i <= n / k; i++) {
primes[k * i] = false;
}
}
}
int count = 0;
for(int i = 2; i < primes.length; i++) {
if(primes[i]) {
count++;
}
}
System.out.println("\ncount: " + count);
}
/**
* 欧拉筛选法
* 在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的
* 时间复杂度为：O(n)
*/
public void primeNumber5(int n) {
// 用来存放质数
int[] set = new int[n + 1];
// 用来标记合数
boolean[] bol = new boolean[n + 1];
int count = 0;
for (int i = 2; i < n; i++) {
// 如果 i 是素数 存放在 set 里
if (!bol[i]){
// count 统计的目前 质数的个数 正好可以用这个 count 将 质数顺序的存放在 set 集合中
set[count] = i;
count++;
}
/*
根据 合数的定义(一个合数肯定是若干素数的乘积) 所以素数的倍数一定是合数
所以 用 这个素数, 乘以现在已知的其他素数, 那么得到的会是一个个合数 在 bol 中标记
*/
for (int j = 0; j < count; j++) {
// 排除掉 超过 n 的合数
if (i * set[j] > n) break;
// 为合数在 bol 中做标记
bol[i*set[j]] = true;
if (i%set[j] == 0 ) break;
}
}
for (int i : set) {
System.out.println(i);
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Find all prime numbers <= n，enter n：");
int n = input.nextInt();
long start = 0;
long end = 0;
start = System.currentTimeMillis();
new PrimeNumber().primeNumber1(n);
end = System.currentTimeMillis();
System.out.printf("primeNumber1 所用时间为(单位毫秒)：%d\n", end - start);
start = System.currentTimeMillis();
new PrimeNumber().primeNumber2(n);
end = System.currentTimeMillis();
System.out.printf("primeNumber2 所用时间为(单位毫秒)：%d\n", end - start);
start = System.currentTimeMillis();
new PrimeNumber().primeNumber3(n);
end = System.currentTimeMillis();
System.out.printf("primeNumber3 所用时间为(单位毫秒)：%d\n", end - start);
start = System.currentTimeMillis();
new PrimeNumber().primeNumber4(n);
end = System.currentTimeMillis();
System.out.printf("primeNumber4 所用时间为(单位毫秒)：%d\n", end - start);
start = System.currentTimeMillis();
new PrimeNumber().primeNumber5(n);
end = System.currentTimeMillis();
System.out.printf("primeNumber5 所用时间为(单位毫秒)：%d\n", end - start);
}
}
原文：https://blog.csdn.net/XlxfyzsFdblj/article/details/81149668
n = 2000000
Find all prime numbers <= n，enter n：
2000000
count: 148933
primeNumber1 所用时间为(单位毫秒)：294368
count: 148933
primeNumber2 所用时间为(单位毫秒)：855
count: 148933
primeNumber3 所用时间为(单位毫秒)：165
count: 148933
primeNumber4 所用时间为(单位毫秒)：71
count: 148933
primeNumber5 所用时间为(单位毫秒)：31
网友评论