CODEWITHSUNDEEP
javaprimes
galomoribundo
galomoribundo

Reputation: 5

Project euler exercise 10 on Java. isPrime method doesn't work in the loop

So, I'm beggining to learn programming and trying project euler with java. The problem 10 seems pretty straight forward and I thought I could use a method I used to get primes before in another problem. The thing is, the method works except when I put it in the for loop and I can't manage to see the diference between this and the other.

So this is my code 

package euler10;
public class Primesum {
    public static void main(String[] args) {
        int suma=0;

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

            if (isPrime(i) == true){
                System.out.println(i);
                suma=suma+i;
            }

        }
        System.out.println(suma);
    }

    public static boolean isPrime(int num) {
         boolean prime = false;
         long i;
        for (i=2; i < Math.sqrt(num) ; i++){
            long n = num%i;
            if (n == 0){
                prime = false;
            } else {
                prime = true;
            }
        }
        return prime;
    }
}

The isPrime method works fine out of the loop but in it it's always true. Even with even numbers it will return true, and I think those aren't very primey :)

Upvotes: 0

Views: 262

Answers (2)

user448810
user448810

Reputation: 17866

Your isPrime function is incorrect; you should delay the return true statement until after the end of the loop, when you know that all values of i do not divide num.

Also, trial division is not a good algorithm for this problem; it will be much faster to use a sieve. Here is an algorithm for summing the primes less than n using the Sieve of Eratosthenes:

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            sum := sum + p
            for i from p*p to n step p
                sieve[i] := False
    return sum

That should calculate the sum of the primes less than two million in less than a second, which is much faster than your program. If you are interested in programming with prime numbers, or if you intend to solve some of the more advanced Project Euler problems and you need some faster algorithms, I modestly recommend this essay at my blog.

Upvotes: 0

ppeterka
ppeterka

Reputation: 20726

I don't really think that there is anything to do with the loop...

However, there is a logic flaw in the code...

public static boolean isPrime(int num) {
    long i;
    for (i=2; i <= Math.sqrt(num) ; i++){
        long n = num%i;
        if (n == 0){
            return false;//found a divisor : not prime
        } 
    }
    //went through all the way to sqrt(num), and found no divisor: prime!
    return true;
}

We can stop whenever the first divisor is found, there is no need to find all of them -- that is another excercise...

Also, logically, if one wanted to use the boolean variable this way, it would have been initialised with true, and put to false, and kept at that, when a divisor is found...

Upvotes: 2

Related Questions