因子和阶乘

这道编程题出自我之前从师兄那淘到的一本书:《算法竞赛入门经典》,清华大学出版社,刘汝佳著。

输入正整数 n (n ≤ 2 ≤ 100),把阶乘 n! = 1 ✖ 2 ✖ 3 ✖ … ✖ n 分解成素因子相乘的形式,从小到大输出各个素数的指数。
例如:825 = 3 ✖ 52 ✖ 11,应表示成(0, 1, 2, 0, 1),表示分别有0、1、2、0、1个2、3、5、7、11。
样例输入:
5
13
样例输出:
5! = 3 1 1
53! = 49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1

具体代码如下:

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
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>

using namespace std;

// 素数判断函数(很经典了吧)
bool is_prime(int n) {
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int main(void) {
    int n;
    while (cin >> n) {
        vector<int> primes; // 用于存储素数
        vector<int> cnt(101, 0); // 一个hash数组,用于记录指数,即有多少个素数
        for (int i = 2; i <= n; i++) {
            // 如果是素数,那么记录指数
            if (is_prime(i)) {
                cnt[i]++;
                primes.push_back(i);
            }
            // 否则将其分解
            else {
                int tmp_i = i;
                for (int j = 0; j < primes.size(); j++)
                    while (tmp_i % primes[j] == 0) {
                        cnt[primes[j]]++;
                        tmp_i /= primes[j];
                    }
            }
        }
        // 输出
        cout << n << "! = ";
        for (int i = 0; i < primes.size(); i++) {
            cout << cnt[primes[i]] << ' ';
        }
        cout << endl;
    }
    return 0;
}


Leave a Reply

Your email address will not be published. Required fields are marked *