文章目录

1 题目

质因子个数

时间限制 1000 ms 内存限制 32768 KB 代码长度限制 100 KB 判断程序 Standard (来自 小小)

题目描述

一个正整数可以分解成一个或多个数组的积。例如36=223*3，即包含2和3两个因子。NowCoder最近在研究因子个数的分布规律，现在给出一系列正整数，他希望你开发一个程序输出每个正整数的因子个数。

输入描述:

输入包括多组数据。

每组数据仅有一个整数n (2≤n≤100000)。

输出描述:

对应每个整数，输出其因子个数，每个结果占一行。

输入例子:

30

26

20

输出例子:

3

2

2

2 解析

先把素数表打印出来，然后再进行质因子分解操作。

对n==1，进行特判输出“1=1”；对于int范围的正整数进行质因子分解，素数表开到105大小就可以了。

3 参考代码

#include <cstdio>#include <cmath>struct factor{int x;int cnt;}fac[10];const int MAXN = 100010;int prime[MAXN], pNum = 0;bool p[MAXN] = {false};void findPrime(){for (int i = 2; i < MAXN; ++i) {if(p[i] == false){prime[pNum++] = i;for (int j = i + i; j < MAXN; j += i) {p[j] = true;}}}}int main(int argc, char const *argv[]){findPrime();int n;while(scanf("%d", &n) != EOF){int N = n;int num = 0;//不同质因子的个数int sqr = (int)sqrt(n*1.0);for (int i = 0; i < pNum && prime[i] <= sqr; ++i) {if(n % prime[i] == 0){//如果prime[i]是n的质因子fac[num].x = prime[i];fac[num].cnt = 0;while(n % prime[i] == 0){//计算质因子prime[i]个数fac[num].cnt++;n /= prime[i];}num++;//不同的质因子个数加1}if(n == 1) break;}if(n != 1){fac[num].x = n;fac[num++].cnt = 1;}printf("%d\n", num); //打印个数}return 0;}

如果觉得《质因子个数————质因子分解》对你有帮助，请点赞、收藏，并留下你的观点哦！