6. 质因数的个数

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

120

输出

5

---

思路

质数基本定理说，一个大于1的整数要么本身是质数，要么可以被分解成质数之积，1既不是质数也不是合数。
对于100这个整数，我们来试着手工分析其质因子，从2开始试，

100%2=0，所以2是其一个质因子，100/2=50
50%2=0，2是其一个质因子，50/2=25
25%2=1，25%3=1，25%4=1,25%5=0，所以5是其一个质因子，25/5=5
5%2=1，5%3=2，5%4=1,5%5=0，5是其一个质因子，5/5=1，分解完毕

解法

由上面的思路，可以直接写出代码

#include<stdio.h>

int main(){
    int x = 0;    //输入的数
    while(scanf("%d", &x) != EOF){
        int count = 0;
        for(int i = 2; i <= x; i++){
            while(x % i == 0){    //从2开始试，用while循环把遇到的质数试干净，再继续往上试
                count++;
                x /= i;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

这个算法是正确的，但是只通过OJ的95%的数据测试，报错运行时间超出，说明时间复杂度太高，还需要继续优化。
改变for循环的规模，修改为：

#include<stdio.h>

int main(){
    int x = 0;    //输入的数
    while(scanf("%d", &x) != EOF){
        int count = 0;
        for(int i = 2; i * i <= x; i++){
            while(x % i == 0){    //从2开始试，用while循环把遇到的质数试干净，再继续往上试
                count++;
                x /= i;
            }
        }
        if(x > 1)
            count ++;
        printf("%d\n", count);
    }
    return 0;
}

模拟一遍就能很好的明白这个算法了，
假设输入的数是37，则for循环从0到6，这已经够了，因为37的质数要么是37本身，要么一定小于6，因为如果大于6的话，假设那个数是a，则37/a也一定小于6，也就是说循环不到a的，所以0到6这个循环够用了，循环结束的时候，如果质数都已经测试出来了，那么之前输入的数肯定会变成1，如果大于1的话，则之前输入的数本身就是一个质数。