[数据结构与算法]【思特奇杯·云上蓝桥-算法集训营】第1周 阶乘约数

蓝桥杯——阶乘约数

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

这个题主要还是数论里面的知识。

一个数的约数等于它的所有质因数的个数+1的乘积。

有了这个定理。根据100的阶乘。

很容易地将1~100的乘积，分解为所有质因数的乘积。

接着再计算质因数的个数即可。

注意这里是填空题，因此不用利用质数的筛法。我认为直接暴力计算1~100的质数就行了。

然后利用一个循环将每一个数一 一分解为质因数即可。

代码如下：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main()
{   
    int check(int n);
    long long all=1;
    int len,number[100]={0},temper;
    vector<int> a;
    
    for(int i=2;i<=100;i++) // 简单的创建一个1~100的质数数组
        if(check(i))
            a.push_back(i);
    len=a.size();
    
    for(int i=2;i<=100;i++)  // 将每一个数分解成质因数后，这里为了计入方便直接创建1~100的数组，对号入座。
    {                        // 因为后续的那个公式默认+1，所以直接将数组归零即可。
        if(check(i))
            number[i-1]++;
        else
        {   
            temper=i;
            while(temper!=1)
            {
                for(int j=0;j<len;j++)
                    if(temper%a[j]==0)
                    {
                        number[a[j]-1]++;
                        temper=temper/a[j];
                        break;
                    }
            }
        }
    }
    
    for(int i=0;i<100;i++)
        all=all*(number[i]+1);

    cout << all << endl;
    return 0;    
}
int check(int n)  
{   
    if(n<2)
        return 0;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}