euler73.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <stdio.h>

int gcd(int a, int b)
{
	if (a==0)
		return b;
	else
		return gcd(b%a, a);
}

int main()
{
	int count = 0;
	for (int d = 5; d <= 12000; d++) {
		int lo = d/3+1;
		int hi = d/2;
		for (int i = lo; i <= hi; i++) {
			if (gcd(i, d)==1)
				count++;
		}
	}
	printf("%d\n", count);
}