/****************************************************************************/
/* Función fi de Euler, número de enteros menores que uno dado              */
/* y primos con él.                                                         */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

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

typedef unsigned long ulong;
ulong fi(ulong n);

int main(int argc, char *argv[])
{
	int i;
	ulong n;

	if (argc==1) {
		printf("Uso: %s n1 [n2] ...[nk]\n",argv[0]);
		printf("calcula la función fi de Euler.\n");
		return 1;
	}
	for (i=1; i<argc; i++) {
		n= (ulong)atol(argv[i]);
		printf("fi(%ld)= %ld\n",n,fi(n));
	}
	
	return 0;
}

/*
 * Función fi de Euler, número de enteros menores que uno dado
 * y primos con él. Suponiendo que n = p1^e1 . p2^e2 ... pk^ek 
 * entonces   fi(n)= n.(1-1/p1).(1-1/p2)...(1-1/pk)
 */

ulong fi(ulong n)
{
	ulong p;
	float f;

	f=n;
	if ((float)n/2 == n/2) {
		f *= (1-1.0/2);
		while ((float)n/2 == n/2) n/=2;
	}
	
	p=3;
	while (p*p <= n) {
		if ((float)n/p == n/p) {
			f *= (1-1.0/p);
			while ((float)n/p == n/p) n/=p;
		}
		p += 2;
	}
	if (n!=1) f *= (1-1.0/n);

	return (ulong)f;
}