4
\$\begingroup\$

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
  • 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;
}
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Your Concerns

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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