java - 要找到给定数字的质因数，为什么要将 for 循环的第二条语句设置为 i * i <= userInput 而不是 i <= userInput？

Question

我是 Java 的新手，正在尝试解决查找给定数字的所有质因数的问题。有人告诉我是否将 for 循环的第二条语句设置为 i * i <= userInput instead of i <= userInput ，程序会更有效率。

我不明白为什么会这样。背后的原因是什么？

Scanner sc = new Scanner(System.in);
int userInput = sc.nextInt();
        sc.close();
        System.out.println("Prime factors of " + userInput + " include: ");

        for (int i = 2; i * i <= userInput; i++){
            while(userInput % i == 0){
                System.out.print(i + " ");
                userInput /= i;
            }
        }
        if (userInput > 1){
            System.out.print(userInput);
        } else {
            System.out.print("");
        }

Answer 1

事实上，这段代码不仅会找到质因数——它还会搜索所有因数。如果你的数字是 Y 可以表示为 X * X，那么任何低于 X 的因子都会有大于 X 的匹配因子。所以你只需要检查所有情况的一半。对于 14 当你发现 2 是因子时，匹配因子是 7，所以你不需要检查 7 的匹配因子。这就是为什么你的条件是包含 i*i。