蓝桥杯2022Java研究生省赛3题质因数个数

 

import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main { public static void main(String[]args) { Scanner scan = new Scanner(System.in); // 唯一分离定律 任何一个数都可以被分解为两个质数相乘的形式 //所以找质因数 当一个数能 long n = scan.nextLong(); int res = 0; for (int i = 2; (long)i * i< n; i++) { if(n%i == 0) { //被整除 res++; while(n%i==0) {//那么就一直除到其b n = n/i; } } } if(n>1) { res++; } System.out.println(res); } }

举个例子，这种为什么不用判断是不是质因数，而是直接for循环（从2开始),原因就是如果能整除的话会一直while循环，我们先列举前几个循环的数   2  3  4  5  6  7  8  9 10  如果要找到的数是396， i = 2那么第一轮396%2 == 0好，我们先对396/2 = 198  198 / 2 = 99  99%2！=0 开始  i = 3 状态 99  33 11  好，下一个能整除11的只有11了 ，那么  4 5  6   7 8 9  10 为什么就不算因数了呢？

这里我将他们进行分类：

一、4 6 8 9 10 不是质数 如何排除的呢(就是如何保证不让他们参与循环的）呢？？？2 整除不了了，那么剩下的数必然没有  4  6 8 10 因数  ， 3 也整除不了了那后面的数必然也没有    9这个因数了.....这样就排除所有非质数了

二、 5  7 这些质数但不能整除原数是如何排除的呢？？？这个有点难理解，396之前除了一堆2 和 3 到了 5 了，不能整除了，那么就算你复原之前的的把 2 3再乘回去，5 也整除不了，就是这些无关质数不会因为除了前面的数而变得整除不了。（特性）

总结：质数的叠加相除

  while(n%i==0) {//那么就一直除到其b

                        n = n/i;

                    }   原因就是直接跳过之后出现的合数（不用再判断了是否为质数了）