題目描述
定義階乘 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/402684.html
標籤：其他
上一篇：2021學習記錄