Java程序永远以大数运行

我正在编写一个计算大数的最大素数因子的Java程序。但是我有一个关于程序复杂性的问题，我不知道是什么导致程序永远无法运行大量数据，它可以在少数情况下正常工作。Java程序永远以大数运行

我已经着手如下：

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collections; 

public class Largest_prime_factor { 

public static void main(String[] args) 
{ 
    //ArrayList primesArray = new ArrayList(); 
    ArrayList factorArray = new ArrayList(); 
    long largest = 1; 
    long number = 600851475143L ; 
    long i, j, k; 

    //the array list factorArray will have all factors of number 
    for (i = 2; i < number; i++) 
    { 
     if(number % i == 0) 
     { 
      factorArray.add(i); 

     } 
    }

这里，数组列表将有号码的所有因素。因此，我只需要获取主要数据，为此，我使用了一种方法来检查数字是否为素数，如果它不是素数，则使用以下方法将其从列表中删除：

java.util.ArrayList.remove()

因此，代码的下一个部分是如下：

for (i = 2; i < number; i++) 
     { 
     if (!isPrime(i)) 
     { 
      factorArray.remove(i); 
      System.out.println(factorArray); 
     } 
     } 


     System.out.println(Collections.max(factorArray)); 
    }

最后一行打印factorArray，这正是我要寻找的数量最多。

public static boolean isPrime(long n) 
    { 
     if(n > 2 && (n & 1) == 0) 
      return false; 
     for(int i = 3; i * i <= n; i += 2) 
      if (n % i == 0) 
       return false; 
     return true; 
    } 

}

上面的函数是我用来确定数字是否为素数，然后再将它从列表中移除的函数。

这个程序完美适用于小数字，但是尽管最后一个函数非常快，但它需要永远给出大数目的输出。起初，我用来检查一个数字是否为素数或不在第一个循环内，但它更慢。

来源

2016-10-04 Ouissal Benameur

也许这更像是一个内存问题，因为你似乎把整数放入列表中。你有没有检查你的记忆是如何演变的？和GC活动？ –

嗯，600851475143是一个非常大的数字。如果你的“较小的数字”是600851475（它本身已经是一个非常大的数字），那么对于较大的数字至少要花1000倍。你期望什么？ –

你的算法必须是O（N）或者更糟，O（N^2） – duffymo

可能的解决方案之一是只测试小于大数的素数是否会将其分开。所以我检查

 for (i=2; i < number; i++) 
     { 
      if(isPrime(i)) 
      { 
       if(number % i == 0) 
       { 
        factorArray.add(i);      
       } 
      } 
     }

所以在这里我只用素数来划分，而不是比600851475143. 较小的所有数字将但这仍然不是很快，该算法的一个完整的修改是必要的，以获得一个最佳的。

来源

2016-10-05 15:55:46

for (i = 2; i < number; i++) 
    { 
     if(number % i == 0) 
     { 
      factorArray.add(i); 

     } 
    }

对于较大的输入尺寸，您将访问最多数值。去除因素的循环相同。

long number = 600851475143L ;

这是一个很大的数字，你正在循环这两次。尝试每10,000或10万计算一次（如果i％10000印刷（i）），您就会了解它的移动速度。

来源

2016-10-04 19:22:26 briansrls

我试过使用factorArray.size（）来代替，但非素数没有从列表中删除。 –

@OuissalBenameur，我想你误解了我想说的话。这不是你在循环内所做的，你试图访问一个需要很长时间的万亿数字。没有办法“修复”这一点，除非你改进了寻找素数的算法。 – briansrls

您正在循环播放600851475143号码。

long number = 600851475143L ; 
for (i = 2; i < number; i++)

即使我们假设每个迭代需要非常非常小的时候（如小到1微秒），它仍然会需要几天的循环完成之前。

为了使程序运行得更快，您需要优化主要搜索逻辑。

减少迭代到合理数字的一种方法是循环直到数字的平方根。

for (i = 2; i < Math.sqrt(number); i++)

或

for (i = 2; i*i < number; i++)

来源

2016-10-04 19:27:50

600851475143L的素因子的计算应该不会超过一毫秒以下（用不完全低效算法）。您的代码当前缺少的主要部分：

边框应该是sqrt（数字）而不是数字。
应该在while循环中检查当前值（以防止将非主要因素添加到列表中，减小检查范围）。
最大。在找到一个因子后，价值应该降低（以及边界）到数量/因素。

进一步的改进是可能的，例如，仅在非偶数迭代（或唯一的迭代是数字既不2的倍数和3）等。

对代码审查相同的问题（link）的示例性实现：

public static long largestPrimeFactor(
     final long input) { 
    //// 
    if (input < 2) 
     throw new IllegalArgumentException(); 

    long n = input; 
    long last = 0; 
    for (; (n & 1) == 0; n >>= 1) 
     last = 2; 
    for (; n % 3 == 0; n /= 3) 
     last = 3; 
    for (long v = 5, add = 2, border = (long) Math.sqrt(n); v <= border; v += add, add ^= 6) 
     while (n % v == 0) 
      border = (long) Math.sqrt(n /= last = v); 
    return n == 1 ? last : n; 
}

来源

2016-10-04 19:49:24 Nevay

@Balkrishna Rawool建议是正确的选择。为此，我建议像这样更改迭代：for（i = 3; i < Math.sqrt（number）; i + = 2）并手动处理2。这将减少你的循环，因为除了2之外的偶数都不是主要的。

来源

2016-10-05 16:11:31

Java程序永远以大数运行

回答

相关问题