题解 | #质数因子#
质数因子
https://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); Integer input = Integer.parseInt(scanner.nextLine()); StringBuilder stringBuilder = new StringBuilder(); findMinPrimeNumber(input, 2, stringBuilder); System.out.println(stringBuilder); } private static void findMinPrimeNumber(Integer input, int lastPrimeNumber, StringBuilder stringBuilder) { if (isPrimeNumber(input)) { stringBuilder.append(input).append(" "); return; } for (int i = lastPrimeNumber; i < input; i++) { if (!isPrimeNumber(i)) { continue; } if (input % i == 0) { stringBuilder.append(i).append(" "); input = input / i; lastPrimeNumber = i; findMinPrimeNumber(input, lastPrimeNumber, stringBuilder); return; } } return; } public static boolean isPrimeNumber(int num) { if (num <= 3) { return true; } //针对大于等于3的自然数,如果这个数是素数,那么一定满足 6x + 1或者 6x - 1。x是大于等于1的自然数 //比如 11 就等于 6x2-1。5就等于6x1-1,7就等于6x1+1。 if (num % 6 != 1 && num % 6 != 5) { return false; } //如果一个数a是合数,那么假设其可以分解为x,y.即 x * y = a. //假设 x <= y,那么一定会满足 x <= √a 且 y>= √a。 //所以只要从2判断到√a,发现数a无法被任何数整除,那么就证明数a是素数 int sqrt = (int) Math.sqrt(num); for (int i = 2; i <= sqrt; i++) { if (num % i == 0) { return false; } } return true; } }#每日一刷#