3
\$\begingroup\$

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 %d\r\n", 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: %d\r\n", primenum);
    }
    printf("THE PRIME NUMBERS ARE %d", primenum);
    return 0;
}
\$\endgroup\$
  • 4
    \$\begingroup\$ You probably are after a sieve of eratosthenes. \$\endgroup\$ – Gerrit0 Oct 20 '18 at 21:05
  • \$\begingroup\$ The easiest thing that you can do to improve a little bit is to nestest loop don't have to iterate to (i-1), SQRT(i) is enough or to write it more efficient way j*j < i. Than for more performance write sieve as suggested above... \$\endgroup\$ – Mazeryt Apr 19 at 14:25
1
\$\begingroup\$

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: %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, &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: %ld\n", start);
            append_prime(start, &size, &n_primes, &list_primes);
        } 
        start += 2;
    }
}


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.