/******************************************************************************
Online C Compiler.
Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <math.h>
#include <stdbool.h>
#include "stdlib.h"
#include "string.h"
#include <stdio.h>
#define INITIAL_TABLE_SIZE 9973
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)
{
sieve_of_eratosthenes((primes.size << 1) + 1);
}
int i;
for (i = x; i < primes.size; i++)
{
if (primes.array[i] == true && primes.array[i - 2] == true)
{
return i;
}
}
goto resize;
}
int main()
{
printf("%d\n", next_twin_prime(10));
int i;
for (i = 0; i < primes.size; i++) {
printf("[%d] = %s\n", i, primes.array[i] ? "prime" : "not a prime");
}
return 0;
}
