100c之45：求出分母为40的最简真分数

Table of Contents

• 1 问题
• 2 分析
• 3 程序
• 4 输出

问题

求出分母为40的最简真分数。

分析

穷举即可

程序

 1:  /**
 2:   * @file   045c.c
 3:   * @author Chaolong Zhang <emacsun@163.com>
 4:   * @date   Tue Jul  2 15:14:42 2013
 5:   * 
 6:   * @brief  求出分母为40的最简真分数。
 7:   * 
 8:   * 
 9:   */
10:  
11:  #include <stdio.h>
12:  int get_gcd( int,int );
13:  
14:  int main(int argc, char *argv[])
15:  {
16:  
17:      int i;
18:      for (i=1; i <= 39; ++i)
19:      {
20:          if (1==get_gcd( i,40 ))
21:          {
22:              printf ("%d/%d
",i,40);
23:          }
24:      }
25:      return 0;
26:  }
27:  
28:  int get_gcd ( int num1, int num2 ){
29:      int temp;
30:      if (num1<num2)
31:      {
32:          temp=num1;
33:          num1=num2;
34:          num2=temp;
35:      }
36:      while (num2!=0)
37:      {
38:          temp=num1%num2;
39:          num1=num2;
40:          num2=temp;
41:      }
42:      return num1;
43:  }

输出

1/40
3/40
7/40
9/40
11/40
13/40
17/40
19/40
21/40
23/40
27/40
29/40
31/40
33/40
37/40
39/40