考研机试 7.质因数的个数

时间：2021/02/23

一.题目描述

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

输入描述

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

输出描述

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

题目链接

https://www.nowcoder.com/practice/20426b85f7fc4ba8b0844cc04807fbd9?tpId=40&tqId=21338&rp=1&ru=%2Fta%2Fkaoyan&qru=%2Fta%2Fkaoyan%2Fquestion-ranking&tab=answerKey

二.算法

题解

下面的代码是参考讨论区的大佬写的，最好的理解方法是带进数执行一边代码。因为输入n至多只存在一个大于sqrt(n)的质因数，所以for循环的上限是sqrt(n)，在for循环外还要再判断一下是否有一个大于sqrt(n)的质因数。

代码

import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        
        Scanner in = new Scanner(System.in);
        
        while(in.hasNext()){
            long n = in.nextLong();
            int count = 0;
            
            for(long i = 2; i <= Math.sqrt(n); i++){
                
                while(n % i == 0){
                    n /= i;
                    count++;
                }
                
                if(n <= 1){
                    break;
                }
            }
            
            if(n > 1){
                count++;
            }
            
            System.out.println(count);
        }
        
        in.close();
    }
}