整数{0, 1, 2, ... m-1}中有多少个数与m互素（最大公因子为1）？

euler.c

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

// return m*PI((p-1)/p);
int fEuler(int m, int p[]) {
	int a = 1, b = 1, t = m;  // a分子, b分母
	for(int i = 0; ; ++i) {
		div_t dt = div(t, p[i]);

		// 如果break, 则t为素数
		// 如果continue, 则p[i]不是其因子
		if(dt.quot < p[i]) break;
		if(dt.rem != 0) continue;

		// 从t中分解p[i]因子
		do{ t = dt.quot; dt = div(t, p[i]); }while(dt.rem == 0);

		// a计算分子, b计算分母
		a *= p[i]-1; b *= p[i];
	}

	// 如果t为素数, 则继续计算

	if(t > 1) { a *= t-1; b *= t; }

	// 为了防止溢出, 先计算m/b
	// 由于b为m的约数, 因此可以整除
	return (m/b)*a;
}

int main() {
	// 按升序排列的素数序列
	int primes[] = { 2,3,5,7,11,13,17,19,23,27,29,31 };
	fEuler(12, primes);
	return 0;
}

欧拉装载问题