UVa 10179 - Irreducable Basic Fractions

// UVa 10179 - Irreducable Basic Fractions
// Euler's totient function

#include <iostream>
#include <math.h>
#include <string.h>
#include <vector>
using namespace std;

#define mx 31622
#define integer unsigned long long int

int main() {
	// prime sieve
	bool isprime[mx + 1];
	memset(isprime, true, sizeof(isprime));
	for (integer i = 4; i <= mx; i += 2)
		isprime[i] = false;
	vector<integer> prime;
	prime.push_back(2);
	for (integer i = 3; i <= mx; i += 2)
		if (isprime[i]) {
			prime.push_back(i);
			for (integer j = i * i; j <= mx; j += (i << 1))
				isprime[j] = false;
		}
	//
	integer n;
	while ((cin >> n) && n) {
		// euler's totient function
		double prod = n;
		for (int i = 0; i < prime.size() && prime[i] <= n; i++) {
			if (n % prime[i] == 0) {
				do
					n /= prime[i];
				while (n % prime[i] == 0);
				prod *= (1.0 - 1.0 / prime[i]);
			}
		}
		if (n > 1)
			prod *= (1.0 - 1.0 / n);
		// output
		cout << ((integer) (prod)) << endl;
	}
	return 0;
}