Cfrtjryk

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can
see that the 6th prime is 13.

What is the 10 001st prime number?

How can I make this more efficient and cleaner?

public class Problem7 {



    public static void main(String args) {

        // a prime factor is something that can divide by only 1 and itself evenly

        int counter = 0;

        int primeNum = 0;



        for (int num = 2; num < 10000000; num++) {

            boolean isPrime = true;

            for (int factor = 2; factor < num; factor++) {



                if (num % factor == 0) {

                    isPrime = false;

                    break;

                }

            }

            if (isPrime) {

                primeNum = num;

                counter++;

            }

            if (counter == 10001) {

                break;

            }

        }

        System.out.println(primeNum);

    }

}

Magic numbers

You should use constants instead of some hard coded values. Adding a meaningful name to your constants improves the readability of the code.

Loop conditions

Instead of picking a huge value for the for loop, you have better alternatives for the end condition of the loop.

This option is similar and makes the intention of the code a little more clear:

for (int num = 2; num < Integer.MAX_VALUE; num++) {

You want to break the code when you find the n prime number, so you can use this in the condition:

for (int num = 2; counter < 10001; num++) {

To improve the performance, you can add a few changes to the code:

Don't test even numbers. All even numbers are divisible by 2.

for (int factor = 3; factor < num; factor = factor + 2) {

Don't test if the number is divisible by non-prime numbers. e.g. You don't need to test if a number is divisible by 6 (2x3), you already test with 2 and 3.

You can keep the prime numbers found so far and reuse them if you need to execute the code multiple times.

Making the code a little more generic, it could be:

public class PrimeFinder {

    // Uses long instead of int to be able to find bigger primes

    List<Long> primes = new ArrayList<>();



    public static void main(String args) {

        PrimeFinder finder = new PrimeFinder();

        System.out.println(finder.getPrime(10001));



    }



    public PrimeFinder() {

        // Start with 2 and 3 in the list to make it easy to iterate over odd numbers.

        primes.add(2l);

        primes.add(3l);

    }



    public long getPrime(int position) {

        // If this was calculated previously, return the result.

        if (position <= primes.size()) {

            return primes.get(position - 1);

        }



        // Start the iteration after the last prime in the list. Skipping even numbers.

        int count = primes.size();

        for (long i = primes.get(primes.size() - 1) + 2; count < position; i = i + 2) {

            if (isPrime(i)) {

                count++;

            }

        }   

        return primes.get(primes.size() - 1);

    }



    private boolean isPrime(long number) {

        for (long prime : primes) {

            if (number % prime == 0) {

                return false;

            }

        }

        primes.add(number);

        return true;

    }

}

More efficient... look at Sieve of Eratosthenes for a huge speed up. I'm ignoring it for now, as it comes again and again.

for (int num = 2; num < 10000000; num++) {

The condition num < 10000000 is plain wrong. It works, but makes no sense. If the requirements change, the limit may be too small. Just drop it. Or better, replace it by counter < 10001 (nobody says, that you have to test num, any condition is allowed).

You surely know that 4, 6, 8, ... are no primes, so you can skip them. Iterate over odd numbers only and set the initial value of counter equal to one (accounting for the skipped prime 2). So you get something like

for (int num = 3; counter < 10001; num += 2) {

This hardly helped the speed, but doing the same thing in

for (int factor = 2; factor < num; factor++) {

surely helps. You only have to deal with odd num, so you test only odd factors.

Observe that for each factor, also num / factor is a factor and the smaller of the two is no bigger than the square root of num. So you can use

int limit = (int) Math.sqrt(num);

for (int factor = 3; factor <= limit; factor += 2) {

        if (isPrime) {

            primeNum = num;

            counter++;

        }

This looks a bit strange. It works, but you assign primeNum just in case it'll be needed. A rather useless variable as num would do, too.

Even for such a rather trivial tasks you should use methods. Write small methods and let each of them do just one thing. Especially, never mix user input or output with computation as this makes the code perfectly non-reusable. Try to write methods like

boolean isPrime(int num);

int nextPrimeAbove(int num);

int nthPrime(int n);

package task;



import java.math.BigInteger;



/* By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see

that the 6th prime is 13.



What is the 10 001st prime number?

*/

public class Prime {

    public static int findPrime(int range) {

        int i = 3;

        int count = 1;

        int res = 0;

        while (count != range) {

            BigInteger b = new BigInteger(i + "");

            if (b.isProbablePrime(1)) {

                count++;

                res = i;

            }

            i += 2;

        }

        return res;

    }



    public static void main(String args) {

        System.out.println(findPrime(10001));

    }

}

/* Output : 104243 */