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

#include "primElem.h"

void clearRow(int number, char *row) {
	if (number == 0)
		return;
	row[0] = 0;
	clearRow(number - 1, &row[1]);
}

int checkRow(int number, char *row) {
	if (number == 0)
		return 1;
	if (row[0] == 0) {
		//printf("-%i", number);
		return 0;
	}
	return checkRow(number - 1, &row[1]);
}

int powModForPrimElem(int a, int n, int mod, char *row) {
	int retval;
	if (n == 0)
		return 1;
	retval = (a * powModForPrimElem(a, n-1, mod, row)) % mod;
	//printf("%i^%i mod %i = %i\n", a, n, mod, retval);
	row[retval] = 1;
	return retval;
}

int primElement(int mod, int start) {
	char *row = alloca(sizeof(char) * mod);
	int i;
	for (i = start; i < mod; i++) {
		clearRow(mod, row);
		powModForPrimElem(i, mod - 1, mod, row);
		if (checkRow(mod - 1, &row[1]))
			break;
	}
	return i;
}

#ifdef NON_LIBRARY

int main(int argc, char **argv) {
	int number;
	//int *row;
	int i;
	int c;
	if (argc < 2) {
		fprintf(stderr, "[%s] Syntax: %s [number]\n", argv[0], argv[0]);
		exit(-1);
	}

	/*
	row = alloca(sizeof(int) * number);
	for (i = 1; i < number; i++) {
		printf("trying: %i...", i);
		clearRow(number, row);
		powMod(i, number - 1, number, row);
		if (checkRow(number - 1, &row[1])) {
			printf(" primElem!");
		} else {
		}
		printf("\n");
	}
	*/
	for (c = 1; c < argc; c++) {
		number = atoi(argv[c]);
		printf("Primitieve Elementen van %i: ", number);
		i = 1;
		while (i < number) {
			i = primElement(number, i);
			if (i < number)
				printf(" %i", i);
			i++;
		}
		printf("\n");
	}
	return 0;
}

#endif