首页 > itarticle > uva 884 – factorial factors

uva 884 – factorial factors

admin 11月 12, 2020 0

Contents

Problem

簡單來說就是將 $n!$ 質因數分解，來看有幾個數字。

Solution

分解方法跟 UVa 10856 一樣用 DP 。

Code


#define N 1000001

int factorial[N];
void ();
int main()
{
    int n;
    solve();
    while (scanf("%d", &n) != EOF)
        printf("%dn", factorial[n]);

    return 0;
}
void ()
{
    int i;
    for (i = 0; i < N; i++)
        factorial[i] = 1;
    factorial[1] = 0;

    for (i = 2; i < N; i++)
    {
        if (factorial[i] == 1)
        {
            for (int j = 2; i*j < N; j++)
                factorial[i*j] = factorial[i] + factorial[j];
        }
    }

    for (i = 2; i < N; i++)
        factorial[i] += factorial[i - 1];
}