首页 > 试题广场 >

质因数的个数

[编程题]质因数的个数
  • 热度指数：50506 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。

输入描述:
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。


输出描述:
对于每组数据，输出N的质因数的个数。
示例1

输入

120

输出

5
算法知识视频讲解
开通博客
头像 philos
发表于 2021-02-02 11:38:41
思路 我们求质因子的时候其实没有必要去先判断一个因子是否为质数，为什么呢？ 比如说一个因子为 11，是质数，那么无论前面怎么进行除法运算，一定有这个因子，所以质数因子不可能漏掉 而对于因子 4，它肯定可以转换成质因子之积：2×2，那么在前面已经被除过了，所以已经没有非质数因子了 所以我们只需要从 2 展开全文
去ta的博客 赞 (54) 回复(0) 收起
头像 瑞穗zz
发表于 2023-02-21 05:57:20
//对于一个数num，num%i==0 则i为其因子 //将i从2开始自增判断即可，i不是因子则自增，i是因子则num/=i，并且i=2 重新开始判断 //不需考虑i是否为质数，因为若i为合数，则当i为这个合数的因子时已经被判断为num的因子了 //这个循环的出口时num==1 #include 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 健康快乐最重要
发表于 2020-03-19 10:49:34
1.先用素数筛子求出sqrt(1e9)+1内的所有的素数（取根号是因为一个数n所有质因数中只有一个大于sqrt平方的）。2.依次对给定的数n除以他的质因数，如果除到了1，说明除尽了，如果没除到1，就将素数筛子里的数向后移一位判断。3.如果最后都判断完了，n仍！=1，说明存在一个大于他的根号的因数，那 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 鱼儿恋上水
发表于 2020-03-31 21:12:36
n至多只存在一个大于sqrt(n)的素因数1.利用素数筛法（欧拉筛法）筛得0-100000区间内所有素数2.输入n3.依次测试步骤1中得到的素数能否整除n，若能则表明该素数为它的一个素因数4.不断将n除以该素因数，直到不能被整除为止5.若在完成某个素数的幂指数统计后，n变为1，则表明n的所有素因数全 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 SteadyGG
发表于 2020-09-20 21:34:40
当枚举到i时意味着所有2 -（i-1）的质因子都除干净了 同时 n 不包括任何2 - （i-1）的质因子了 所以i一定是质数 int div(int x){ int s = 0; for(int i = 2; i <= n; i++){ if( 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 燃烧的橘子
发表于 2023-03-06 22:23:21
#include <iostream> using namespace std; int main() { int n; int ret; while(cin>>n) { ret=0; for(int i=2; 展开全文
去ta的博客 赞 (1) 回复(2) 收起
头像 子豪不自豪
发表于 2023-12-26 19:53:49
#include <math.h> #include <stdio.h> int judge_zhishu(int num){ for (int i=2;i*i<=num;i++){ if (num % i == 0){ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客568792594号
发表于 2024-02-16 15:35:26
#include <bits/stdc++.h> using namespace std; int divide(int x){ int count = 0; for (int i=2; i<=x/i; i++){ if (x%i == 0){ int s = 0 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 吃葡萄不爱吐葡萄皮
发表于 2024-03-21 12:03:41
#include <stdio.h> #include <math.h> int IsPrime(int n); int main(){ int x,count; while(scanf("%d",&x)!=EOF){ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客440904392号
发表于 2024-10-04 21:09:54
#include <stdio.h> int main() { int n; while (scanf("%d", &n) != EOF) { int count = 0; for (int i = 2; i * 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

基础数学
难度：
168条回答 31182浏览

热门推荐

通过挑战的用户

查看代码

相关试题

质因数的个数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号