Finding the Nth prime number in C language

Question

The code runs just fine but instead of using "for loop" to iterate upto 200000 , I think there can be a better alternative and I am having trouble finding it. I need help to optimise this solution.The time taken by this solution currently is 56ms.

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

int isPrime(long long int number)
{
    int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}
int returnNPrime(int N)
{
    int counter = 0;
    int i ;
    if(N == 1) return 2;
    for(i=3;i<200000;i+=2)
    {
        if(isPrime(i))
        {
            counter++;
            if(counter == (N-1))
             return i;
        }
    }
    return 0;
}
   int main(int argc, char *argv[]) 
   {
       printf("%d",returnNPrime(10001));
       return 0;
   }

Also search SO for "prime number", you'll find thousands of previous questions. — Barmar, Nov 23 '15 at 16:17
Hint: Rather than test against lots of integers `i` with `for (i=2; i*i<=number; i++) { if (number % i == 0) return 0;`, just test against a list of smaller primes. IOWs, keep track of them as you go. — chux - Reinstate Monica, Nov 23 '15 at 16:37
Related: [Which is the fastest algorithm to find prime numbers?](http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers) — GingerPlusPlus, Nov 23 '15 at 17:00

score 1 · Answer 1 · 2019-06-29T23:52:19.697

Don't put an arbitrary stop condition. You know that the list of primes is infinite and that the loop will eventually stop. Write it like this:

int returnNPrime (int N)
{
    int counter = 0;
    int i;
    if (N == 1) return 2;
    for (i = 3; ; i += 2)
    {
        if (isPrime(i))
        {
            counter++;
            if (counter == (N - 1))
                return i;
        }
    }
}

That being said, this solution is inefficient because you don't store previously found primes.

Try something like this:

#include <stdio.h>
#include <stdbool.h>

#define N 10001

int primes[N] = { 2, 3 };

int main ()
{
    for (int n = 2; n < N; n++) {
        for (int x = primes[n - 1] + 2; ; x += 2) {
            bool prime = true;
            for (int i = 0; i < n; i++) {
                int p = primes[i];
                if (p * p > x) {
                    break;
                }
                if (x % p == 0) {
                    prime = false;
                    break;
                }
            }
            if (prime) {
                primes[n] = x;
                break;
            }
        }
    }

    printf ("%d\n", primes[N - 1]);
}

Disagree that "This method is known as the sieve of Erathostenes." See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes — chux - Reinstate Monica, Nov 23 '15 at 17:35
I beat a friend with your algorithm, his took 10s for 2million primes, with yours it around 5s :D thx, if you know an even faster way let me know - I already googled around a lot, yours was the fastest I found (I didn't try it with special libraries). — Cold_Class, Dec 02 '17 at 14:29
Can you please tell me why we need to use # define for N and not simply initialise N as long N = 10001; — Bully Maguire, Aug 16 '19 at 01:18

score 0 · Answer 2 · answered Nov 23 '15 at 16:47

Read this paper http://cr.yp.to/bib/1996/deleglise.pdf which describes how to count the number of primes <= N in O (n^(2/3)) or so and implement the algorithm. It's substantially faster than the Eratosthenes sieve, because it doesn't actually find any primes but just counts how many there are.

Make an educated guess how large the n-th prime would be. Say the guess is x. Use the algorithm above to find out how many primes <= x there are, then use a sieve if you are close enough, or use a better guess with the information you just found and try again. Total time O (n^(2/3)).

With some decent hardware and a lot of patience this will let you find solutions up to n = 10^22 or so.

chux - Reinstate Monica · Answer 3 · 2015-11-23T18:23:48.330

OP's method consumes a lot of time with as it does not take advantage that there is no need to determine the remainder if i is not a prime.

for (i=2; i*i<=number; i++) {
  if (number % i == 0) return 0;

The Sieve_of_Eratosthenes is likely faster yet is a dramatic change from OP's code.

Suspect this code is still too slow for OP.

The follows adjust OP's code by only attempting to test against previously found primes. Also it uses pcandidate / plist[index] as part of a terminating condition. Optimized compilers often can provide this at a small cost once pcandidate % plist[index] is computed.

bool prime_test(const unsigned long *plist, unsigned long long pcandidate) {
  if (pcandidate <= 2) return pcandidate == 2;
  for (size_t index = 0; ; index++) {
    unsigned long long remainder = pcandidate % plist[index];
    if (remainder == 0) return false;
    unsigned long long quotient = pcandidate / plist[index];
    if (quotient < plist[index]) return true;
  }
  assert(0);
  return true;
}

unsigned long long prime_nth(size_t n) {
  unsigned long plist[n+1];
  plist[0] = 2;
  unsigned long long pcandidate = plist[0];
  for (size_t index = 0; index <= n; index++) {
    while (!prime_test(plist, pcandidate)) pcandidate++;
    plist[index] = (unsigned long) pcandidate;
    pcandidate++;
  }
  return plist[n];
}

A classic simplification involves only seeking new primes amongst odd numbers. Also change all math to unsigned. Left for OP.

Finding the Nth prime number in C language

3 Answers3