分解素因数——1. 质因数的个数

质因数的个数

题目描述

求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235，共有5个质因数。

输入描述:

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

输出描述:

对于每组数据，输出N的质因数的个数。

示例1

输入

120

输出

5

解题心得：

• 分解素因数： image.png
• 算法：我们按照之前所讲的素数筛选法（见素数筛选——2. 素数）预先筛选出所有可能在题面所给定的数据范围内成为素因数的素数。并在程序输入待处理数字n时，依次遍历所有小于n的素数，判断其是否为n的因数。若确定某素数为n的因数，则通过试除确定其对应的幂指数。最后求出各个幂指数的和即为所求。
• 题目中n小于10^9，素数只需筛选到100000即可。数n最多只可能存在一个大于100000的素因子，其幂指数必为1。
• 程序运行时出错，经检查是因为乘法溢出。添加当i>=1000时，不再找该素数的倍数，即

if(i>=1000)
     continue;

• 提交程序时，记得检查是否把自测时额外的输出已删除。

• 当我们完成素因数分解后我们同样可以确定被分解整数因数的个数为

  
  image.png

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>



int main(){

   int m[100001]={0},n,i,j,size=0,msize[100000];
   for(i=2;i<=100000;i++){
        if(m[i]==0){
                msize[size]=i;
                size++;
              
            if(i>=1000)
                continue;
            for(j=i;j*i<=100000;j++){
                m[j*i]=1;
            }
        }
   }


   while(scanf("%d",&n)!=EOF){

        int nsize[100000]={0},sum=0;
    for(i=0;i<size;i++){
        if(n<=1){
            break;
        }
        while(n%msize[i]==0){
            nsize[i]++;
            n=n/msize[i];
            
        }
    }
    if(n>1){
        sum++;
    }
    for(j=0;j<i;j++){
        sum=sum+nsize[j];
    }
    printf("%d\n",sum);
   }
    return 0;

}

如果觉得有帮助，就点个赞再走吧^_^