Testing Goldbach's Conjecture hypothesis

A book1 that I'm reading states Goldbach's conjecture as follows:

• Every even integer > 2 could be represented as a sum of two prime numbers.

• Every integer > 17 could be represented as a sum of three unique prime numbers.

• Every integer could be represented as a sum consisted of maximally six prime numbers.

• Every odd integer > 5 could be represented as a sum of three prime numbers.

• Every even integer could be represented as a difference between two prime numbers.

and then asks for a code that checks each of the five statements. Here is the code:

Goldbach.c

// upper bound of the interval we search for primes
#define MAX 100

#include 
#include 
#include 
#include "HelperArray.h"
#include "HelperPrime.h"
#include "Goldbach.h"

int main(){
    testGoldbackHypothesis();
    return 0;
}

HelperArray.h

```
#ifndef HELPERARRAY_H
#define HELPERARRAY_H

/*
Function: pi()

It returns the approximate
number of primes up to the
paramter x.
(To be used to estimate the size of the array to store primes.)
*/
long int pi(int x){
return x / (log((double) x) - 1);
}

//-----------------------------------------------------------

/*
Function: arraySize()

It returns the size of the
array that will hold primes.

x/logx always > prime number density pi(x)/x.
*/
long int arraySize(int x){
return x / log((double) x);
}
//-----------------------------------------------------------

/*
initArray();

*/
void initArray(int* primes, unsigned int size, int initValue){
unsigned int i;
for (i = 0; i < size; ++i){
primes[i] = initValue;
}
}
//-----------------------------------------------------------

/*
Function: printArray();

*/
void printArray(int* primes, unsigned int size){
unsigned int i;
int* ptrToArray = primes;
int fieldWidth = 1 + log10((double)MAX);

printf("{");
for (i = 0; i < size; ++i){
printf("%*d", fieldWidth, ptrToArray[i]);

if (i < size - 1){
// exclu

Would it be better if memory is reallocated for each prime outside of the current array size?

No. See following.


Is the current approach of checking right, are there more effective algorithms?

-
char isPrime(int n){ is barely run-time efficient. Rather than seek the next prime with ++denom, maintain a prime list and use the next one. For code using only int, could use a bit accessed array uint8_t IsPrime[(INT_MAX-1)/8 + 1] (about 512M bytes) or something smaller based on MAX, populated with Sieve of Eratosthenes. The question becomes what is "efficient". Is that speed, memory usage, code space usage, source code terseness, small stack usage? OP did not specify - assume speed.

-
A compiler may not recognize that sqrt() has no side effects and that n is constant, thus repetitively calling sqrt(). Call sqrt() once. Better to round() result too.

//while (denom <= sqrt((double) n)){
unsigned limit = (unsigned) round(sqrt(n));
while (denom <= limit) {

    ...if (n % denom == 0){
}

-
Good use of unsigned int middle = first + (last - first) / 2; to avoid overflow issues - even though (first + last) / 2; appears faster, the latter can fail.

-
Minor. Returning char rather than int/unsigned is rarely faster/less code as that type is usually the processor's "preferred" type. Return int or bool. Profile code if this optimization is in doubt.

// char isSumOfTheMostSixPrimes(...
int isSumOfTheMostSixPrimes(...

Is the code written according to the C coding standard?

-
.h files are best for define and declarations. It is non-standard practice to put code in a .h file.

-
HelperArray.h does not include needed .h files. .h files should not depend on the code that includes them to have included certain files. This file should include them.

// add for `log()`, etc.
#include 

long int pi(int x){
  return x / (log((double) x) - 1);
}

-
MAX is used, but not defined in HelperArray.h. The .h file needs to 1) not depend on other non-included declarations or defines or 2) should error intelligently.

#ifndef MAX
  #error Define `MAX` before including HelperArray.h
#endif
void printArray(int* primes, unsigned int size){
    unsigned int i;
    int* ptrToArray = primes;
    int fieldWidth = 1 + log10((double)MAX);
    ...

-
Change of type without checking range - candidate bug. Similar unqualified type changes used. The loose use of int/unsigned permeates code.

char binarySearch(unsigned int target, int* primes, unsigned int size){
    ...
    // What if `last` > INT_MAX?
    int last = size;

-
Invalid code. Likely missing )

void findPrimesTill(int* primes, unsigned int size, unsigned int upperBound{
char isSumOfThreePrimes(unsigned int target, int* primes, unsigned int size{

-
Unused variables are OK, but why have them?

char isSumOfTheMostSixPrimes(unsigned int target, int* primes, unsigned int size){
    // Unused
    unsigned int bound = 6;
    unsigned int currentSum = 0;

void Third(int* primes, unsigned int size, unsigned int upperBound){
    // Unused
    int* ptrToArray = primes;

-
Cast is OK, but not needed per the standard

// primes = (int*)malloc(sizeof(int) * size);
// Better 
primes = malloc(sizeof(int) * size);
// Even better: Avoid coding the wrong type.
primes = malloc(sizeof *primes * size);

-
Unclear why functions return type long. The C standard uses size_t as the Goldilocks type (not too narrow, not too wide) for array indexing and size.

// long int pi(int x){
// long int arraySize(int x){
size_t pi(int x){
size_t arraySize(int x){

StackExchange Code Review Q#140302, answer score: 3