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