图文解析求质数，三种优化方法_求质数的最优算法

质数(素数)定义： 只能被1和本身整除的数（2是最小的质数）

题目要求：求出100000以内的质数个数

方法一： 简单粗暴的嵌套循环

	boolean flag = true; //用于判断是否为质数
    int count = 0;       //记录质数个数

    long startTime = System.currentTimeMillis(); //开始时间
    
    for (int n = 2; n <= 100000; n++) {
		//判断当前n是否为质数，
        for (int i = 2; i < n; i++) {
            if (n % i == 0){
                //能被整除，当前n不是质数，flag设为false
                flag = false;
            }
        }
        //通过flag判断当前n是否为质数，是则数量加1
        if (flag){
            count++;
        }
        //重置flag状态
        flag = true;
    }
    long endTime = System.currentTimeMillis(); //结束时间
    System.out.println(count); //质数数量
    System.out.println(endTime-startTime); //时间差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

质数数量count：9592
开始到结束的时间差：16990ms (时间差不同的电脑各不相同)

方法二： 优化方式一，去除偶数，break结束循环

因为偶数一定能被2整除，所以偶数一定不是质数。

	boolean flag = true; //用于判断是否为质数
    int count = 0;       //记录质数个数

    long startTime = System.currentTimeMillis(); //开始时间
    
    for (int n = 2; n <= 100000; n++) {
    	if (i != 2 && i % 2 == 0){
        	//n为偶数，跳过本次循环的后续操作，进行下次循环
            continue;
        }
		//判断当前n是否为质数，
        for (int i = 2; i < n; i++) {
            if (n % i == 0){
                //能被整除，当前n不是质数，flag设为false
                flag = false;
                //已经确定n不是质数，结束当前循环
                break;
            }
        }
        //通过flag判断当前n是否为质数，是则数量加1
        if (flag){
            count++;
        }
        //重置flag状态
        flag = true;
    }
    long endTime = System.currentTimeMillis(); //结束时间
    System.out.println(count); //质数数量
    System.out.println(endTime-startTime); //时间差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

质数数量count：9592
开始到结束的时间差：1545ms

通过去除偶数，添加break，方法二比方法一耗时少了10倍

方式三： 将判断次数减半（大约）

当i = n/2时，n/i == 2，此时如果再进行循环判断，i的值不断变大，即i > n/2时，1< n/i < 2即n/i不可能为整数，此时继续循环判断已经没有意义了，所以循环判断只需要进行到n/2+1就行

	boolean flag = true; //用于判断是否为质数
    int count = 0;       //记录质数个数

    long startTime = System.currentTimeMillis(); //开始时间
    
    for (int n = 2; n <= 100000; n++) {
    	if (i != 2 && i % 2 == 0){
        	//n为偶数，跳过本次循环的后续操作，进行下次循环
            continue;
        }
		//判断当前n是否为质数，只需要判断到n/2即可
        for (int i = 2; i < n/2+1; i++) {
            if (n % i == 0){
                //能被整除，当前n不是质数，flag设为false
                flag = false;
                //已经确定n不是质数，结束当前循环
                break;
            }
        }
        //通过flag判断当前n是否为质数，是则数量加1
        if (flag){
            count++;
        }
        //重置flag状态
        flag = true;
    }
    long endTime = System.currentTimeMillis(); //结束时间
    System.out.println(count); //质数数量
    System.out.println(endTime-startTime); //时间差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

质数数量count：9592
开始到结束的时间差：803ms 时间再次少一半

方法四： 继续优化方式三

根据上图分析，判断n是否为质数，只需要判断 2<= i <= Math.sqrt(i)区间即可

	boolean flag = true; //用于判断是否为质数
    int count = 0;       //记录质数个数

    long startTime = System.currentTimeMillis(); //开始时间
    
    for (int n = 2; n <= 100000; n++) {
    	if (i != 2 && i % 2 == 0){
        	//n为偶数，跳过本次循环的后续操作，进行下次循环
            continue;
        }
		//判断当前n是否为质数，只需要判断到Math.sqrt(n)即可
		//注意是 i <= Math.sqrt(n); 要有= 否则可能少数量
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0){
                //能被整除，当前n不是质数，flag设为false
                flag = false;
                //已经确定n不是质数，结束当前循环
                break;
            }
        }
        //通过flag判断当前n是否为质数，是则数量加1
        if (flag){
            count++;
        }
        //重置flag状态
        flag = true;
    }
    long endTime = System.currentTimeMillis(); //结束时间
    System.out.println(count); //质数数量
    System.out.println(endTime-startTime); //时间差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

质数数量count：9592
开始到结束的时间差：13ms 时间已经只要消耗13毫秒了