TransWikia.com

C: Sieve of Eratosthenes and next twin prime

Code Review Asked on October 27, 2021

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;
}

One Answer

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.

Answered by AJNeufeld on October 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP