求约数

求一个数的约数个数

方法一:简单粗暴,for循环取余计数

public static int f1(int n) {
     int ans=0;
     for(int i=1;i<=n;i++) {
	if(n%i==0){
	ans++;
	}
     }
     return ans;
}

方法二:优化方法一,范围从1-n到1-\(\sqrt{n}\)。

public static int f2(int n) {
    int ans=0;
    for(int i=1;i*i<=n;i++) {
	if(n%i==0){
	  if(i*i==n) {
	    ans++;  // 在36中,会遇到6*6的可能
	  }else ans+=2;  // +2是因为i<根号n,只会判断一半,所以+2
	}
    }
    return ans;
}

方法三:使用公式 \(\mathbf{n}=\prod_{i=1}^{k} p_{i}^{a_{i}}=p_{1}^{a_{1}}* p_{2}^{a_{2}} \ldots p_{k}^{a_{k}}\)

如此,约数的个数就为\((a_{1}+1)(a_{2}+1)\dots (a_{k}+1)\)

例如:24= 2*2*2*3=\(2^{3} \cdot 3^{1}\) 那么24的约数个数为(3+1)(1+1)= 8

public static int f3(int n) {
     int ans=1;  // 要连*,初始值为1
     int temp=n;
     for(int i=2;i*i<n;i++) {  //for循环这里不用考虑i=4的情况,可参考视频最后,所有的i都为素数
        int num=0;            //  如 720,180/2=90/2=45/3=15/5=3,不会出现除4的可能,因为一
	    while(temp%i==0){     //  旦4可以除尽,前面/2的时候一定会把它除掉
	       num++;
	       temp/=i;
	    }
	    ans=ans*(num+1);
      }
      if(temp>1)ans=ans*(1+1);  // 如果temp最后是素数,不会进入到上面的for循环,只有1和它自己
      return ans;               // 如68=2*2*17 temp最后就是17,17是素数,只能被1和自己整除,
		                // 就不会进入for循环中,但是也作为68的一个约数,所以要+1
}

100!的约数个数

如果直接先把100!算出来再求约数个数,就很容易超时。

  • 定义prime数组,用来后期统计1-100的约数个数
  • 参考方法三,求出每个数的约数个数,放入prime数组
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long res=fun(100);
		System.out.println(res);
		
	}
	
	public static long fun(int n) {
		int[] prime=new int[n+1];
		long ans=1;
		for(int i=2;i<=n;i++) {  //这个循环是 1*2*3*4...98*99*100
			int temp=i;
			for(int j=2;j*j<=temp;j++) {  // 此循环求一个数的约数个数
				while(temp%j==0) {
					prime[j]++;
					temp/=j;
				}
			}
			if(temp>1)prime[temp]++;
		}
		for(int k=2;k<n;k++) {
			if(prime[k]>=1)ans=ans*(prime[k]+1);
		}
		return ans;
	}

}
消息盒子
# 您需要首次评论以获取消息 #
# 您需要首次评论以获取消息 #

只显示最新10条未读和已读信息