质数概念: 只能被1和自己整除的数
**
初步思路
**：运用双层循环，判断是否为质数，true则num+1；false跳过
代码如下：
package somethings;
import java.util.Locale;
/**
* @author Small_Tsky
* @date 2020/2/23 - 16:21
**/
public class Unimportance {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int n = 10000000;
// 初始化num (因为1和2都为质数未被计入for循环里）
int num = 2;
for (int i = 3; i <= n; i++) {
for (int j = 2; j <i ; j++) {
// i除1和本身没有其他的因子，即为质数
if (i % j != 0) {
num++;
}
}
}
System.out.println("一千万以内的质数个数为："+num);
long end = System.currentTimeMillis();
System.out.println("所用时间："+(edn - start)+"毫秒");
}
}
运行结果： 无
数据过于庞大，运算次数要循环**1+2+…+（10000000-2）**次。
-----------------------------------------------------------------------
下面就要优化优化思路，不能蛮干了：
优化思路：
对与确定的质数先做标记，标记完成后，遍历标记的质数，num++；
代码如下：
import java.util.Arrays;
/**
* @author Small_Tsky
* @date 2020/2/23 - 16:25
**/
public class Isprimes {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int n = 10000000;
int num = 0;
boolean [] isprimes = new boolean[n];
// 定义isprimes[]
Arrays.fill(isprimes,true);
for (int i = 2; i <= isprimes.length; i++) {
for (int j = 2; i * j < isprimes.length; j++) {
// 标记不符合条件的num，即有因子的全部标记false；
isprimes[i * j] = false;
}
}
isprimes[0]=false;
// 遍历isprimes[]
for (int i = 0; i <isprimes.length ; i++) {
if (isprimes[i]){
num++;
}
}
long end = System.currentTimeMillis();
System.out.println("一千万以内的质数一共有 " + num + " 个");
System.out.println("所用时间为 " + (int) (end - start)+"毫秒");
}
}
运行结果：
一千万以内的质数一共有 664580 个
所用时间为 2132毫秒
Process finished with exit code 0
-----------------------------------------------------------------------
前辈思路（埃氏筛法）：
代码如下：
package arrylist;
import property.Item;
import java.util.Arrays;
/**
* @author Small_Tsky
* @date 2020/2/23 - 16:30
**/
public class list {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int n = 10000000;
boolean[] data = new boolean[n];
Arrays.fill(data, true);
for (int i = 1; i <= data.length; i++) {
if(i%2==0) {
data[i-1] = false;
}
}
data[1] = true;
//先把除了2之外的偶数全部确定为合数
int num = 0;
data[0] = false;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (data[i - 1]) {
// 这里的步长改为2*i，跳过偶数部分
for (int j = i * i; j <= n; j += 2 * i) {
data[j - 1] = false;
}
}
}
for (int i = 0; i < data.length; i++) {
if (data[i]) {
num++;
}
}
long end = System.currentTimeMillis();
System.out.println("一千万以内的质数一共有 " + num + " 个");
System.out.println("所用时间为 " + (int) (end - start)+"毫秒");
}
}
运行结果：
一千万以内的质数一共有 664579 个
所用时间为 186毫秒