「既約分数クイズ」を解く（Ruby, C言語）

ここのところで結城先生の「既約分数クイズ」のことを知りました。結城先生らしい「お話」仕立てですので、是非参照して頂きたいですが、簡単にいうと

問題：正の整数Nが与えられているとき、以下の条件を満たす既約分数p/qを「すべて」求めるアルゴリズムを示してください。条件は：

p, qは整数(pは0以上で、qは1以上N以下).

gcd(p, q) = 1 (pとqの最大公約数は1).

0 <= p/q <= 1.

http://www.hyuki.com/dig/frac.html

というものです。

Ruby で解いてみたのですが、これだとあっさり解けすぎますよね。結城先生はもっと考えてごらんということだと思います。

N = 10
p (1..N).flat_map {|q| (0..q).map {|p| Rational(p, q)}}.uniq

結果。

[(0/1), (1/1), (1/2), (1/3), (2/3), (1/4), (3/4), (1/5), (2/5), (3/5), (4/5),
 (1/6), (5/6), (1/7), (2/7), (3/7), (4/7), (5/7), (6/7), (1/8), (3/8), (5/8),
 (7/8), (1/9), (2/9), (4/9), (5/9), (7/9), (8/9), (1/10), (3/10), (7/10), (9/10)]

まだあまり慣れていない C言語で書いてみましょう。
irreducible_fraction_problem.c

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

int n = 10;

int gcd(int p, int q) {
    if (!q) return p;
    return gcd(q, p % q);
}

int main () {
    int *a;
    int co = 2;
    a = malloc(sizeof(int) * n * n);
    
    a[0] = 0;
    a[1] = 1;
    
    for (int q = 1; q <= n; q++) {
        for(int p = 1; p <= q; p++) {
            if (gcd(p, q) != 1) continue;
            a[co++] = p;
            a[co++] = q;
        }
    }
    
    for (int i = 0; i <= co - 2; i += 2) {
        printf("%d/%d ", a[i], a[i + 1]);
    }
    
    printf("\n");
    free(a);
    
    return 0;
}

結果。

0/1 1/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5
1/6 5/6 1/7 2/7 3/7 4/7 5/7 6/7 1/8 3/8 5/8
7/8 1/9 2/9 4/9 5/9 7/9 8/9 1/10 3/10 7/10 9/10

　
こんなのでどうですかね。なお gcd(int p, int q) は「ユークリッドの互除法」を使って p と q の最大公約数を求めます。

なお、結城先生の「解答編」もあります。こちらもどうぞ。