euler项目#10无法在java上得到答案

Question

public static void main(String[] args) {
    long sum=0;

    problemTen a= new problemTen();
    for (int i=2; i<2000000 ; i++){
        if(a.isPrime(i))
            sum += i;

    }
    System.out.println(sum);



}

public boolean isPrime(long num){
    if(num==1) return false;
    if(num==2) return true;
    for (int k=2; k<num; k++){
        if(num%k ==0) return false;
    }
    return true;

}

控制台没有给我任何答案。你能用手吗？

Answer 1

您的代码似乎运行得很慢。您可以通过以下几种方式改进它的性能：

• 您不需要在您的1方法中测试isPrime(long num)或2，因为您已经从2开始循环，并且您已经在用for (int k=2; k<num; k++){测试这个值
• 不要测试所有的数字，而只测试奇数(你已经知道4，6，.不是素数)所以 for (int i=2；i<2000000；i++) 您可以使用 用于(int i=3；i<2000000；i+=2) // ^-更改 但是，不要忘记使用2而不是0初始化0。
• 但是，对性能的最大影响是避免在isPrime中测试高于isPrime值的值。想想看，如果某个数字不是素数，就意味着它可以写成number = x * y。假设x<=sqrt(number)<=y是x<=y，那么如果我们找不到x，就没有必要搜索y。所以在isPrime而不是 for (int k=2；k使用 int sqrt = (int) Math.sqrt(num)；for (int k= 2；k <= sqrt；k++) // ^因此，对于num类123454321，最大迭代次数将不是~123454321，而是sqrt(123454321) = 11111。