算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。
例如
90=2 * 3^2 * 5；
1
我们要做的就是找到90的所有质因子，然后统计个数；
模板：
#include <iostream>#include<map>#include<cstdio>using namespace std;int a[1000];//用来存放一个数的质因子map<int,int> mp;//统计每个质因子出现的次数int main(){int n;int id=0;//作为数组的下标scanf("%d",&n);for(int i=2;i*i<=n;i++) //一个数的质因子不会超过这个数的算术平方根{if(n%i==0) a[id++]=i;//把满足条件的质数（素数）记录下来while(n%i==0)//并且统计含有多少个这样的质因子{mp[i]++;n/=i;//时刻更新n的值}}if(n>1) a[id++]=n,mp[n]++;//如果n到最后没有被除尽，那么剩下的数也是一个质因子for(int i=0;i<id;i++)printf("%d %d\n",a[i],mp[a[i]]);return 0;}
结果：
上午写了统计一个数的质因子，下午应用的时候，Runtime error整整一下午；刚开始用上面的方法一直time limit；后来在网上查阅资料，发现可以先对素数打表，然后把是素数的放在一个数组里，依次从小到大判断这个素数是不是当前数的因子；
具体代码如下：
const int maxx=1e6+7;ll pr[maxx];//标记素数ll pp[maxx];//存放素数void prime(){for(int i = 2; i <= sqrt(maxx); i++)if(!pr[i])for(int j = i * i; j <= maxx; j += i)pr[j] = true;for(int i = 2; i <= maxx; i++)if(!pr[i])pp[cot ++] = i;}void get_prime(ll n){for(int i = 0; i < cot && pp[i] <= sqrt(n); i++)//以此判断数组里面的素数是否为当前数的因子；并且因子要小于当前数的算术平方根{int cc = 0;while(n % pp[i] == 0){cc ++;n /= pp[i];}sum *= (cc + 1);}if(n > 1)sum *= 2;}
这样写没问题吧，当然；可是就是Runtime error；我数组也没有开特别大或者特别小啊，检查了一下午 交了四十多次；我真的好难啊~~~…
后来发现，题中的内存限制为32Mb，我开了两个1e6的int型数组，用的时候数组太大，造成爆栈，所以runtime error；
改用bool类型的数组好多了，一下子就ac了（bool型只占一个字节）
同时对素数的筛选和记录也换了种方式；
const int maxx = 1e6 + 10;bool pr[maxx];ll pp[maxx];ll sum, cot;ll a,b;void prime(){for(int i = 2; i <= sqrt(maxx); i++)if(!pr[i])for(int j = i * i; j <= maxx; j += i)pr[j] = true;for(int i = 2; i <= maxx; i++)if(!pr[i])pp[cot ++] = i;}void get_prime(ll n){for(int i = 0; i < cot && pp[i] <= sqrt(n); i++){int cc = 0;while(n % pp[i] == 0){cc ++;n /= pp[i];}sum *= (cc + 1);}if(n > 1)sum *= 2;}
写着写着就想吐，太难受了 ，，，，，，一下午四十多发，我好难…
上面代码用到了素数筛和统计因子个数的公式；
到这里就ojbk了。。。。
如果觉得《算术基本定理之统计质因子个数———以及因子的个数》对你有帮助，请点赞、收藏，并留下你的观点哦！
