ProjectEuler/c/0003.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

struct primes_da {
	uint64_t *data;
	uint64_t size;
	uint64_t cap;
};


bool isprime(struct primes_da *primes, uint64_t n);
void primes_fill(struct primes_da *primes);

int
main(int argc, const char **argv)
{
	uint64_t res = 0;
	uint64_t i = 0;
	uint64_t target = 600851475143;
	uint64_t prime = 0;
	ldiv_t dm = {0};
	struct primes_da primes = {0};

	primes.cap = 256;
	primes.data = calloc(primes.cap, sizeof(uint64_t));
	primes.size = 0;

	primes_fill(&primes);

	while ( i < target ) {
		if ( i >= primes.size ) {
			primes.cap = primes.cap * 2;
			primes.data = realloc(primes.data,
					      primes.cap * sizeof(uint64_t));
			primes_fill(&primes);
		}
		prime = primes.data[i];
		dm = ldiv((int64_t)target, (int64_t)prime);
		if ( isprime(&primes, (uint64_t)dm.quot) ) {
			if ( prime > res ) {
				res = prime;
			}
		}
		if ( dm.rem != 0 ) {
			++i;
			continue;
		}
		if ( prime > res ) {
			res = prime;
		}
		target = (uint64_t)dm.quot;
	}

	printf("Result = %ld!\n", res);
	(void) argc; (void) argv;
	return 0;
}

bool
isprime(struct primes_da *primes, uint64_t n)
{
	uint64_t i = 0;
	if ( (n & 1) == 0 ) {
		return false;
	}

	if ( primes != NULL ) {
		if ( n < primes->data[primes->size-1] ) {
			for ( i = 0; i < primes->size; ++i ) {
				if ( n == primes->data[i] ) {
					return true;
				}
			}
			return false;
		}
	}

	for ( i = 2; i < n; ++i ) {
		if ( (n % i) == 0 ) {
			return false;
		}
	}
	return true;
}

void
primes_fill(struct primes_da *primes)
{
	uint64_t i = primes->size;
	if ( i == 0 ) {
		i = 2;
	}
	for ( ; primes->size < primes->cap; ++i ) {
		if ( isprime(NULL, i) ) {
			primes->data[primes->size++] = i;
		}
	}
}