tgt.c

#include <inttypes.h>
#include <stdlib.h>
#include <stdio.h>

#include "eratos.h"

#define PRIME_LIMIT    (uint64_t)1e5
#define ALLOWED_CHAINS (uint64_t)30e7
#define ARRAY_ELEMS    (uint64_t)40

uint64_t *primes = NULL;
size_t prime_count = 0;

size_t chain_count = 0;
size_t longest_chain = 0; 

struct array
{
	uint64_t *data;
	size_t len;
};
typedef struct array array;

int uint64_cmp(const void* a, const void* b)
{
	uint64_t x = *(uint64_t*)a;
	uint64_t y = *(uint64_t*)b;
	return x - y;	
}

array** getChains(uint64_t max)
{
	array** chains = calloc(ALLOWED_CHAINS, sizeof(array*));
	if(!chains)
		exit(1);

	chains[0] = calloc(1, sizeof(array));
	chains[0]->data = calloc(ARRAY_ELEMS, sizeof(uint64_t));
	chains[0]->len = 0;
	for(size_t i = 0; i < prime_count - 1 && primes[i] <= max; ++i)
	{
		uint64_t diff = primes[i + 1] - primes[i] + 1;
		if(bsearch(&diff, primes, prime_count, sizeof(uint64_t), uint64_cmp))
		{
			array* tmp = chains[chain_count];
			if(tmp->len < ARRAY_ELEMS)
			{
				tmp->data[tmp->len] = primes[i];
				++tmp->len;
			}
			else
			{
				printf("Too many links in one chain! "
					">= %lu links in chain #%lu, starting at %lu\n",
					(unsigned long)tmp->len, (unsigned long)chain_count, (unsigned long)tmp->data[0]);
				longest_chain = tmp->len + 1;
				++chain_count;
				chains[chain_count] = calloc(1, sizeof(array));
				chains[chain_count]->data = calloc(ARRAY_ELEMS, sizeof(uint64_t));
				chains[chain_count]->len = 0;
			}
		}
		else
		{
			if(chain_count > ALLOWED_CHAINS)
			{
				printf("Too many chains! >= %lu chains\n", (unsigned long)chain_count);
				return chains;
			}
			array* tmp = chains[chain_count];
			tmp->data = realloc(tmp->data, sizeof(tmp->data[0]) * tmp->len);
			if(tmp->len > longest_chain)
				longest_chain = tmp->len;
			if(tmp->len != 0)
				++chain_count;
			chains[chain_count] = calloc(1, sizeof(array));
			chains[chain_count]->data = calloc(ARRAY_ELEMS, sizeof(uint64_t));
			chains[chain_count]->len = 0;
		}
	}
	chains = realloc(chains, (chain_count + 1) * sizeof(chains[0]));
	chains[chain_count] = 0;
	return chains;
}

void printChains(array** chains)
{
	for(size_t i = 0; i < ALLOWED_CHAINS && chains[i]; ++i)
	{
		array* tmp = chains[i];
		if(tmp->len == 0)
			continue;
		printf("%lu [", (unsigned long)tmp->len);
		size_t k;
		for(k = 0; k + 1 < tmp->len && k < ARRAY_ELEMS; ++k)
		{
			printf("%" PRIu64 ", ", tmp->data[k]);
		}
		printf("%" PRIu64 "]\n", tmp->data[k]);
	}
}

int main()
{
	prime_count = eratos(PRIME_LIMIT, &primes);
	array** chains = getChains(PRIME_LIMIT);
	
	printChains(chains);

	printf("Chain count: %lu\n", (unsigned long)chain_count);
	printf("Longest chain: %lu\n", (unsigned long)longest_chain);

	for(int i = 0; chains[i] != 0; ++i)
	{
		free(chains[i]->data);
		free(chains[i]);
	}
	free(chains);
	return 0;
}