要找到给定数字的质因数,为什么要将 for 循环的第二条语句设置为 i * i <= userInput 而不是 i <= userInput?
To find prime factors of a given number, why set the second statement of the for loop to i * i <= userInput instead of 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。
因为它将搜索 space 从 N 削减到 N 的平方根。
你可以这样写:
for (int i = 2; i <= Math.sqrt(userInput); i++)
这将循环的迭代次数从 N 减少到 N 的平方根。例如:如果 N = 16,则迭代次数将减少到 4。对于较小的 N,这看起来并不多,但你随着 N 值的增加,将会看到差异。
Imagine N=16, the factors are:
1,16 -- you are disallowing this anyway but I present if for completeness
2,8
4,4
------ The ones below are already covered and do not need to be looped through --------
8,2
16,1
一个更快的方法是找到一个增量器并链接 here。
我是 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。
因为它将搜索 space 从 N 削减到 N 的平方根。
你可以这样写:
for (int i = 2; i <= Math.sqrt(userInput); i++)
这将循环的迭代次数从 N 减少到 N 的平方根。例如:如果 N = 16,则迭代次数将减少到 4。对于较小的 N,这看起来并不多,但你随着 N 值的增加,将会看到差异。
Imagine N=16, the factors are:
1,16 -- you are disallowing this anyway but I present if for completeness
2,8
4,4
------ The ones below are already covered and do not need to be looped through --------
8,2
16,1
一个更快的方法是找到一个增量器并链接 here。