# C: Sieve of Eratosthenes and next twin prime

I am wondering if I can get some feedback for my implementation of "Sieve of Eratosthenes" and twin prime. I followed this pseudocode.

Few notes:

• I added MAX(primes.size << 1, (x << 1) + 1) to make I resize the table large enough to find the next twin prime.
• Use a struct to keep track of the size of the dynamic array

• Using POW
• goto statement

Only playground to test the code: https://www.onlinegdb.com/HydogHGxw

Thank you.

#include "prime.h"
#include <math.h>
#include <stdbool.h>
#include "stdlib.h"
#include "string.h"

#define INITIAL_TABLE_SIZE 9973
#define MAX(x, y) (((x) > (y)) ? (x) : (y))

typedef struct
{
bool *array;
unsigned int size
} PRIMES;

PRIMES primes = {NULL, 0};

/**
* Create a boolean array "prime[0..n]" and initialize
* all entries it as true. A value in prime[i] will
* finally be false if i is Not a prime, else true.
*/
void sieve_of_eratosthenes(int n)
{
if (primes.array != NULL)
{
free(primes.array);
}

primes.size = n;
primes.array = malloc(n * sizeof(bool));
memset(primes.array, true, n * sizeof(bool));

primes.array[0] = false;
primes.array[1] = false;

int i, j;
for (i = 2; i < (int)sqrt((double)n); i++)
{
// If primes[p] is not changed, then it is a prime
if (primes.array[i] == true)
{
// Update all multiples of p
for (j = (int)pow((int)i, 2); j < n; j += i)
{
primes.array[j] = false;
}
}
}
}

/**
* Return the next prime greater than parameter such that -2 is also a prime
*/
int next_twin_prime(int x)
{
if (primes.array == NULL)
{
sieve_of_eratosthenes(INITIAL_TABLE_SIZE);
}

resize:

if (x >= primes.size)
{
int new_size = MAX(primes.size << 1, (x << 1) + 1);

sieve_of_eratosthenes(new_size);
}

int i;
for (i = x; i < primes.size; i++)
{
if (primes.array[i] == true && primes.array[i - 2] == true)
{
return i;
}
}

goto resize;
}


The use of pow(i, 2) is unnecessary; you should simply use i*i.

The goto statement is also unnecessary. You could wrap the code in while(true) { ... }.

## Other Concerns

The cast (int) i is also unnecessary, as i is already an integer. Perhaps you meant to cast to a double?

Computing sqrt(n) in the for loop termination condition is inefficient; you should compute it once outside the loop.

The primes global should probably be declared static, so it isn’t visible outside the module. Then the “helper” function sieve_of_eratosthenes should also be static.

Your overflow and resizing of the sieve does not preserve any previous work; perhaps you could use realloc?

No twin prime pair would ever be even, so you could optimize the sieve to skip even numbers.

This statement memset(primes.array, true, n * sizeof(bool)); is questionable. If a bool is larger than 1 byte, then what are you storing in the array? For instance, if each sizeof(bool) == 2, then primes.array[0] would be 0x0101, which is not the same as true.