From f54a9727f09e0ffe52f4123ed3f9e0cd67ddcff9 Mon Sep 17 00:00:00 2001 From: Iru Cai Date: Tue, 29 May 2018 21:05:53 +0800 Subject: 69, 71, 81 --- euler71.c | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 euler71.c (limited to 'euler71.c') 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 + +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); +} -- cgit v1.2.3