这道编程题出自我之前从师兄那淘到的一本书：《算法竞赛入门经典》，清华大学出版社，刘汝佳著。
输入正整数 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; } |
