一篇搞懂素数求法

前言

这篇文章是写常考的算法之一——求解素数

这种题在之前的时候，会说的特别明显，而在近几届比赛中（貌似换了出题组），题目变得会绕个弯的问你，但是大家丝毫不用慌，题目在变，内容不变，所有的算法均有解答的框架，不信你看我之前的文章：

所有的算法均有固定的东西，只要掌握了框架，万变不离其宗，废话不多说，直接开整

什么是素数

这是百度百科的结果，搜索出来的直接就是质数，意思就是除了1和它本身，没有其他的数能整除它，其实素数也就是质数

那么该如何求解呢？

素数简单求解

这个相信大家都见过，所以直接上代码了

// 判断整数 n 是否是素数
boolean isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            // 有其他整除因子
            return false;
    return true;
}

这个求法特别简单，显而易见，但是费时费力，而且如果遇到很大的数，直接就崩了，于时，这个方法蓝桥杯显然不会常用

素数进阶求解

首先上面这种求素数的方法是绝对不高效的，如果是遇到让你求多少位上的素数且这个位很大的情况下，求解的速度很慢
这个时候就需要用到一些小技巧
也就是说，我们并不需要i 遍历到n,只需要到sqrt(n),举个例子
12=2*6
12=3*4
12=sqrt(n)*sqrt(n)//分界
12=4*3
12=6*2
就是说分界上下的一样，只不过顺序反了，所以只需要i<+sqrt(n)即可

//判断是否是素数
public static boolean f(int num){
	for(int i=2;i<=Math.sqrt(num);i++){
		if(num%2==0){
			return false;
		}
		return true;
	}
}

这种解法会极大的缩短时间，这也是我们一般会用到的解法，但是这个解法依旧不是很高效，于是乎，下面我们就不介绍更高效的解法了

练习

素数就是不能再进行等分的整数。比如:7，11。而9不是素数，因为它可以平分为3等份。一般认为最小的素数是2,接着是3，5, ...
我们假定2是第一个素数，3是第二个素数,以此类推...请你输出第666个素数的值.

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个数字，填写多余的内容将无法得分。

public class Main {
    public static void main(String[] args) {
        int n =666, count = 0, i = 2;
        while (count <= n) {
            if (isPrime(i)) {
                count++;
                if (count == n)
                    System.out.println(i);
            }
            i++;
        }
    }
 
    private static boolean isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0)
                return false;
        }
        return true;
    }
}

看到这，我相信大家已经掌握了素数的求解了吧，只需要再去刷几道题就好了，加油吧少年

送给大家一句话

乾坤未定，你我皆是黑马