Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

結城浩さんの既約分数クイズ*1に挑戦するも、良い案を考えつかず…。結局、力ずくの方法で作りました。しかも0/1は、特別扱い。

#include

int gcd(int,int);

main()
{
  int n,i,j;

  printf("Input Number --> "); scanf("%d",&n);
   
  printf("0/1, ");
  for (i = 1 ;i <= n ; i++)
    for (j = 1 ; j <= i ; j++)
      if (gcd(i,j) == 1)
        printf("%d/%d, ",j,i);
  printf("\n");
}

int gcd(int x,int y)
{
  int tmp;

  if(x < y){
    tmp = x;
    x = y;
    y = tmp;
  }
  do {
    tmp = x % y;
    x = y;
    y = tmp;
  } while(y != 0);
  return x;
}

新たな解法