Java程序永远需要大量运行
发布时间:2020-12-15 04:36:09 所属栏目:Java 来源:网络整理
导读:我正在编写一个 Java程序来计算大数的最大素数因子.但我对程序的复杂性有一个问题,我不知道是什么导致程序永远运行大数字,它适用于小数字. 我进行如下: import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;public class Lar
我正在编写一个
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; } } 上面的函数是我用来确定数字是否是素数之前从列表中删除它. 这个程序适用于小数字,但是为大数字提供输出需要永远,尽管最后一个函数非常快. 解决方法
您正在循环超过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++) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |