66 lines
1.0 KiB
C
66 lines
1.0 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <gmp.h>
|
|
|
|
typedef struct frac_s *frac;
|
|
struct frac_s {
|
|
int n, d;
|
|
frac next;
|
|
};
|
|
|
|
frac parse(char *s)
|
|
{
|
|
int offset = 0;
|
|
struct frac_s h = {0}, *p = &h;
|
|
|
|
while (2 == sscanf(s, "%d/%d%n", &h.n, &h.d, &offset)) {
|
|
s += offset;
|
|
p = p->next = malloc(sizeof *p);
|
|
*p = h;
|
|
p->next = 0;
|
|
}
|
|
|
|
return h.next;
|
|
}
|
|
|
|
int run(int v, char *s)
|
|
{
|
|
frac n, p = parse(s);
|
|
mpz_t val;
|
|
mpz_init_set_ui(val, v);
|
|
|
|
loop: n = p;
|
|
if (mpz_popcount(val) == 1)
|
|
gmp_printf("\n[2^%d = %Zd]", mpz_scan1(val, 0), val);
|
|
else
|
|
gmp_printf(" %Zd", val);
|
|
|
|
for (n = p; n; n = n->next) {
|
|
// assuming the fractions are not reducible
|
|
if (!mpz_divisible_ui_p(val, n->d)) continue;
|
|
|
|
mpz_divexact_ui(val, val, n->d);
|
|
mpz_mul_ui(val, val, n->n);
|
|
goto loop;
|
|
}
|
|
|
|
gmp_printf("\nhalt: %Zd has no divisors\n", val);
|
|
|
|
mpz_clear(val);
|
|
while (p) {
|
|
n = p->next;
|
|
free(p);
|
|
p = n;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
run(2, "17/91 78/85 19/51 23/38 29/33 77/29 95/23 "
|
|
"77/19 1/17 11/13 13/11 15/14 15/2 55/1");
|
|
|
|
return 0;
|
|
}
|