1 files changed, 39 insertions, 0 deletions
diff --git a/euler71.c b/euler71.c
new file mode 100644
index 0000000..7a802c5
--- /dev/null
+++ b/euler71.c
@@ -0,0 +1,39 @@
+#include <stdio.h>
+
+int gcd(int x, int y)
+{
+	if (x == 0)
+		return y;
+	else
+		return gcd(y%x, x);
+}
+
+void imm_left(int numer, int denom, int max_denom, int *nu, int *de)
+{
+	/* nu/de < numer/denom
+	 * => nu < numer*de/denom
+	 */
+	int res_nu = 0, res_de = 1;
+	int i;
+	for (i = 2; i <= max_denom; i++) {
+		if (i == denom)
+			continue;
+		int t = numer * i / denom;
+		/* t/i > res_nu/res_de */
+		if (gcd(t, i) != 1)
+			continue;
+		if (t * res_de > i * res_nu) {
+			res_nu = t;
+			res_de = i;
+		}
+	}
+	*nu = res_nu;
+	*de = res_de;
+}
+
+int main()
+{
+	int nu, de;
+	imm_left(3, 7, 1000000, &nu, &de);
+	printf("%d/%d\n", nu, de);
+}