#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

typedef unsigned long long int ULLONG;

ULLONG * getprimes(ULLONG upper) {
	ULLONG *results, *tmp, current_size = upper / 3, n = 0, i, j;
	unsigned char * pool;

	pool = malloc(sizeof(unsigned char) * upper);
	if (!pool)
		return NULL;

	memset(pool, (unsigned char) 1, upper);

	for (i = 4; i < upper; i += 2)
		pool[i] = 0;

	for (i = 0; i < upper; i++) {
		if (i % 2 == 0)
			continue;
		for (j = (i + 2) * 2; j < upper; j += (i + 2)) {
			pool[j] = 0;
		}
	}

	results = malloc(sizeof(ULLONG) * current_size + 1);
	if (!results)
		return NULL;

	for (i = 2; i < upper; i++) {
		if (pool[i]) {
			if (n >= current_size) {
				current_size *= 2;
				tmp = realloc(results, sizeof(ULLONG) * current_size);
				if (!tmp) {
					return NULL;
				}
				results = tmp;
			}
			results[n++] = i;
		}
	}
	results[n] = 0;
	return results;
}

int main(int argc, char *argv[]) {
	/*ULLONG *results;
	clock_t before, after;
	double duration;

	before = clock();
	results = getprimes(200000);
	after = clock();
	duration = (double)(after - before) / CLOCKS_PER_SEC;
	printf("%f\n", duration);
	free(results);

	before = clock();
	results = getprimes(2000000);
	after = clock();
	duration = (double)(after - before) / CLOCKS_PER_SEC;
	printf("%f\n", duration);
	free(results);

	before = clock();
	results = getprimes(200000000);
	after = clock();
	duration = (double)(after - before) / CLOCKS_PER_SEC;
	printf("%f\n", duration);
	free(results);

	/*while (*results) {
		printf("%lld ", *results);
		results++;
	}
	puts("\n");*/
	ULLONG target = 600851475143, upper = 1000;
	ULLONG *factors, *tmp;
	ULLONG *primes = getprimes(upper);
	int found = 0, n = 0, current_size = 10, i;

	factors = malloc(sizeof(unsigned char) * current_size);

	while (target > 2) {
		while (*primes) {
			if (target % *primes == 0) {
				found = 1;

				if (n >= current_size) {
					current_size *= 2;
					tmp = realloc(factors, sizeof(ULLONG) * current_size);
					if (!tmp) {
						exit(1);
					}
					factors = tmp;
				}

				printf("%lld\n", target);
				printf("%lld\n", *primes);
				factors[n++] = *primes;
				target /= *primes;
				break;
			}
			primes++;
		}

		if (!found) {
			if (target > upper) {
				upper *= 2;
				free(primes);
				primes = getprimes(upper);
			} else {
				printf("%lld\n", target);
				break;
			}
		}
	}

	/*for (i = 0; i < n; i++)
		printf("%lld\n", factors[i]);*/


}