# 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 <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;
}
}
printf("Prime Numbers Found so far: %d\r\n", primenum);
}
printf("THE PRIME NUMBERS ARE %d", primenum);
return 0;
}

• You probably are after a sieve of eratosthenes. – Gerrit0 Oct 20 '18 at 21:05
• 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... – Mazeryt Apr 19 '19 at 14:25

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;
*list_primes = (long*)malloc( ( (*n_primes + 4095) / 4096 ) * 4096 * sizeof(long) );
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) {
*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;
}