求约数的3种方法

第一种方法：

遍历1到sqrt（num），如果num能被循环的i整除，则当前数为num的约数，其背面num/i也为num的约数

当num为一个平方数时，i会计入两次，所以添加一个a/i！=i来判段

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返回值最大的；

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，获得最大数

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();
	}
}