我怎样才能减少我的函数运行时间

Question

在这段代码中，我想解决 Project Euler 问题 #3。 objective就是求最大的素数。我的代码运行正常，但在运行时出现问题。我怎样才能减少运行时间？谁能提出任何建议？

public class Euler3 {

    //https://www.hackerrank.com/contests/projecteuler/challenges/euler003
    public static void main(String[] args) {

        long[] inputs = readInputs();

        for (int i = 0; i < inputs.length; i++) {

            System.out.println(findBiggestPrime(inputs[i]));
        }

    }

    public static boolean isPrime(long num) {

        if (num == 2)
            return true;

        for (long i = 3; i * i <= num; i += 2) {

            if (num % i == 0)
                return false;

        }

        return true;
    }

    private static long[] readInputs() {

        Scanner scanner = new Scanner(System.in);
        int inputQuantities = scanner.nextInt();

        long[] inputs = new long[inputQuantities];

        for (int i = 0; i < inputQuantities; i++) {

            inputs[i] = scanner.nextLong();
        }
        return inputs;
    }

    private static long findBiggestPrime(long number) {

        long biggestPrime = 0;

        if (number % 2 == 0) {

            number = number / 2;
            biggestPrime = 2;
        }

        if (number == 2) 
            return 2;



        for (int i = 3; i <= number; i += 2) {

            if (number % i != 0)  
            continue;

            if(!isPrime(i)) 
                continue;;

                biggestPrime = i;
                number = number / biggestPrime;

        }


        return biggestPrime;
    }


}

Answer 1

线条

if(!isPrime(i)) 
     continue;

会减慢你的算法，不应该存在。

你在算法中遇到的任何因素都应该自动成为素数。例如，您不应该遇到因数 15，因为您应该已经遇到过 3 和 5 并同时除以它们。

要完成这项工作，您不应该只做 number = number / biggestPrime;。当你遇到一个因素时，你应该一直除以它，直到它不再成为数字。这样你就清除了权力。

Answer 2

isPrime() 效率极低。这是一个跟踪 HashSet 中已确认倍数的版本。我不知道您使用的#'s 的数量级是多少。这似乎在 ~100K 范围内对我的机器有一定的效率。

private static final Set<Long> multiples = new HashSet<>();

private static boolean isPrime(long l) {
    if(l%2==0 && l>2)
        return false;
    if(multiples.contains(l))
        return false;
    double r = Math.sqrt(l);
    for(long i=3;i<=r;++i) {
        for (long j = i * 2; j <= l; j += i) {
            multiples.add(j);
            if (j == l) {
                return false;
            }
        }
    }
    return true;
}

我怎样才能减少我的函数运行时间

How can I reduce my function runtime

java

performance