@toc

1、问题描述

给定正整数 n, 请问有多少个质数是 n 的约数。

输入格式

输入的第一行包含一个整数 n。

输出格式

输出一个整数, 表示 n 的质数约数个数。

样例输入

396

样例输出

3

样例说明

396 有 2,3,11 三个质数约数。

评测用例规模与约定

对于 30% 的评测用例, 1≤n≤10000 。

对于 60% 的评测用例,1≤n≤ $10^9$ 。

对于所有评测用例, 1≤n≤ $10^{16}$ 。

运行限制

• 最大运行时间：10s
• 最大运行内存: 512M

2、解题思路

质数又被称为素数，是指一个大于1的自然数，除了1和它本身外，不能被其他的自然数整除。

2.1 质数判断

判断一个数字是否是质数，就是看它的因子是否只有1和它本身。质数的判断我们简单写个函数判断就行，代码如下，遍历的时候不需要从2到n，只需要遍历到n的平方根即可。

//判断因子是否是质数
    public static boolean judge(long n){
        if(n==0||n==1){
            return false;
        }
        for (long i = 2L; i <=Math.sqrt(n); i++) {
            if(n%i==0){
                return false;
            }
        }
        return true;
    }

2.2 求取因子

关于一个数字的因子，我们在这里找出所有能够被我们输入的数字n整除的数即可，并且可以用一个数组或者集合去收集这些因子，求因子的代码实现如下：

遍历到Math.sqrt(n)即可。

 //返回因子list
    public static List<Long> factor(long n){
        ArrayList<Long> arr = new ArrayList<>();
        for (long i = 1L; i <=Math.sqrt(n) ; i++) {
            if(n%i==0){
                arr.add(i);
                if(i!=n/i){
                    arr.add(n/i);
                }
            }
        }
        return arr;
    }

上面两步已经完成了求取因子和判断质数的函数，我们只需要遍历因子集合，判断每个因子是否是质数即可，用一个计数器变量count来统计质因子的个数就行，最后输出这个count。

3、完整代码实现

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n=scan.nextLong();
        List<Long> factor = factor(n);
        long count=0L;
        for (Long f : factor) {
            if (judge(f)) {
                count++;
            }
        }
        System.out.println(count);
        scan.close();
    }
    //返回因子list
    public static List<Long> factor(long n){
        ArrayList<Long> arr = new ArrayList<>();
        for (long i = 1L; i <=Math.sqrt(n) ; i++) {
            if(n%i==0){
                arr.add(i);
                if(i!=n/i){
                    arr.add(n/i);
                }
            }
        }
        return arr;
    }
    //判断因子是否是质数
    public static boolean judge(long n){
        if(n==0||n==1){
            return false;
        }
        for (long i = 2L; i <=Math.sqrt(n); i++) {
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
}

输入一个测试用例试一下

2、3、11是396的三个质因数。