蓝桥杯-质因数个数
- 1、问题描述
- 2、解题思路
- 2.1 质数判断
- 2.2 求取因子
- 3、完整代码实现
1、问题描述
给定正整数 n, 请问有多少个质数是 n 的约数。
输入格式
输入的第一行包含一个整数 n。
输出格式
输出一个整数, 表示 n 的质数约数个数。
样例输入
代码语言：javascript复制396样例输出
代码语言：javascript复制3样例说明
396 有 2,3,11 三个质数约数。
评测用例规模与约定
对于 30% 的评测用例, 1≤n≤10000 。
对于 60% 的评测用例,1≤n≤
。
对于所有评测用例, 1≤n≤
。
运行限制
- 最大运行时间：10s
- 最大运行内存: 512M
2、解题思路
质数又被称为素数，是指一个大于1的自然数，除了1和它本身外，不能被其他的自然数整除。
2.1 质数判断
判断一个数字是否是质数，就是看它的因子是否只有1和它本身。质数的判断我们简单写个函数判断就行，代码如下，遍历的时候不需要从2到n，只需要遍历到n的平方根即可。
代码语言：javascript复制//判断因子是否是质数
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整除的数即可，并且可以用一个数组或者集合去收集这些因子，求因子的代码实现如下：
代码语言：javascript复制遍历到
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、完整代码实现
代码语言：javascript复制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的三个质因数。
