Project Euler #7: Nth prime number

I was solving Project Euler #7 on Hackerrank but for two cases, execution time is more than 2 sec. Can you help with optimizing? I'm new to programming.

#include <stdio.h>
#include <stdbool.h>
/*INPUT EXAMPLE
2 -> no of test cases
3 -> 1st test case
5 -> 2nd test case
*/
bool IsPrime(unsigned long);

int main(){
int n;
scanf("%d", &n);

while (n != 0) {
n--;
unsigned long m, l = 2, k = 1;
scanf("%lu", &m);
if (m == 1) {
printf("%d\n", 2);
} else if(m == 2){
printf("%d\n", 3);
}else{
while(1){
if(IsPrime(6*k-1) == true){
l++;
if(l == m){
printf("%lu\n", 6*k-1);
break;
}
}
if(IsPrime(6*k+1) == true){
l++;
if(l == m){
printf("%lu\n", 6*k+1);
break;
}
}
k++;
}
}
}
}
bool IsPrime(unsigned long n){
unsigned long k;
for(k = 2; k*k <= n; k++){
if(n % k == 0){
return false;
}
}
return true;
}

• "but for two cases, execution time is more than 2 sec" --> What are those 2 cases? – chux - Reinstate Monica Dec 20 '18 at 6:38

bool IsPrime(unsigned long n){
unsigned long k;
for(k = 2; k*k <= n; k++){
if(n % k == 0){
return false;
}
}
return true;
}


A couple things off the bat.

bool isPrime(unsigned long n) {
for (unsigned long k = 2; k*k <= n; k++) {
if (n % k == 0) {
return false;
}
}

return true;
}


The general standard is to name functions either camelCase or snake_case. You used PascalCase, which is generally only used for classes and structs.

It is standard to declare loop variables that are not used outside the loop in the for declaration. That's one of the advantages of a for loop, that it allows you to do that.

But neither of those would cause performance problems. This code checks if each number from 2 to $$\\sqrt{n}\$$ is a factor of n. But you don't need to check all the numbers. You only need to check the primes. And of course, you generate a list of primes, so it's easy enough to save that and check just the primes.

Something like

bool isPrime(unsigned long n, unsigned long *primes) {
for (size_t k = 0; primes[k]*primes[k] <= n; k++) {
if (n % primes[k] == 0) {
return false;
}
}

return true;
}


Back in the calling function, you will need to add some code to handle primes.

Before the loop.

unsigned long *primes = malloc(2 * sizeof *primes);
if (!primes) {
// panic:  exit, return, or whatever seems reasonable
}
primes[0] = 2;
primes[1] = 3;

size_t length = 2;


Then take

    unsigned long m, l = 2, k = 1;
scanf("%lu", &m);
if (m == 1) {
printf("%d\n", 2);
} else if(m == 2){
printf("%d\n", 3);
}else{
while(1){


and replace it with

    size_t m;
scanf("%u", &m);
if (m > length) {
unsigned long *temp = realloc(primes, m * sizeof *primes);

if (!temp) {
free(primes);
// panic:  same way as last time
}

primes = temp;
}
m--;

unsigned long candidate = 5;
unsigned long increment = 4;
while (length <= m) {
increment = 6 - increment;


This changes the array index to size_t. This will easily support 10,000, which is the maximum m (what HackerRank calls $$\N\$$).

This also changes l to a size_t, since it has to be smaller than m and it will index an array.

This expands the primes array as necessary to handle the inputs.

I moved declarations to when they are initialized.

Your k code has some problems:

1. You do an increment, a multiplication, a subtraction, and an addition every two iterations.
2. You do two iterations of l per loop iteration.
3. You have to duplicate code to handle both the same.
4. You have to loop forever since the exit criterion is hidden.
5. You have to check two conditions before the loop to handle the first two primes.

This version of the code prepares to do

1. One iteration per loop iteration.
2. The exit criterion is in the loop declaration.
3. This does one subtraction and one addition on every iteration.
4. The code no longer needs duplicated.
5. No special cases are needed for the first two primes.
6. The solution can be printed after the loop, once rather than in four different places.
7. If some previous test looked for a later prime, we remember that and don't enter the loop at all.

The candidate variable will have the same values as 6*k-1 and 6*k+1. The increment will alternate between 2 and 4 (6-2=4 and 6-4=2). So candidate will be 5, 7, 11, 13, 17, ... Just as previously.

The rest of the loop can be

        if (isPrime(candidate, primes)) {
primes[length] = candidate;
length++;
}

candidate += increment;
}


And then

    printf("%lu\n", primes[m]);


If m was originally 1, it will now be 0 and primes[0] is 2. If m was originally 2, it will now be 1 and primes[1] is 3. So there's the special cases.

Outside the outer loop, you should

free(primes);


The big performance improvements are

1. Not recalculating the same primes for each test case.
2. Not checking for non-prime factors in isPrime.
• Thank you so much for making this more clear and way of explanation is very helpful and nice. – Aditya Singh Dec 21 '18 at 9:24

Avoid overflow, infinite loop

For large n, k*k can overflow mathematically.

When n == ULONG_MAX, for(k = 2; k*k <= n; k++) is an infinite loop.

Both of these can be solved with k*k <= n --> k <= n/k. As an added bonus, good compilers will see the nearby n/k and n%k and emit code that costs little extra as both are computed together - thus a candidate linear speed improvement

Minor: Incorrect functionality

As a point of correct-ness, IsPrime(0), IsPrime(1) should return false.

Minor: Detect limits

6*k+1 in IsPrime(6*k+1) is a potential overflow. Ensure k is not too large. This test may not be necessary given the if(l == m) ... break. One would need to test.

k++;
if (k > (ULONG_MAX - 1)/6) break;  // add


bool IsPrime(unsigned long n){
unsigned long k;
// for(k = 2; k*k <= n; k++){
for(k = 2; k <= n/k; k++){
if(n % k == 0){
return false;
}
}
// return true;
return n > 1;
}

• Thank you for helping. "k*k <= n --> k <= n/k" I like this. – Aditya Singh Dec 21 '18 at 9:27