题解 | #质数因子#
质数因子
https://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int i = 2; // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case int a = in.nextInt(); while(a > 0){ if(a % i == 0 && judge(i)){ System.out.print(i + " "); a = a / i; }else{ i ++; } if(judge(a)){ if(a == 1){ return; } System.out.print(a); return; } if(i > a){ return; } } } } //判断是否为质数 public static boolean judge(int a){ for(int i = 2; i < a/2 + 1; i ++){ if(a % i == 0){ return false; } } return true; } }
总思路:对传来的数从i = 2(第一个质数)进行整除,整除不了就++,并进行判断这个i是否为质数,直到整除完毕
判断质数思路:就是在1和本身(不包含)之间进行整除,但全遍历的话效率会很低,考虑到对称性,由一半的数进行整除就行