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:
MAX(primes.size << 1, (x << 1) + 1)
to make I resize the table large enough to find the next twin prime.Things I am concerned about:
POW
goto
statementOnly 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) { ... }
.
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP