我试图创建一个Java程序来计算任何长数的最大素数（在这种情况下为600851475143）。当我尝试运行它时，该程序将无限期编译，而不会产生警告或结果。我知道可能有更简单/更直接的方法来解决此问题，但是我很好奇为什么这个方法似乎行不通。我不认为逻辑本身是错误的，可能的错误可能是我对长变量的使用（我以前从未经常使用过它们）。
我已经声明了一些变量，只要允许它们将空间增加到'long'大小
public class LargestPrimeFactor {
public static void main(String []args){
long num = 600851475143L;
long largestPrimeFactor = 0L;
boolean flag = false;
//Find all factors of num
for (long i = 2L; i <= num/2; i++){
//If a number i is a factor of num
if((num % i) == 0){
//Find if the factor i is a prime number (only divisible by 1 and by itself)
//by checking whether dividing it by any number results in an integer
for (long j = 2L; j <= i/2; j++){
if (i/j == 0){
flag = true;
}
if (!flag){
if (i > largestPrimeFactor){
largestPrimeFactor = i;
}
}
}
}
}
System.out.print(largestPrimeFactor);
}
}
当然，您的代码不会无限运行。只是您的代码效率不高，因此打印结果花费的时间太长。如果使用较小的数字进行测试或使用有效的代码，则将得到结果。
下面给出的是一种有效的方法：
public class Main {
public static void main(String[] args) {
long num = 600851475143L;
long divisor = 2, largestPrimeFactor;
while (num != 0) {
if (num % divisor != 0) {
divisor++;
} else {
largestPrimeFactor = num;
num /= divisor;
if (num == 1) {
System.out.println("The largest prime factor: " + largestPrimeFactor);
break;
}
}
}
}
}
输出：
The largest prime factor: 6857
您的代码还存在以下逻辑问题：
flag变量已在外部循环外部声明，这意味着一旦成为false，就永远不会将其重置为true。 i / j == 0，您需要检查i % j == 0。break之后立即i % j == 0内部循环。 largestPrimeFactor的检查需要从内部循环移动到外部循环。顺便说一下，对素数的测试也不有效。除了检查数字的一半外，检查数字的平方根就足够了。有关更多详细信息，请检查https://en.wikipedia.org/wiki/Primality_test。下面给出的是用于素数测试的有效代码：
static boolean isPrime(int number) {
boolean prime = true;
if (number == 0 || number == 1 || number == -1)
return false;
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
prime = false;
break;
}
}
return prime;
}
这并未专门解决算法中的所有问题，但可以提供一些指导。您给定的数字应该很快分解，因为其主要因子的大小非常接近。这样可以加快速度，因为发现其他因素后，目标数量减少得更快。
请考虑以下示例。第一个值是您的值，第二个是更大的值，第三个是最小的值（最后一个原因）。
输出如下所示：实际上，这是您的电话号码。 adding部分是一个新因子，continuing部分是除以该因子后剩下的部分，还有待进一步分解的部分。括号中的值是找到给定数字的因素。
Checking: 600851475143
Adding 71, continuing with 8462696833
Adding 839, continuing with 10086647
Adding 1471, continuing with 6857
Adding 6857, continuing with 1
[71, 839, 1471, 6857]
结果是前两个数字分解非常快。第三次将花费很长时间。那是因为它是素数，并且使用此方法，我必须生成直至该值的所有素数才能验证这一事实。因此，不是唯一因素（双关语）是大小，而是主要因素的相对大小。
这里是测试步骤。
for (long test : new long[] { 600851475143L,
14385829455476874L, 300851475157L }) {
System.out.println();
System.out.println("Checking: " + test);
List<Long> factors = findFactors(test);
System.out.println(factors);
}
static private int lastReturnedPrimeIdx = 0;
static private List<Long> primes = new ArrayList<>(
List.of(2L, 3L));
// find all prime factors in a supplied number.
public static List<Long> findFactors(long n) {
List<Long> factors = new ArrayList<>();
lastReturnedPrimeIdx = 0;
while (n > 1) {
long p = nextPrime();
while (n % p == 0) {
factors.add(p);
n /= p;
System.out.println("Adding " + p
+ ", continuing with " + n);
}
}
return factors;
}
// Get the next prime. This memoizes the primes as they are computed.
// Future tests on the same run can thus take advantage of the cached values.
// Prime are computed in bulk.
private static long nextPrime() {
if (lastReturnedPrimeIdx < primes.size()) {
return primes.get(lastReturnedPrimeIdx++);
}
// start where the it left off last time.
long candidate = primes
.get(lastReturnedPrimeIdx - 1);
long max = primes.size() + 1_000; // generate 1000 more primes.
outer:
while (primes.size() < max) {
candidate += 2;
long bound = (long)Math.sqrt(candidate);
for (int i = 0; i < primes.size(); i++) {
long p = primes.get(i);
if (candidate % p == 0 ) {
continue outer;
}
if (p > bound) {
break;
}
}
primes.add(candidate);
}
return (primes.get(lastReturnedPrimeIdx++));
}
}
最后一点：我建议您通过以下方式计算未来的候选素数：
primes直到候选者的平方根。另一个选项是Sieve of Eratosthenes
看起来您的程序编译正常，但是陷入了无限（或很长）循环中如果将System.out.println("program started");放在main方法的开头，则可能会显示它。
此外，如果您降低long num，也会看到方法完成。
编辑：您有两个嵌套的for循环。第一个执行num / 2次，另一个执行（num / 2）/ 2。
如果我没记错的话，它将循环（num ^ 2）/ 8次。对于long num = 600851475143L;来说很多。因此，您的应用被卡住了4.51 × 10^22次以上]
查找因素是一项非常需要计算的操作。