蓝桥杯——求素数（看完绝对素数满分）

大家好，我是璐画

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

这种题在之前的时候，会说的特别明显，而在近几届比赛中（貌似换了出题组），题目变得会绕个弯的问你，但是大家丝毫不用慌，题目在变，内容不变，所有的算法均有解答的框架，不信你看我之前的文章： 蓝桥杯——深搜DFS（看完绝对入门DFS）https://blog.csdn.net/m0_47963315/article/details/123496806?spm=1001.2014.3001.5502所有的算法均有固定的东西，只要掌握了框架，万变不离其宗，废话不多说，直接开整

目录

什么是素数

素数简单求解

素数进阶求解

素数问题

送给大家一句话

什么是素数

这是百度百科的结果，搜索出来的直接就是质数，意思就是除了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;}}

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

 为什么呢？因为记得太多了反而忘了，而且蓝桥杯给的时间很宽裕的啊，不像leetcode

素数问题

素数就是不能再进行等分的整数。比如: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;    }}

这里就是题解，用的就是上面的素数求解方法啊，大家再多看看啊

下面给你们个绕一下的提，是改编的题，可以说这道题会了，你蓝桥杯素数必拿下！！！

看这道题，让你求多少对，而且每个都属素数，求组合与顺序无关啊

大家先自己想几分钟

思路

首先就是这个和顺序无关这个条件

比如9  （225）（333）（252）（522）这是全部，然后在看下，只有（225）（333）这两个啊

如何实现？

只需要a<=b<=c

就完美实现了啊

上代码

public class 友好搭档 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int num = sc.nextInt();int count = 0;for(int i=2;i<num;i++) {for(int j=2;j<num;j++) {for(int n=2;n=i&&n>=j&&f(i)&&f(j)&&f(n)&&i+j+n==num) {count++;}}}}System.out.println(count);}public static boolean f(int num) {  for(int i=2;i<=Math.sqrt(num);i++) {   if(num%i==0) {   return false;   }   }   return true; }}

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

送给大家一句话

乾坤未定，你我皆是黑马