前言
这篇文章是写常考的算法之一——求解素数
这种题在之前的时候，会说的特别明显，而在近几届比赛中（貌似换了出题组），题目变得会绕个弯的问你，但是大家丝毫不用慌，题目在变，内容不变，所有的算法均有解答的框架，不信你看我之前的文章：
所有的算法均有固定的东西，只要掌握了框架，万变不离其宗，废话不多说，直接开整
什么是素数
这是百度百科的结果，搜索出来的直接就是质数，意思就是除了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*612=3*412=sqrt(n)*sqrt(n)//分界12=4*312=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;
}
}
看到这，我相信大家已经掌握了素数的求解了吧，只需要再去刷几道题就好了，加油吧少年
送给大家一句话
乾坤未定，你我皆是黑马