600851475143(Java)的最大素数因子是多少?我可能犯了什么错误?

Question

代码对于int数据类型工作得很好，但是600851475143似乎是一个太大的数字。我怎样才能让它工作?它一直在运行，从来没有给我一个答案。

public class Main {
public static void main(String[] args) {
long a = 600851475143L;
boolean prime = false;
long big = 0L;
for (long i = 1L; i < a; i++){
if (a % i == 0){
for (int j = 2; j < i/(float)2; j++){
if (i % j == 0){
prime = true;
break;
}
}
if(!prime){
big = i;
}
}
}
System.out.println(big);
}
}

Answer 1

您需要为j使用long。

你的变量命名也有点误导:prime是真的，当数字不是素数…

Answer 2

你的代码有很多问题。我的第一个建议是，使用命名良好的变量编写干净简洁的代码。其次，分析程序的运行时复杂性，即使它在大输入下运行得很快。在if(a % i == 0)条件下运行内部循环的事实，使您的程序效率极低。

在这里，我提供了一个重构版本的代码，考虑了运行时的复杂性和良好的变量名称:

public static void main(String[] args) {
System.out.println(largestPrimeFactorOf(600851475143L));
}
public static long largestPrimeFactorOf(long input)
{
List<Long> factors = new ArrayList<>();
// You start from 2, as 1 is not a prime number and also using 1 will cause an infinite loop
for (long i = 2L; i < input; i++) {
if (input % i == 0) {
factors.add(i);
while (input % i == 0) {
input /= i;
}
}
}
// As we always add a bigger number to the factor list, the last element is the greatest factor.
return factors.get(factors.size() - 1);
}

表示当输入是一个大素数时，程序仍然很慢，例如100000000019。为了有效地处理这种情况，最好使用有效的素数测试算法。你可以在网上搜索一下。https://en.wikipedia.org/wiki/Primality_test