最大的素因子程序需要aaaages – Java

所以这是项目Euler的问题3。 对于那些不知道的人,我必须找出最大的素数因子600851475143.我有以下代码:

import java.lang.Math; // 600851475143 public class LargestPrimeFactor { public static void main(String[] stuff) { long num = getLong("What number do you want to analyse? "); long[] primes = primeGenerator(num); long result = 0; for(int i = 0; i < primes.length; i++) { boolean modulo2 = num % primes[i] == 0; if(modulo2) { result = primes[i]; } } System.out.println(result); } public static long[] primeGenerator(long limit) { int aindex = 0; long[] ps = new long[primeCount(limit)]; for(long i = 2; i < limit + 1; i++) { if(primeCheck(i)) { ps[aindex] = i; aindex++; } } return ps; } public static boolean primeCheck(long num) { boolean r = false; if(num == 2 || num == 3) { return true; } else if(num == 1) { return false; } for(long i = 2; i < Math.sqrt(num); i++) { boolean modulo = num % i == 0; if(modulo) { r = false; break; } else if(Math.sqrt(num) < i + 1 && !modulo) { r = true; break; } } return r; } public static int primeCount(long limit) { int count = 0; if(limit == 1 || limit == 2) { return 0; } for(long i = 2; i <= limit; i++) { if(primeCheck(i)) { count++; } } return count; } public static long getLong(String prompt) { System.out.print(prompt + " "); long mrlong = input.nextLong(); input.nextLine(); return mrlong; } } 

但是当我用小于600851475143的东西(很多)测试程序时,比如100000000,那么程序需要时间 – 实际上,到目前为止,100000000已经用了20分钟而且还在继续。 我显然在这里得到了错误的方法(是的,程序确实有效,我用较小的数字试了一下)。 任何人都可以提出一种不那么详尽的方式吗?

试试这个 ..

 public class LargestPrimeFactor{ public static int largestPrimeFactor(long number) { int i; for (i = 2; i <= number; i++) { if (number % i == 0) { number /= i; i--; } } return i; } /* change according to ur requirement. public static long getLong(String prompt) { System.out.print(prompt + " "); long mrlong = input.nextLong(); input.nextLine(); return mrlong; } */ public static void main(String[] args) { //long num = getLong("What number do you want to analyse? "); System.out.println(largestPrimeFactor(600851475143l)); } } 
 public static void main(String[] args) { long number = 600851475143L; long highestPrime = -1; for (long i = 2; i <= number; ++i) { if (number % i == 0) { highestPrime = i; number /= i; --i; } } System.out.println(highestPrime); } 

公共类LargestPrimeFactor {

 public static boolean isPrime(long num){ int count = 0; for(long i = 1; i<=num/2 ; i++){ if(num % i==0){ count++; } } if(count==1){ return true; } return false; } public static String largestPrimeFactor(long num){ String factor = "none"; for(long i = 2; i<= num/2 ; i++){ if(num % i==0 && isPrime(i)){ factor = Long.toString(i); } } return factor; } public static void main(String[] args) { System.out.println(largestPrimeFactor(13195)); } 

}

我在Project Euler上做了几十个挑战。 有些问题可以用蛮力解决(他们建议不要这样做),但其他问题需要“开箱即用”的思考。 你无法通过蛮力解决问题。

网上有很多帮助可以引导您朝着正确的方向前进,例如: http : //thetaoishere.blogspot.com.au/2008/05/largest-prime-factor-of-number.html

数可以具有的素因子的数量总是小于该数的sqrt,因此不需要遍历数n来找到其最大的素因子。

看到这段代码。

  public class LargestPrimeFactor { public static void main(String[] args) { Scanner sc=new Scanner(System.in); long num=sc.nextLong(); if(num>0 && num<=2) { System.out.println("largest prime is:-" + num); System.exit(0); } int i=((Double)Math.sqrt(num)).intValue(); int j=3; int x=0; //used for looping through the j value which can also be a prime. for eg in case of 100 we might get 9 as a divisor. we need to make sure divisor is also a prime number. int z=0; //same function as j but for divisor int y=3; int max=2; //divisor is divisible boolean flag=false; //we found prime factors boolean found=false; while(x<=i) { y=3; flag=false; if(num % j ==0) { if(j>max) { for(z=0;z 

更改

for(long i = 2; i <= limit; i++)

 // add the one for rounding errors in the sqrt function new_limit = sqrt(limit) + 1; // all even numbers are not prime for(long i = 3; i <= new_limit; i+=2) { ... } 

以1,000,000为例,而不是迭代1,000,000次,只需要进行大约500次迭代。