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

我是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("");
        }

最佳答案

实际上，此代码不仅会找到主要因素，还会搜索所有因素。如果您的数字为Y可以表示为X * X，则X之下的任何因数都将具有大于X的匹配因数。因此，您只需要检查所有情况的一半即可。对于14，当您发现2是因子时，匹配因子为7，因此您无需检查匹配因子7。这就是为什么您的条件包含i * i的原因。

关于java - 要查找给定数字的素数，为什么将for循环的第二条语句设置为i * i <= userInput而不是i <= userInput？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34854166/