n!的因子数

coding>C++
742 词

题目描述

n的因子数你一定知道啦，比如6有因子1,2,3,6 我们就说$div(6)=4$现在我们换一个问题，我们希望计算$n!$拥有多少个不同的因子，比如$3!=6$所以我们应该输出$4$

输入

每行只有一个正整数n$(1<=n<=100)$

输出

输出n!对应的不同因子数，结果可能很大，请用64位整数存储

样例输入

1
3

样例输出

1
4

提示

整数的质因子分解

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>

using namespace std;
using ll = long long;
const int maxn = 1000 + 1;
char is_prime[maxn];
ll primes[maxn], k = 0;
ll n;

void fill() {
    for (ll i = 2; i <= n; i++)is_prime[i] = 1;
    for (ll i = 2; i <= n / i; i++)if (is_prime[i])for (int j = 2 * i; j <= n; j += i)is_prime[j] = 0;
    for (ll i = 0; i <= n; i++) if (is_prime[i])primes[k++] = i;
}

int main() {
    ll tot = 1;
    cin >> n;
    fill();
    for (int i = 0; i < k; i++) {
        ll j = 0;
        ll p = primes[i];
        for (ll t = p; t <= n; t *= p)
            j += n / t;

        tot = tot * (j + 1);
    }
    cout << tot << endl;
    return 0;
}