Trying to find the 10,001st prime number in Java (Project Euler)

Question

I'm a java student and I just started using project euler to keep me practicing code writing and just typing in general. I'm currently stuck on the 7th question and can't find what's wrong with my code.

     public static void main(String[] args)
     {
      int num, remainder, divisor;
      boolean working = true;
      num = 2;

     for(int count = 0; count <= 10001; count++)
     {

      divisor = num - 1;
      remainder = 1;
      working = true;

      while(working != true)
      {
         remainder = 1;
         divisor = num - 1;

         while(remainder!=0)
         {
            remainder = num%divisor;

            if(divisor==1);
            {working = false;}

            divisor--;
          }
         num = num++;
      }
     }
     //System.out.println(num -1);
    }

The output I get is 1 and I can't figure out why. I am very new to coding so please dont get to frantic over my code if it's bad and inefficient LOL.

off topic, but the way you check for primes is extremely inefficient. 1st, n is highly not divisible by n-1. 2nd, you don't need to check for even divisors. 3rd, you don't even need to check for all divisors from 1 to n-1, only from 1 to sqrt(n) is enough — phuclv, Mar 03 '15 at 07:54
I did something like this once. If you hold on to the prime number you have already found, you only need to check against those. — Jake, Apr 06 '15 at 13:58

score 1 · Answer 1 · edited May 23 '17 at 12:28

The following is causing the unexpected results in your code.

    if(divisor==1);
    {working = false;} // Note: {...} is a statement block and statement
                       // blocks do not need a terminating semicolon, this
                       // can be problematic because no syntax errors will
                       // occur

Change to:

    if(divisor==1) {
        working = false;
    }

The semicolon at the end of the if statement causes the conditional to be an empty statement.

The Empty Statement

An empty statement does nothing.
EmptyStatement:
    ;
Execution of an empty statement always completes normally

More information can be found here: Semicolon at end of if statement.

score 0 · Answer 2 · answered Apr 06 '15 at 13:52

The purpose of Euler is to write code that executes as fast as possible. If I remember correctly your code should take less that one minute to find the answer.

Having said that, it should be known that even numbers (Except 2) are not prime numbers. So you can already have a running count of primes that start at 1, and increment every time you determine a prime number. Then you have another counting number that starts at 3, this counting number you'll have to perform a check to see if its prime and increment your prime count if true. Regardless, if the number is prime or not you'll want to increment this number by 2.

You should have controlling loop that runs until your prime count reaches 10001

Without giving you a direct answer in code, here's some pseudo code to get you going:

int primeCounter = 1;
int number = 3;

while (primeCounter < 10001)
{
    if (number is prime)
    {
        primeCounter++;
    }

    // Increment by 2, because we're only going to check odd numbers for prime
    number += 2;
}

// This will be your 10001st prime number
output number

score 0 · Answer 3 · answered Apr 06 '15 at 14:10

You can use these facts:

1 is not a prime.

All primes except 2 are odd.

All primes greater than 3 can be written in the form 6k+/-1.

Any number n can have only one prime factor greater than n. http://www.millersville.edu/~bikenaga/number-theory/primes/primes.html

Trying to find the 10,001st prime number in Java (Project Euler)

3 Answers3