蓝桥杯-阶乘约数-java

<>题目描述

定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。

* 数论的一个知识点：

思路：
举个例子
180=2 * 2 * 3 * 3 * 5=22*32 * 5
那么 2 的2 次方对应的约数有 1 2 4 （3个）
3的二次方约数有 1，3， 9 （3个）
5的约数有 1，5 （2个）
则180的约数个数有(1+2) * (1+2) * (1+1)=18个。直接模拟判断约数的个数即可
利用唯一分解定理，分解出质因数对应的的幂数
其中arr数组对应的是质因数的幂数，也就是 a1,a2,a3…
public class Main { public static void main(String[] args) { // 100 的阶乘有多少约数
int[] arr=new int[102]; //利用唯一分解定理分解100的阶乘 // 必须要从2开始 for (int i=2;i<=100;i++){
int n=i; for (int j=2;j*j<=n;j++ ){ while (n%j==0){// 当能够整除 的时候，对应余数的幂次加一 arr[j]
++; n/=j; } } //整除完了后如果剩下的n不为1，则当前的n为因子 if (n>1){ arr[n]++; } } long ans=1; for
(int i=2;i<=100;i++){ if (arr[i]>0){ ans*=(arr[i]+1); } } System.out.println(ans
); } }
其中我们判断在一定范围也可以通过下面 的isprime方法构造素数数组也可
public static boolean isprime(int x){ if (x==1) return false; for (int i=2;i<x;
i++){ if (x%i==0){ return false; } } return true; }

• « 上一篇：选择排序原理
• » 下一篇：开发自己的SpringBoot Starter