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
Things I am concerned about:
- Using
POW gotostatement
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; } 
