More efficient ways of finding (n)th prime number

[gusty path]

Hi all,

I made the following method to find the (n)th prime number, but I was wondering what would make it more efficient/if there is a better algorithm to do so?

        int mostRecentPrime = 3;
        for (int i = 2; i < primes; i++) {
            for (int add = 2; true; add+=2) {
                boolean hasBeenBroken = false;

                int peak = (int)Math.sqrt(mostRecentPrime + add)+1;
                for (int ind = 3; ind <= peak; ind+=2) {
                    if ((mostRecentPrime + add) % ind == 0) {
                        hasBeenBroken = true;
                        break;
                    }
                }
                if (!hasBeenBroken) {
                    mostRecentPrime += add;
                    break;
                }
            }
        }
        return (primes == 1) ? 2 : mostRecentPrime;
    }```

Thanks!

[weak torrent]

Detected code, here are some useful tools:

Formatted code

public static int primeFinderStandard(int primes) {
  int mostRecentPrime = 3;
  for (int i = 2; i < primes; i++) {
    for (int add = 2; true; add += 2) {
      boolean hasBeenBroken = false;
      int peak = (int ) Math.sqrt(mostRecentPrime + add) + 1;
      for (int ind = 3; ind <= peak; ind += 2) {
        if ((mostRecentPrime + add) % ind == 0) {
          hasBeenBroken = true;
          break ;
        }
      }
      if (!hasBeenBroken) {
        mostRecentPrime += add;
        break ;
      }
    }
  }
  return (primes == 1) ? 2 : mostRecentPrime;
}

<@&987246746478460948> please have a look, thanks.

[weak torrent]

While you are waiting for getting help, here are some tips to improve your experience:

Code is much easier to read if posted with syntax highlighting and proper formatting.

If nobody is calling back, that usually means that your question was not well asked and hence nobody feels confident enough answering. Try to use your time to elaborate, provide details, context, more code, examples and maybe some screenshots. With enough info, someone knows the answer for sure.

Don't forget to close your thread using the command </help-thread close:1027500463647621170> when your question has been answered, thanks.

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

There are several more efficient algorithms for finding the nth prime number. Here are a few popular ones:

1. Sieve of Eratosthenes: This is one of the most efficient methods for finding prime numbers up to a certain limit. It works by iteratively marking the multiples of each prime, starting from 2, as composite (not prime). The remaining unmarked numbers are primes. By using this sieve, you can generate a list of primes up to a certain limit and then easily find the nth prime number.

2. Sieve of Atkin: Similar to the Sieve of Eratosthenes, this algorithm also generates a list of primes up to a certain limit. It is more optimized and faster than the Sieve of Eratosthenes for larger limits.

3. Miller-Rabin Primality Test: This probabilistic algorithm determines if a number is likely to be prime or composite with high accuracy. It can be used to quickly test large numbers for primality.

4. Prime Number Theorem: This theorem provides an estimation for the number of primes less than or equal to a given number n. By using this theorem, you can estimate an upper bound for the nth prime and then use other algorithms like trial division or sieves to find it efficiently.

These algorithms are more efficient than simply checking divisibility by all numbers up to n-1, which is what your method might be doing. Implementing any of these algorithms should significantly improve the efficiency of finding the nth prime number.