质因数
题目描述
求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
输入描述:
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。
输出描述:
对于每组数据，输出N的质因数的个数。
示例1
输入
120
输出
5
思路
1）题目需要多组测试用例，我的第一个想法是没能每个测试用例都去判断质数，所以可以使用打表法，把100000以内的质数标记出来
2）因为c++中的数组不能太大（同时也是考虑到题目有内存要求），标记的质数表不能全部包含所有可能的输入数据的质因数，这里就有一个小技巧：如果输入的数据n已经和2到n的开方之前的质数计算后，剩余不为1，则表示还存在一个大于质数表内的质数
#include<stdio.h>
#include<math.h>
#define maxSize 100000
int a[maxSize]= {0};//用于存储质数表，下标即为该数值，当数组值为0代表为质数，1为非质数
int main()
{
//使用筛选法
for(int i=2; i<10; i++)
{
for(int j=i*i; j<maxSize; j+=i)
{
a[j]=1;
}
}
int n,sum,temp;//sum存放质因数个数
while(scanf("%d",&n)!=EOF)
{
if(n<maxSize&&a[n]==0){//当输入的数小于数组的最大值，且对应数组值为0，即该数为质数
printf("1\n");
continue;
}
sum=0,temp=n;
for(int i=2;i<=sqrt(n)+1;i++)//在2到该数的开方值范围内的质数表中进行计算
{
if(!a[i]){
while(!(temp%i))
{
sum++;
temp/=i;
}
}
}
if(temp!=1) sum++;//如果temp计算后的值不为1，代表剩余的值是一个大于质数表内的质数
printf("%d\n",sum);
}
}思路升级
其实不需要再循环里判断i是为为质数，如果i是合数，则一定不会被整除：那前面的质数一定已经合数中包含的质数被整除过了
#include <iOStream>
#include <math.h>
using namespace std;
int main(){
int n;
while(cin>>n){
int i,count=0;
for(i=2;i<=sqrt(n);i++){
while(n%i==0){
count++;
n/=i;
}
if(n<1) break;
}
if(n>1) count++;
cout<<count<<endl;
}
return 0;
}
文章最后发布于: 2018-05-16 17:13:23
相关阅读
Office小知识（一）——word插入各种方向和条件个数的大括
Word中插入左右上下，多个单个花括号的总结 一：左右大括号（单个） 点击插入->公式，选择“括号”->“单方括号”，在插入的括号的虚线框中
相当于计算度数不超过4的无标号无根树个数。按照无根树的套路，我们直接枚举子树即可。但是无根树可以用exp来搞，这个度数有限制。我
题目描述输入n个整数,依次输出每个数的约数的个数。输入输入的第一行为N，即数组的个数(N<=1000)接下来的1行包括N个整数，其中每个数
辗转相减法： #include <stdio.h> #include <stdlib.h> int main() { int a, b; printf("请输入要求公约数的两个数："); scanf(
这篇文章来自 GrowingIO 联合创始人 & 运营副总裁陈明先生，全文总结了 15 个运营必备的数据分析方法论。不论是刚刚入行的萌新，还是