蓝桥杯——求素数(看完绝对素数满分)
大家好,我是璐画
这篇文章是写蓝桥杯常考的算法之一——求解素数
这种题在之前的时候,会说的特别明显,而在近几届比赛中(貌似换了出题组),题目变得会绕个弯的问你,但是大家丝毫不用慌,题目在变,内容不变,所有的算法均有解答的框架,不信你看我之前的文章: 蓝桥杯——深搜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; }}
看到这,我相信大家已经掌握了素数的求解了吧,只需要再去刷几道题就好了,加油吧少年
送给大家一句话
乾坤未定,你我皆是黑马