素数与最大公约数GCD：
题目一：
#include <climits>
#include <cmath>
#include <iostream>
using namespace std;
#include<vector>
#include<algorithm>
int main() {int n;cin>>n;vector<vector<int>>v(n,vector<int>(2));//数组队中最小值int m=INT_MAX;for(int i=0;i<n;i++){cin>>v[i][0]>>v[i][1];m=min(m,min(v[i][0],v[i][1]));}vector<int>s;vector<int>tmp(sqrt(pow(10,9)*2),1);for(int i=2;i<tmp.size();i++)//i为素数值，将合适的i插入数组{if(tmp[i]==1)s.push_back(i);for(int j=i*i;j<tmp.size();j+=i){tmp[j]=0;}}auto it=lower_bound(s.begin(), s.end(),m);//找到素数中大于等于m的值if(it==s.end())return -1;int i;while(it>=s.begin()){for(i=0;i<n;i++){if(v[i][0]%*it!=0&&v[i][1]%*it!=0)break;}if(i==n)break;it--;}cout<< (i==n?*it:-1)<<endl;return 0;
}
// 64 位输出请用 printf("%lld")解题思路：
首先得到范围内的所有素数集合，由输入的数对得到其中最小的值，在素数数组中查找大于等于最小值的素数，由该素数判断是否可以整除每组数对中至少一个的数据，全部满足则输出该素数，不满足则素数减小一个继续判断，直到到达结束判断的条件输出-1；
题目二：
#include <iostream>
#include <string>
using namespace std;
#include<vector>int main()
{vector<int>s(sqrt(2 * pow(10, 5)), 1);vector<int>ss;//a、b最大2*10^9 for (int i = 2; i < s.size(); i++){if (s[i])ss.push_back(i);for (int j = i * i; j < s.size(); j += i){s[j] = 0;}}// for (auto it : ss)cout << it << " ";int n;cin >> n;vector<int>v(n);for (int i = 0; i < n; i++){cin >> v[i];}for (int i = 0; i < v.size(); i++){for (int j = 0; j < ss.size(); j++){if (v[i] % ss[j] == 0){cout << (v[i] / ss[j]) << endl;break;}}}return 0;
}解题思路：
由输入数据的最大值最小得到素数的范围，求得该范围上所有素数后，由原输入的整数，整除最小素数所得到的为最大公约数。