Problem Solving►UVa

UVa 884 - Factorial Factors

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

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

Solution

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

Code

UVa 884
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
31
32
33
#include<cstdio>
#define N 1000001

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

    return 0;
}
void solve()
{
    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];
}