java - 最大的质因数程序需要 aaaages - Java

Question

所以这是 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 分钟并且还在继续。显然，我在这里采用了错误的方法(是的，该程序确实 有效，我用较小的数字进行了尝试)。谁能建议一种不那么详尽的方法？

Answer 1

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);
}