Codeforces Round #632 (Div. 2) F. Kate and imperfection(贪心&素数筛)

题目传送门

题意:求给定[1,n]的序列,长度为从2到n的序列中gcd(a,b)(a不等于b)的最大值。

思路:根据贪心思想,显然先将最大公约数为1的放入集合(即素数),再将最大公约数为2的放入集合(比如2),再将最大公约数为3的放入集合(比如6)依次类推,显然当放入一个合数时,它的所有因数都在集合中(它的因数都被筛过),因此此时的答案为它的最大因子。利用埃氏筛从小到大遍历不断更新最大因子即可。

AC代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int>v(n+1,1);
	for(int i=2;i<=n;i++)//埃氏筛
		for(int j=2*i;j<=n;j+=i)//对加入每个合数时,此时的值为它的最大因子。 
			v[j]=i;
	sort(v.begin(),v.end());
	for(int i=2;i<=n;i++) printf(i==n?"%d\n":"%d ",v[i]);
	return 0;
}