Program that finds prime numbers in a specific range 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 &lt;stdio.h&gt;

#define START 190000000 
#define END 200000000

int main()
{
    int primenum = 0, i = 0, j = 0, c = 0;
    for (i = START; i &lt;= END; i++)
    {
        printf("EXMINING %d\r\n", i);
        c = 2;
        for (j = 2; j &lt;= i-1; j++)
        {
            if (i%j == 0)
            {   c=1;
                break;
            }
        }
        if (c == 2) primenum = primenum + 1;
        printf("Prime Numbers Found so far: %d\r\n", primenum);
    }
    printf("THE PRIME NUMBERS ARE %d", primenum);
    return 0;
}
I combine here all the above and look up tables.


Use the threshold of sqrt(test_prime) to shrink the range to be tested, as said by @Gaurav.
Increase the prime number to be tested by 2, as said by @1201ProgramAlarm.
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).
Load/Save the look up table for future executions.
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 &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;math.h&gt;
#include &lt;string.h&gt;

#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 &lt;= max) {
        if (test % prime == 0)
            return 0;
        if (++index &gt;= 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 &gt; 2) {
            (*list_primes)[(*n_primes)++] = 2;
        } else {
            return *n_primes;
        }

        if (threshold &gt; 3) {
            (*list_primes)[(*n_primes)++] = 3;
        } else {
            return *n_primes;
        }

        if (threshold &gt; 5) {
            (*list_primes)[(*n_primes)++] = 5;
        } else {
            return *n_primes;
        }

        if (threshold &gt; 7) {
            (*list_primes)[(*n_primes)++] = 7;
        } else {
            return *n_primes;
        }
    }


    long prime = (*list_primes)[(*n_primes)-1] + 2;
    while (prime &lt; threshold) {
        //printf("Examining number: %ld / %ld      \r", prime, threshold);
        if (is_prime(prime, *n_primes, *list_primes)) {
            //printf("\nPrime number found: %ld\n", 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, &amp;size, &amp;n_primes, &amp;list_primes);

    if ((start &amp; 0x01) == 0)
        start++;
    while (start &lt; end) {
        printf("Examining number: %ld       \r", start);
        if (is_prime(start, n_primes, list_primes)) {
            printf("\nPrime number found: %ld\n", start);
            append_prime(start, &amp;size, &amp;n_primes, &amp;list_primes);
        } 
        start += 2;
    }
}


int main()
{
    find_primes_interval(START, END);
    return 0;
}