蓝桥杯算法训练 素因子去重

这个题不难，是我对书理解不透彻，把一个习题经验用错了地方，故记录成博客，告诫自己。 错误之处：int pri[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

在《算法进阶指南》里，约数那一部分提过一个引理：

1～N中任何数的不同质因子都不会超过 10 个，且所有质因子的指数总和不超过30。 证明： 最小的11个质数的乘积$2\times 3\times 5\times 7\times 11\times 13\times 19\times 23\times 29\times 31>2\times 10^9$，所以$N\le 2\times 10^9$不可能有多余10个不同的质因子

所以我最开始是这样写的：

const int P = 15; int pri[P] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}; ll n,ans = 1; signed main(){ cin >> n; for (int i = 0;i < P; i++) { if(n % pri[i] == 0)ans *= pri[i]; } cout << ans << endl; return 0; }

是我理解成了，[1, N]之内的所有数都可以用这些素数表示，其实很显然不是，如果稍微对 素数 理解深刻的人就马上会想到证据反驳我。 很容易举出反例，比如1231，就是一个素数，并且不能用上面这15个素数的乘积表示。

那么从头想起，我们只要这样就可以找到答案:

对于每一个i，判断它是不是n的约数 n % i == 0，每次找到n的一个约数就把答案乘上它 ans *= i，为了让这个约数只出现一次，所以要把这个约数的k倍，从n里剔除，也就是 while(n % i == 0) n /= i最后可能还剩下一个素数 n 除不尽，所以把最后的结果乘上n。 #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <list> #include <map> //#include <unordered_map> #include <stack> #include <vector> #include <typeinfo> #include <set> using namespace std; #pragma GCC optimize("Ofast") #define ll long long #define INF 0x3f3f3f3f #define ull unsigned long long #define ms(a, b) memset((a), (b), sizeof (a)) #define readfile(a) freopen((a),"r",stdin) ll n,ans = 1; signed main(){ cin >> n; for(int i = 2;i <= n / i;i++){ //要注意这里的是小于等于，比如 9的话，就要把考虑3进去 if(n % i == 0){ ans *= i; while (n % i == 0)n /= i; } } cout << ans * n << endl; return 0; }