Java code for project euler #7 gives wrong answer

Question

This code is meant to find the 1001st prime but gives me the answer 47 which is clearly wrong.

public class problem7 {

   public static void main(String[] args) {
        int[] myarray = new int[1001];
        int j = 0;
        boolean prime = false;

        for (int i = 2;; i++) {
            for (int k = 2; k < i; k++) {
                if (i == (k - 1) && i % k != 0) {
                    prime = true;
                }

                if (i % k == 0) {
                    prime = false;
                    prime = true;
                }
                if (prime) {
                    myarray[j] = i;
                }
                if (j == 1000) {
                    System.out.println(myarray[1000]);
                    return;
                }

                j++;
            }

        }
    }
}

Any help would be greatly appreciated.

A starting point: Work on your indenting, it makes spotting errors a lot more easier ;) — Sebi, Jul 24 '15 at 12:40
Debug and check what you are putting in `myarray`. Also, have you noticed that you are doing `prime=false;` immediately followed by `prime=true`? — Tavo, Jul 24 '15 at 12:42
@Callum I improved the program in my answer because it was simply easier to write it from scratch. — Roberto Anić Banić, Jul 24 '15 at 12:51
@Roberto OP is bringing their car to a mechanic, they aren't looking to buy a new one. — CubeJockey, Jul 24 '15 at 13:07

Charnjeet Singh · Answer 1 · 2015-07-24T12:53:52.227

1

I think j++ is increment only if prime number is inserted not at all case.By using this code you will be get your 1001 Prime number

public static void main(String[] args) {
        int[] myarray = new int[1001];
        int j = 0;

        for (int i = 2;; i++) {
            boolean prime = false;
            for (int k = 2; k < i; k++) {
                if (i % k == 0) {
                    prime = true;
                }
            }
            if (!prime) {
                myarray[j] = i;
                j++;
            }
            if (j == 1001) {
                break;
            }
        }
        for (int primeNumber : myarray) {
            System.out.println(primeNumber);
        }
    }

edited Jul 24 '15 at 12:53

answered Jul 24 '15 at 12:42

Charnjeet Singh

3,056
6
35
65

Why is this upvoted and my solution is not, even though it is more efficient – Roberto Anić Banić Jul 24 '15 at 12:56
@Charnjeet why are you storing the number in the array if it is not prime rather than if it is prime? – Callum Luke Perks Jul 24 '15 at 13:08
@Callum looks like his booleans need to be switched around. If when using modular division, the result is zero, the number isn't prime. – CubeJockey Jul 24 '15 at 13:13

score 1 · Answer 2 · answered Jul 24 '15 at 12:48

Your check for prime is wrong: you cannot declare a number prime and set prime = true based on a single test. The inner loop should set prime to false, but it shouldn't reset it to true: once it's false, it's false.

The algorithm should proceed as follows:

For each i, set prime=true
Loop over potential divisors k
If a divisor such that i % k == 0 is found, set prime = false, and break the loop
If prime is still true at the end of the nested loop, add i to the list of primes.

This should give you a correct result, at which point you should consider optimizing your solution using considerations below:

If you did not find a divisor among k below or at sqrt(i), then i is prime
You do not have to try all numbers k, only the ones from the list of primes that you have discovered so far.

Roberto Anić Banić · Answer 3 · 2015-07-24T12:54:58.087

This is an implementation of dasblinkenlights algorithm!

public static void main(String args[]) {
    int[] primes = new int[1001];
    int i = 1;
    int index = 0;
    while (primes[1000] == 0) {
        i++;
        boolean skip = false;
        for (int i1 : primes) {
            if (i1 == 0)
                break;
            if (i % i1 == 0) { //checks if the number is a multiple of previous primes, if it is then it skips it
                skip = true;
                break;
            }
        }
        if (!skip) {
            if (isPrime(i)) {
                primes[index] = i;
                System.out.println(i);
                index++;
            }
        }
    }
}

static boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

An algorithm made from scratch is of no help to OP. I am sure that he could find a dozen implementations in five minutes, but he's trying to get it working by himself. — Sergey Kalinichenko, Jul 24 '15 at 12:53
Sorry, this is an implementation of your algorithm though :) — Roberto Anić Banić, Jul 24 '15 at 12:54

score 0 · Answer 4 · edited May 23 '17 at 12:06

0

The primality test you done here is kind of ambiguous. Because the general approach is, we pick any number assuming its prime, so at the beginning, prime = true. Then if there exist any factor k of input such that k < input and kthen the number is not prime, so prime = false.

I modified your code and get a result: 104743 .

Update: Here is a bit faster way to find large prime. The inner loop will iterate up to square root of i, reason: Why do we check upto the square root of a prime number to determine if it is prime?

public static void main(String[] args) {
    int[] myarray = new int[10001];
    int j = 0;
    boolean prime = true;
    int i = 2;
    while (true) {
        prime = true;
        for (int k = 2; k*k <= i; k ++) {
            if (i % k == 0) {
                prime = false;
            }
        }
        if (prime) {
            myarray[j] = i;
            if (j == 10000) {
                System.out.println(myarray[10000]);
                return;
            }
            j++;
        }  
        if(i > 4)
            i += 2;
        else
            i++;
    }
}

edited May 23 '17 at 12:06

Community

1
1

answered Jul 24 '15 at 13:12

mazhar islam

5,561
3
20
41

I got that answer myself now but its still wrong – Callum Luke Perks Jul 24 '15 at 13:16
7927 is the wrong answer – Callum Luke Perks Jul 24 '15 at 13:19
Then what is the 1001th prime? – mazhar islam Jul 24 '15 at 13:20
I dont know thats what im meant to be finding out – Callum Luke Perks Jul 24 '15 at 13:22
The 1001th prime is 7927, the 1000th prime is 7919 and the 1002th prime is 7933....sigh – mazhar islam Jul 24 '15 at 13:24
sorry i was meant to be finding the 10001st prime. ive changed the numbers of the array and the if statement that prints the number but the code just runs forever – Callum Luke Perks Jul 24 '15 at 13:34
I updated the answer increasing performance, check it now. – mazhar islam Jul 24 '15 at 14:13

Java code for project euler #7 gives wrong answer

4 Answers4