Codeforces Round #632 (Div. 2) F. Kate and imperfection（思维+贪心+素数筛）

题意：一个集合的 imperfection 定义为：这个集合中任意一对数的 gcd 中的最大 gcd（e.g.{1，2，3，6} 的 imperfection 为 3），现在给定一个原始集合长度为n，集合内的元素为（1~n），让找出特定长度 k 的子集，是得它是这个长度中的子集中 imperfection 最小的，输出这个最小值

思路：贪心，首先先将最大公约数为1的放入集合（即素数），再将最大公约数为2的放入集合（比如2，4），再将最大公约数为3的放入集合（比如6，9）依次类推，可以发现当放入一个合数时，它的所有因数都在集合中(它的因数都被筛过），此时的答案为它的最大因子。利用埃氏筛从小到大遍历不断维护更新最大因子即可

AC_Code:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 3e5+10;
 5 const int inf = 0x3f3f3f3f;
 6 #define rep(i,first,second) for(ll i=first;i<=second;i++)
 7 #define dep(i,first,second) for(ll i=first;i>=second;i--)
 8 
 9 int n;
10 int main(){
11     cin>>n;
12     vector<int>v(n+1,1);
13     rep(i,2,n){//埃氏筛
14         for(int j=2*i;j<=n;j+=i){
15             v[j]=i;
16         }
17     }
18     sort(v.begin(),v.end());
19     rep(i,2,n){
20         if( i==2 ) cout<<v[i];
21         else cout<<' '<<v[i];
22     }
23     cout<<'
';
24     return 0;
25 }