项目Euler＃3永远使用Java
Project Euler上的问题＃3是：
13195的主要因素是5,7,13和29。
600851475143的最大主要因素是什么？
我的解决方案永远。 我认为我得到了正确的实施; 然而，当用大数字进行测试时，我无法看到结果。 它永远运行。 我想知道我的算法是否有问题：
public class LargestPrimeFactor3 { public static void main(String[] args) { long start, end, totalTime; long num = 600851475143L; long pFactor = 0; start = System.currentTimeMillis(); for(int i = 2; i < num; i++) { if(isPrime(i)) { if(num % i == 0) { pFactor = i; } } } end = System.currentTimeMillis(); totalTime = end - start; System.out.println(pFactor + " Time: "+totalTime); } static boolean isPrime(long n) { for(int i = 2; i < n; i++) { if(n % i == 0) { return false; } } return true; } } 虽然不是Java，但我认为您可能会做出以下建议。 基本上，需要通过仅测试奇数除数和直到数字的平方根来减少迭代。 这是一种蛮力方法，可以在C＃中实现即时结果。
static bool OddIsPrime (long oddvalue) // test an odd >= 3 { // Only test odd divisors. for (long i = 3; i <= Math.Sqrt(oddvalue); i += 2) { if (value % i == 0) return false; } return true; } static void Main(string[] args) { long max = 600851475143; // an odd value long maxFactor = 0; // Only test odd divisors of MAX. Limit search to Square Root of MAX. for (long i = 3; i <= Math.Sqrt(max); i += 2) { if (max % i == 0) { if (OddIsPrime(i)) // i is odd { maxFactor = i; } } } Console.WriteLine(maxFactor.ToString()); Console.ReadLine(); }
您应该根据找到的每个因素进行划分。 然后，当我们按升序计算可能的除数时，没有必要测试它们的素数（任何因此找到的除数不能是复数，它的因子将被分开）。 然后你的代码变成：
class LargestPrimeFactor4 { public static void main(String[] args) { long start, end, totalTime; long num = 600851475143L; // odd value is not divided by any even long pFactor = 1L; start = System.currentTimeMillis(); for(long i = 3L; i <= num / i; ) { if( num % i == 0 ) { pFactor = i; num = num / i; } else { i += 2; } } if( pFactor < num ) { pFactor = num; } end = System.currentTimeMillis(); totalTime = end - start; System.out.println( pFactor + " Time: " + totalTime); } }
public HashSet distinctPrimeFactors(int n) //insane fast prime factor generator { HashSet factors = new HashSet (); int lastres = n; if (n==1) { factors.add(1); return factors; } while (true) { if (lastres==1) break; int c = 2; while (true) { if (lastres%c==0) break; c++; } factors.add(c); lastres/=c; } return factors; }
如果要快速生成数字的不同素因子，请使用此方法，使每次迭代的数字变小。 您可以将int更改为long，它应该适合您。
这是通过试验分区进行整数分解的伪代码：
define factors(n) z = 2 while (z * z <= n) if (n % z == 0) output z n /= z else z++ output n
理解这一点的最简单方法是通过一个例子。 考虑n = 13195的因式分解。最初z = 2，但将13195除以2会得到1的余数，所以else子句设置z = 3并且我们循环。 现在n不能被3或4整除，但是当z = 5时，将13195除以5时的余数为零，因此输出5并将13195除以5使得n = 2639并且z = 5不变。 现在新的n = 2639不能被5或6整除，但是可以被7整除，所以输出7并设置n = 2639/7 = 377.现在我们继续z = 7，剩下的就是余数，就像除法一样由8，9和10,11和12，但377/13 = 29没有余数，所以输出13并设置n = 29.此时z = 13，z * z = 169，这是大于29，所以29是素数并且是13195的最终因子，因此输出29.完全因子分解为5 * 7 * 13 * 29 = 13195。
有更好的算法可以使用试验除法对整数进行因式分解，甚至更强大的算法可以使用除了试验除法之外的技术对整数进行因式分解，但上面显示的算法可以帮助您入门，并且足以用于Project Euler＃3。 当你准备好了更多时，请看这里 。
提高性能的两件事：
static boolean isPrime(long n) { for(int i = 2; i <= sqrt(n); i++) // if n = a * b, then either a or b must be <= sqrt(n). { if(n % i == 0) { return false; } } return true; }
现在为主循环
for(int i = num; i > 1; i--) // your interested in the biggest, so search from high to low until you have a match { if(num % i == 0 && isPrime(i)) // check for num % i == 0 is faster, so do this first { pFactor = i; break; // break if you have a factor, since you've searched from the top } }
在这里仍然有一些可以改进的东西，但那是你找到的。 想想修改num 。 与项目欧拉玩得开心:)
你可以只是对数字进行分解，然后最大的素数就是答案：
import java.util.ArrayList; import java.util.Collections; public class PrimeFactorization { /* returns true if parameter n is a prime number, false if composite or neither */ public static boolean isPrime(long n) { if (n < 2) return false; else if (n == 2) return true; for (int i = 2; i < Math.pow(n, 0.5) + 1; i++) if (n % i == 0) return false; return true; } /* returns smallest factor of parameter n */ public static long findSmallestFactor(long n) { int factor = 2; // start at lowest possible factor while (n % factor != 0) { // go until factor is a factor factor++; // test the next factor } return factor; } /* reduces the parameter n into a product of only prime numbers and returns a list of those prime number factors */ public static ArrayList primeFactorization(long n) { ArrayList primes = new ArrayList (); // list of prime factors in the prime factorization long largestFactor = n / findSmallestFactor(n); long i = 2; while (i <= largestFactor) { // for all possible prime factors // (2 - largest factor of the number being reduced) if (isPrime(i) && n % i == 0) { // if this value is prime and the number is divisible by it primes.add(i); // add that prime factor to the list n /= i; // divide out that prime factor from the number // to start reducing the new number largestFactor /= i; // divide out that prime factor // from the largest factor to get the largest // factor of the new number i = 2; // reset the prime factor test } else { i++; // increment the factor test } } primes.add(n); // add the last prime number that could not be factored Collections.sort(primes); return primes; } }
然后像这样调用它：
ArrayList primes = PrimeFactorization.primeFactorization(600851475143L); System.out.println(primes.get(primes.size() - 1));
整个过程只需几毫秒。
这不是完美的解决方案，但它适用于600851475143。
public static void main(String[] args) { long number= 600851475143L; int rootOfNumber = (int)Math.sqrt(number)+10; for(int i = rootOfNumber; i > 2; i--) { if(number % i == 0) { if(psudoprime(i)) { System.out.println(i); break; } } } } public static boolean psudoprime(int num) { for(int i = 2; i < 100; i++) { if(num % i == 0) { return false; } } return true; }
public class LargestPrimeFactor { static boolean isPrime(long n){ for(long i=2;i<=n/2;i++){ if(n%i==0){ return false; } } return true; } static long LargestPrimeFact(long n){ long largestPrime=0; for(long i=2;i
资料来源： http ： //crispylogs.com/project-euler-problem-3-solution/
这一个完美！
public class Puzzle3 { public static void main(String ar[]) { Long i=new Long("1"); Long p=new Long("600851475143"); Long f=new Long("1"); while(p>=i) { if(p%i==0) { f=i; p=p/i; int x=1; i=(long)x; } i=i+2; } System.out.println(f); }
}