牛客网每日刷题(4)

1. GCD

1.1. 题目

链接：https://ac.nowcoder.com/acm/contest/9667/D
来源：牛客网

题目描述
牛牛有一个集合 S 包含 1 至 n 所有的数， 现在他想让你找一个最小的数 k ， 使得在 S 中任意找一个子集 T ， T 集合中的元素个数为 k ， T 中都存在两个数 x ， y ，且 gcd(x,y) > 1 . 如果找不到满足题目条件的 k ，就输出 -1 ,否则输出 k .

gcd(x, y) 为求 x y 的最大公约数。

输入描述:
一个数字 n ( 1 ≤ n ≤ 1e5 )

输出描述:
如果找不到满足题目条件的 k ，就输出 -1 ,否则输出 k .

1.2. 样例输入&&样例输出

样例1

3

-1

样例2

6

5

1.3. 思路

数学题，当n<4时 找不到输出-1当n>4时，根据抽屉原则，
把这个区间之内的所有的质数全部放到子集 T 中，
再添加一个非 1 并且没有出现过的数字，必定存在两个数的 gcd 不为 1 。
所以素数筛这个区间的素数，最后的结果加 2 即可。

1.4. AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 3e6+5;
#define INF 2e9
int f[maxn];
typedef long long ll;
#define sc(n) scanf("%d",&n)

bool isprime(int x){
    for(int i=2;i<sqrt(x);i++){
        if(x%i==0)return 0;
    }
    return 1;
}

int main(){
    int n;cin>>n;
    if(n<4)cout<<-1;
    else{
        int cnt=0;
        for(int i=2;i<=n;i++){
            if(!f[i])cnt++;
            for(int j=i+i;j<=n;j+=i){
                f[j]=1;
            }
        }
        cout<<cnt+2;
    }
    system("pause");
    return 0;
}