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

int is_prime(int n) {
	if(n <= 1) {
		return -1;
	}

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

	return 1;
}

float euler_f(int n) {
	int last_prime = 0, i = 2;
	float e = n;

	while(n != 1) {
		if(n % i == 0 && is_prime(i)) {
			if(last_prime != i) {
				e = e * (1.0 - 1.0 / i);
				last_prime = i;
			}
			n = n / i;
		} else {
			i += 1;
		}
	}

	return e;
}

int main(int argn, char ** argv) {
	int number = atoi(argv[1]);
	int bound  = atoi(argv[2]);
	int i;
	printf("Numbers that match: ");
	for(i = 1; i < bound; i ++)  {
		if(euler_f(i) == number) {
			printf("%d, ", i);
		}
	}
	printf("\n");
	return 0;
}


// The Euler function φ: N → N is a mapping associating to each positive integer n the number φ(n), which is the number of integers that are relatively prime to n.
// For example φ(6) = 2 because only 1 and 5 are relatively prime to 6.
// The formula for finding such a number is the following:
// 	given n, φ(n) = n * (1 - 1 / P1) * ... * (1 - 1 / Pi), P1 to Pi being the set of prim factors of n