I'm kinda new to programming, and as a solution to an exercise, I made a program to find prime numbers in a range. It runs just right for small ranges of numbers, but for this exercise we are given a high range of nums, and it just takes much time to finish examining. Any suggestions how can I make it faster?

#include <stdio.h>



#define START 190000000 

#define END 200000000



int main()

{

    int primenum = 0, i = 0, j = 0, c = 0;

    for (i = START; i <= END; i++)

    {

        printf("EXMINING %drn", i);

        c = 2;

        for (j = 2; j <= i-1; j++)

        {

            if (i%j == 0)

            {   c=1;

                break;

            }

        }

        if (c == 2) primenum = primenum + 1;

        printf("Prime Numbers Found so far: %drn", primenum);

    }

    printf("THE PRIME NUMBERS ARE %d", primenum);

    return 0;

}

I combine here all the above and look up tables.

1. Use the threshold of sqrt(test_prime) to shrink the range to be tested, as said by @Gaurav.


2. Increase the prime number to be tested by 2, as said by @1201ProgramAlarm.


3. Use a look up tables to check only with the prime numbers we have detected until that moment (we remove a lot of unnecessary checks).


4. Load/Save the look up table for future executions.


5. Use SIMD instrinsics (not implemented in this solution), so that you can check 4 primes into the look up table at the same time.

My tests took about 4 minutes without pre-calculated lookup table, and about 30 seconds using pre-calculated lookup table.

The code here

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <string.h>



#define START 190000000 

#define END 200000000



int is_prime(long test, long n_primes, long* list_primes) {

    long max = sqrt(test);

    long index = 1;

    long prime = list_primes[index];

    while (prime <= max) {

        if (test % prime == 0)

            return 0;

        if (++index >= n_primes)

           break;

        prime = list_primes[index];

    }

    return 1;

}





void append_prime(long prime, long* size, long* n_primes, long** list_primes) {

    if (*n_primes == *size) {

        *list_primes = (long*)realloc(*list_primes, (*size + 4096)*sizeof(long));

        *size += 1024;

    }

    (*list_primes)[*n_primes] = prime;

    *n_primes += 1;

}





int load_from_disk(long* size, long* n_primes, long** list_primes) {

    FILE* f = fopen("primes.dat", "rb");

    if (f == NULL)

        return 0;

    fread(size, sizeof(long), 1, f);

    fread(n_primes, sizeof(long), 1, f);

    *list_primes = (long*)malloc( ( (*n_primes + 4095) / 4096 ) * 4096 * sizeof(long) );

    fread(*list_primes, sizeof(long), *n_primes, f);

    fclose(f);

    f = NULL;

    return 1;

}





int save_to_disk(long* size, long* n_primes, long** list_primes) {

    FILE* f = fopen("primes.dat", "w");

    if (f == NULL)

        return 0;

    fwrite(size, sizeof(long), 1, f);

    fwrite(n_primes, sizeof(long), 1, f);

    fwrite(*list_primes, sizeof(long), *n_primes, f);

    fclose(f);

    f = NULL;

    return 1;

}





long find_primes_until(long threshold, long* size, long* n_primes, long** list_primes) {

    if (!load_from_disk(size, n_primes, list_primes)) {

        *size = 4096;

        *n_primes = 0;

        *list_primes = (long*)malloc((*size) * sizeof(long));

        memset(*list_primes, 0, (*size) * sizeof(long));



        if (threshold > 2) {

            (*list_primes)[(*n_primes)++] = 2;

        } else {

            return *n_primes;

        }



        if (threshold > 3) {

            (*list_primes)[(*n_primes)++] = 3;

        } else {

            return *n_primes;

        }



        if (threshold > 5) {

            (*list_primes)[(*n_primes)++] = 5;

        } else {

            return *n_primes;

        }



        if (threshold > 7) {

            (*list_primes)[(*n_primes)++] = 7;

        } else {

            return *n_primes;

        }

    }





    long prime = (*list_primes)[(*n_primes)-1] + 2;

    while (prime < threshold) {

        //printf("Examining number: %ld / %ld      r", prime, threshold);

        if (is_prime(prime, *n_primes, *list_primes)) {

            //printf("nPrime number found: %ldn", prime);

            append_prime(prime, size, n_primes, list_primes);

        }

        prime += 2;

    }

    save_to_disk(size, n_primes, list_primes);



    return *n_primes;

}





void find_primes_interval(long start, long end)

{

    long* list_primes = NULL;

    long  size = 0;

    long  n_primes = 0;



    find_primes_until(start, &size, &n_primes, &list_primes);



    if ((start & 0x01) == 0)

        start++;

    while (start < end) {

        printf("Examining number: %ld       r", start);

        if (is_prime(start, n_primes, list_primes)) {

            printf("nPrime number found: %ldn", start);

            append_prime(start, &size, &n_primes, &list_primes);

        } 

        start += 2;

    }

}





int main()

{

    find_primes_interval(START, END);

    return 0;

}