欧拉计划 #3 Java:为什么在寻找最大质因数时向上数到平方根,而不是从平方根向下数?
Project Euler #3 Java: Why count up to square root when finding the largest prime factor, rather than counting down from square root?
我正在尝试解决项目 Euler 的问题 3,我编写了以下代码,它给出了正确答案
public class 最大素因子 {
public static boolean isPrime(int p) {
boolean isPrime = true;
for (int i = 2; i < p / 2; i++) {
if (p % i == 0) {
return false;
}
}
return isPrime;
}
public static double largestPrimeFactor(long n) {
double factor = 0;
for (int j=1; j<Math.sqrt(n); j++) {
System.out.println("j is : "+ j);
if (n % j == 0 && isPrime(j)) {
factor = j;
}
}
return factor;
}
public static void main(String args[]) {
long limit = 600851475143L;
System.out.println(largestPrimeFactor(limit));
}}
我想知道当我们寻找最大因数时,从 1 开始并增加到平方根是否是个好主意。所以我尝试将 largestPrimeFactor(long n) 方法中的 for 循环更改为从 n 的平方根开始倒数。但是现在我得到了一个错误的答案。这是什么原因?
public class LargestPrimeFactor {
public static boolean isPrime(int p) {
boolean isPrime = true;
for (int i = 2; i < p / 2; i++) {
if (p % i == 0) {
return false;
}
}
return isPrime;
}
public static double largestPrimeFactor(long n) {
double factor = 0;
for (int j=(int)Math.sqrt(n); 1<j; j--) {
System.out.println("j is : "+ j);
if (n % j == 0 && isPrime(j)) {
factor = j;
}
}
return factor;
}
public static void main(String args[]) {
long limit = 600851475143L;
System.out.println(largestPrimeFactor(limit));
}}
您在找到第一个质因数后没有休息 - 您找到的第一个是最大的,您不应该进一步搜索。为此,你应该 return 你找到的第一个正确值是这样的
public static double largestPrimeFactor(long n) {
double factor = 0;
for (int j=(int)Math.sqrt(n); 1<j; j--) {
if (n % j == 0 && isPrime(j)) {
return j; // Changed this line
}
}
return factor;
}
我正在尝试解决项目 Euler 的问题 3,我编写了以下代码,它给出了正确答案 public class 最大素因子 {
public static boolean isPrime(int p) {
boolean isPrime = true;
for (int i = 2; i < p / 2; i++) {
if (p % i == 0) {
return false;
}
}
return isPrime;
}
public static double largestPrimeFactor(long n) {
double factor = 0;
for (int j=1; j<Math.sqrt(n); j++) {
System.out.println("j is : "+ j);
if (n % j == 0 && isPrime(j)) {
factor = j;
}
}
return factor;
}
public static void main(String args[]) {
long limit = 600851475143L;
System.out.println(largestPrimeFactor(limit));
}}
我想知道当我们寻找最大因数时,从 1 开始并增加到平方根是否是个好主意。所以我尝试将 largestPrimeFactor(long n) 方法中的 for 循环更改为从 n 的平方根开始倒数。但是现在我得到了一个错误的答案。这是什么原因?
public class LargestPrimeFactor {
public static boolean isPrime(int p) {
boolean isPrime = true;
for (int i = 2; i < p / 2; i++) {
if (p % i == 0) {
return false;
}
}
return isPrime;
}
public static double largestPrimeFactor(long n) {
double factor = 0;
for (int j=(int)Math.sqrt(n); 1<j; j--) {
System.out.println("j is : "+ j);
if (n % j == 0 && isPrime(j)) {
factor = j;
}
}
return factor;
}
public static void main(String args[]) {
long limit = 600851475143L;
System.out.println(largestPrimeFactor(limit));
}}
您在找到第一个质因数后没有休息 - 您找到的第一个是最大的,您不应该进一步搜索。为此,你应该 return 你找到的第一个正确值是这样的
public static double largestPrimeFactor(long n) {
double factor = 0;
for (int j=(int)Math.sqrt(n); 1<j; j--) {
if (n % j == 0 && isPrime(j)) {
return j; // Changed this line
}
}
return factor;
}