算术基本定理之统计质因子个数

2024-07-12 09:22| 来源: 网络整理| 查看: 265

算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。例如 90=2 * 3^2 * 5；

我们要做的就是找到90的所有质因子，然后统计个数；模板：

#include #include #include using namespace std; int a[1000];//用来存放一个数的质因子 map mp;//统计每个质因子出现的次数 int main() { int n; int id=0;//作为数组的下标 scanf("%d",&n); for(int i=2;i*i mp[i]++; n/=i;//时刻更新n的值 } } if(n>1) a[id++]=n,mp[n]++;//如果n到最后没有被除尽，那么剩下的数也是一个质因子 for(int i=0;i for(int i = 0; i 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 int cc = 0; while(n % pp[i] == 0) { cc ++; n /= pp[i]; } sum *= (cc + 1); } if(n > 1) sum *= 2; }

写着写着就想吐，太难受了，，，，，，一下午四十多发，我好难…

上面代码用到了素数筛和统计因子个数的公式；

在这里插入图片描述到这里就ojbk了。。。。

【本文地址】

公司简介

联系我们