原题链接：最多约数问题
第一种方法：
遍历1到sqrt（num），如果num能被循环的i整除，则当前数为num的约数，其背面num/i也为num的约数
当num为一个平方数时，i会计入两次，所以添加一个a/i！=i来判段
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 | import java.util.HashSet;import java.util.Set;public class Main{ static Set set=new HashSet<>(); public static void main(String[] args) { //这里举例求2000的约数 int a=2000; //遍历1到sqrt(2000) for(int i=1;i*i<=a;i++) { if(a%i==0) { //加入集合 set.add(i); //判段是否为i*i=num，排掉重复 if(a/i!=i) { set.add(a/i); } } } //输出约数 for(int i:set) { System.out.println(i); } System.out.println(); //输出约数个数 System.out.println(set.size()); } } |
第二种方法：
其实第二种方法我用的还比较多，从蓝桥杯20年国赛第三题用的就是这种方法好算一些，但是这个方法好像在这道题时间会溢出，麻了。
第一步：欧拉筛选质数
第二部：判段传入num是否为质数，如果为质数，则直接返回2,如果不是则遍历2到num-1,把num的所有质数个数找出来，比如20可以分成2个2和一个5；选2有3种情况，选一个2\两个2或者不选，5也可以分为0或者1，组合出来的结果就是(2+1）*（1+1）=6。此题也是如此，找到一个数的所有质数个数，把每个质数个数+1全部乘起来就是ans。
第三部，遍历a到b，找出div返回值最大的；
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | import java.io.*;public class Main{ static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); static boolean[] isPrime; static int a,b; public static void main(String[] args) throws IOException { String[] temp=bf.readLine().split(" "); int a=Integer.parseInt(temp[0]); int b=Integer.parseInt(temp[1]); //欧拉筛 isPrime=new boolean[b+1]; isPrime[0]=isPrime[1]=true; for(int i=2;i*i<=b;i++) { if(!isPrime[i]) { for(int j=2*i;j<=b;j+=i) { isPrime[j]=true; } } } long max=0; for(int i=a;i<=b;i++){ max=Math.max(max,div(i)）; } pw.print(max); pw.flush(); } public static long div(int num) { long ans=1; int[] arr=new int[num]; //判段是否为质数 if(!isPrime[num]) { return 2; }else { //存储当前变量，避免被下面运算修改 int temp=num; //循环2至num-1，如果为质数就arr[i]++ for(int i=2;i<num;i++) { if(!isPrime[i]) { while(temp%i==0) { temp/=i; arr[i]++; } } } //组合 for(int i=1;i<num;i++) { if(arr[i]!=0) { ans*=(arr[i]+1); } } } return ans; }} |
第三种方法：
这个其实是很容易的方法，但也是过这题的方法。
有点像欧拉筛，也是一个很好的方法，遍历1到b，把它的倍数存到相应的数组中去，这样就可以得到每个数的约数了。循环a-b，获得最大数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | import java.io.*;public class Main{ static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); public static void main(String[] args) throws IOException { //读取 String[] temp=bf.readLine().split(" "); int a=Integer.parseInt(temp[0]); int b=Integer.parseInt(temp[1]); int[] arr=new int[b+1]; //遍历1到b,把他的倍数++ for(int i=1;i<=b;i++) { for(int j=i;j<=b;j+=i) { arr[j]++; } } int max=0; for(int i=a;i<=b;i++) { max=Math.max(arr[i],max); } pw.print(max); pw.flush(); }} |
9.9 分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复