pchain - primes and patterns

pchain.c

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

uint64_t *prime = NULL, pCount = 0;

uint64_t primeByN(uint64_t k, uint64_t n) {
	uint64_t j;
	for(j = 0; j < n; ++j)
		if(k % prime[j] == 0)
			return 0;
	return 1;
}

uint64_t generatePrimes(uint64_t count) {
	uint64_t i = 1, j;
	if(prime)
		free(prime);
	printf("trying to malloc %ld bytes\n", sizeof(uint64_t) * count);
	prime = malloc(sizeof(uint64_t) * count);
	if(!prime)
		return -1;

	prime[0] = 2;
	for(pCount = 1, i = 3; pCount < count; ++i) {
		if(!primeByN(i, pCount))
			continue;
		prime[pCount++] = i;
	}
	return 0;
}

uint64_t main(uint64_t argc, char **argv) {
	uint64_t i, j, k, m = 100, e = 2, ps = 1, start, w, patternWorks = 1, patcnt;
	char buf[256];
	uint32_t *pattern;

	if(argc > 1) {
		e = atoi(argv[1]);
		if(e < 1)
			e = 1;
	}

	if(generatePrimes(e)) {
		fprintf(stderr, "Couldn't generate primes!\n");
		return 1;
	}

	for(i = 0; i < e; ++i)
		ps *= prime[i];
	start = prime[e - 1]*prime[e - 1];
	printf("%ld'st extension, ps: %ld\n", e, ps);

	m = ps * 4 + start;
	printf("start, end: %ld, %ld\n", start, m);

	printf("trying to malloc %ld bytes", sizeof(uint32_t) * ps);
	printf(" (%ld)\n", (ps >> 3) >> 1);
	pattern = malloc(sizeof(uint32_t) * ps);
	if(!pattern) {
		fprintf(stderr, "Could not allocate space for pattern!\n");
		return 1;
	}

	w = sprintf(buf, "%ld", m);
	w++;
	printf("width: %d\n", w);

	if(e < 3) {
		for(i = 1; i < start; ++i) {
			if(primeByN(i, e))
				printf("%*ld", w, i);
			else
				printf("%*c", w, '*');
		}
		printf("\n\n");
	}

	patcnt = 0;
	if(e < 4)
		printf("pattern: \n");
	for(i = start; i < start + ps; ++i) {
		pattern[i - start] = primeByN(i, e);
		if(pattern[i - start])
			pattern[i - start] = ++patcnt;
		if(e < 4) {
			if(pattern[i - start])
				printf("%*ld", w, pattern[i - start]);
			else
				printf("%*c", w, ' ');
		}
	}
	if(e < 4)
		printf("\n");
	printf("ps, pc, r: %ld, %ld, %lf\n", ps, patcnt, (double)patcnt / ps *100);

	patternWorks = 1;
	for(i = start; i < m; ++i) {
		if(primeByN(i, e)) {
			if(!pattern[(i - start) % ps])
				patternWorks = 0;
			if(e < 4)
				printf("%*ld", w, i);
		} else {
			if(pattern[(i - start) % ps]) {
				printf("Pattern fails with %ld\n", i);
				patternWorks = 0;
			}
			if(e < 4)
				printf("%*c", w, '*');
		}
		if(e < 4)
			if((i - start + 1) % ps == 0)
				printf("\n");
	}

	if(patternWorks) {
		printf("pattern works!\n");
		for(i = start, j = 0; i < m; ++i) {
			if(pattern[(i - start) % ps]) {
				k = ((i - start) / ps) * patcnt + pattern[(i - start) % ps] - 1;
				if(k != j)
					patternWorks = 0;
				if(e < 4)
					printf("%*ld", w, k);
				j++;
			} else
				if(e < 4)
					printf("%*c", w, '*');
			if((e < 4) && ((i - start + 1) % ps == 0))
				printf("\n");
		}
		if(patternWorks)
			printf("indice pattern works!\n");
		else
			printf("indice pattern fails :(\n");
	} else
		printf("pattern fails :(\n");

	return 0;
}