C语言奇葩之求最大公约数、最小公倍数、分解质因数的做法(C语言)




奇葩的请求最大公约数、最小公倍数、分解质因数的做法(C语言)

  1 /*
  2 最奇葩的求最大公约数与最小公倍数
  3 create by laog 
  4 time 2017年7月27日12:23:14
  5 */
  6 
  7 //两个数的最大公约数
  8 //两个数的最小公倍数
  9 //将一个正整数分解质因数  --和 2.3.5取余
 10 
 11 #include <stdio.h>
 12 
 13 int main1()
 14 {
 15     // 3,4
 16     //20
 17     int v;
 18     scanf("%d", v);
 19     int a = 20;
 20     int start = 1;
 21     int end = a;
 22     int result = 0;
 23     for (i = start; i <= end; i++)
 24     {
 25         //求出一个数中的最大质数
 26         if (a % i == 0 && i % 2 != 0)
 27         {
 28             result = i;
 29         }
 30     }
 31     printf(result);
 32 }
 33 //最奇葩得求最大公约数和最小公倍数
 34 int main2()
 35 {
 36     //最大公约数
 37     //输入
 38     int a = 20;
 39     int b = 25;
 40     //声明循环的标志
 41     int start = 1;
 42     int end = a < b ? a : b;
 43     //声明接收最大公约数的遍历
 44     int maxGongyue = 0;
 45     for (int i = start; i < end; i++)
 46     {
 47         if (a % i == 0 && b % i == 0)
 48         {
 49             maxGongyue = i;
 50         }
 51     }
 52     printf(maxGongyue);
 53     return 0;
 54 }
 55 //求最小公倍数
 56 int main3()
 57 {
 58     //最小公倍数
 59     //输入
 60     int a = 30;
 61     int b = 50;
 62     //声明循环标志
 63     int start = a * b;
 64     int end = a > b ? a : b;
 65     //声明接收最小公倍数的变量
 66     int minGongbei = 0;
 67     for (int i = start; i >= end; i--)
 68     {
 69         if (i % a == 0 && i % b == 0)
 70         {
 71             minGongbei = i;
 72         }
 73     }
 74     printf(minGongbei);
 75     return 0;
 76 }
 77 
 78 //判断一个数是不是质数
 79 int panDuanZhiShu(int s)
 80 {
 81     int sign = 1;
 82     for (int i = 2; i <= process - 1; i++)
 83     {
 84         if (s % i == 0)
 85         {
 86             sign = 0;
 87         }
 88     }
 89     return sign;
 90 }
 91 
 92 int main4()
 93 {
 94     //分解质因数
 95     //输入
 96     int a = 90;
 97     int start1 = 1;
 98     int end1 = a;
 99     int process = a;
100     while (1)
101     {
102         for (int i = start1; i < end; i++)
103         {
104             if (panDuanZhiShu(i))
105             {
106                 if (process % i == 0)
107                 {
108                     printf(i);
109                     process = process / i;
110                     break;
111                 }
112             }
113         }
114         //当process=1得时候跳出循环
115         if (process == 1)
116         {
117             break;
118         }
119     }
120 }
121 /**
122 下面这种做法是比较正常的
123 利用算法
124 */
125 /*
126 有两整数a和b:
127 
128 ① a%b得余数c
129 
130 ② 若c=0,则b即为两数的最大公约数
131 
132 ③ 若c≠0,则a=b,b=c,再回去执行①
133 
134 例如求27和15的最大公约数过程为:
135 
136 27÷15 余1215÷12余312÷3余0因此,3即为最大公约数
137 */
138 void main()   /*  辗转相除法求最大公约数 */   
139 {   
140    int m, n, a, b, t, c;  
141    printf("Input two integer numbers:\n");  
142    scanf("%d%d", &a, &b);  
143    m=a;   n=b;  
144    while(b!=0)  /* 余数不为0,继续相除,直到余数为0 */   
145    { c=a%b; a=b;  b=c;}  
146    printf("The largest common divisor:%d\n", a);  
147    printf("The least common multiple:%d\n", m*n/a);  
148 }
149