CODEWITHSUNDEEP
java
shira
shira

Reputation: 3

euler project #10 cannot get the answer on java

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;

}

Console is not giving me any answers. Can you please hand ?

Upvotes: 0

Views: 40

Answers (1)

Pshemo
Pshemo

Reputation: 124235

Your code seems to just run slowly. You can improve its performance in few ways:

  • you don't need to test for 1 or 2 in your isPrime(long num) method since you already started looping from 2 and you are already testing this value with for (int k=2; k<num; k++){

  • don't test all numbers, but only odd ones (you already know that 4, 6, ... are not prime) so instead of 

    for (int i=2; i<2000000 ; i++)

    you can use 

    for (int i=3; i<2000000 ; i+=2)
//         ^              ^^^^ - changes

    but don't forget to initialize sum with 2 instead of 0.

  • but biggest impact on performance is avoiding testing values above sqrt(num) value in isPrime. Think of it, if some number is not prime, it means that it can be written as number = x * y. Assuming that x<=y we know that x<=sqrt(number)<=y so if we warn't able to find x there is no point in searching for y. So in isPrime instead of

    for (int k=2; k<num; k++)

    use 

    int sqrt = (int) Math.sqrt(num);  
for (int k = 2; k <= sqrt; k++)
//              ^^^^^^^^^^

    So for num like 123454321 max number of iterations wouldn't be ~123454321 but sqrt(123454321) = 11111

Upvotes: 2

Related Questions