用埃拉托色尼筛算法求两个数最大公约数C++的实现

 1 #include "stdafx.h"
 2 #include "iostream"
 3 #include <algorithm>
 4 #include <vector>
 5 
 6 //使用埃氏筛选法求最大公约数
 7 void sort(int m, int n) ;
 8 
 9 int main()
10 {
11 int a, b;
12 
13 for (int i = 0; i < 3; )
14 {
15 std::cout << "请输入两个数" << "\n";
16 std::cin >> a >> b;
17 
18 std::cout << "\n";
19 
20 sort(a, b);
21 i++;
22 if (i == 3)
23 {
24 std::cout << "是否继续,输入n退出或输入任意数继续\n";
25 char confirm;
26 std::cin >> confirm;
27 if (confirm != 'n')
28 i = 0;
29 }
30 }
31 system("pause");
32 return 0;
33 }
34 
35 void sort(int m, int n)
36 {
37 int imax, imin;
38 int sq;
39 
40 //取最大最小值
41 imax = std::max(m, n);
42 imin = std::min(m, n);
43 
44 //构造辅助数组
45 bool *isTrue = new bool[imin];
46 sq = sqrt(imin) + 1;
47 
48 //数组初始化
49 for (int i = 2; i <= imin; i++)
50 {
51 isTrue[i] = true;
52 
53 }
54 
55 //数组中TRUE为质数
56 for (int i = 2; i <= sq; i++)
57 {
58 if (isTrue[i])
59 {
60 for (int j = 2; j <= imin; j++)
61 {
62 if (j%i == 0 && i != j)
63 isTrue[j] = false;
64 }
65 }
66 }
67 
68 //打印质数
69 for (int i = 2; i <= imin; i++)
70 {
71 if (isTrue[i])
72 std::cout << "质数:" << i << std::endl;
73 }
74 std::cout << "\n\n";
75 //求两数最大公约数
76 int s = 1;//最大公约数
77 for (int i = 2; i <= imin; )
78 {
79 //std::cout << i;
80 if (isTrue[i])
81 {
82 if (imax%i == 0 && imin%i == 0)
83 {
84 imax /= i;
85 imin /= i;
86 s *= i;
87 //std::cout <<imax<<imin<< i;
88 }
89 else ++i;
90 }
91 else ++i;
92 }
93 
94 std::cout <<m<<"和"<<n<<"的最大公约数为" <<s << "\n";
95 }

简单的小程序，练习笔记