洛谷T779196 模拟赛2 T1 互质划分（coprime）

T779196 模拟赛2 T1 互质划分（coprime）

题目描述

正整数 \(a\) 和 \(b\) 的最大公因数是满足 \(a,b\) 同时是 \(d\) 的倍数的最大的正整数 \(d\)。
而正整数 \(a\) 和 \(b\) 互质，指的是 \(a\) 和 \(b\) 的最大公因数为 \(1\)。
给定一个正整数 \(n\)，求最少把 \(1\sim n\) 共 \(n\) 个正整数分成多少堆，才能使得每一堆里面每两个数都互质。
输入格式

一行一个正整数 \(n\)。
输出格式

一行一个整数表示最少的堆数。
输入输出样例 #1

输入 #1

1. 2

复制代码

输出 #1

1. 1

复制代码

输入输出样例 #2

输入 #2

1. 5

复制代码

输出 #2

1. 2

复制代码

说明/提示

样例 1 解释

一种合法方案是把 \(1,2\) 放在同一堆，则 \(1,2\) 的最大公因数是 \(1\)，它们互质，所以满足要求。
样例 2 解释

一种合法方案是把 \(1,2,5\) 放在同一堆，\(3,4\) 放在同一堆，可以验证是满足要求的。
数据规模与约定

对于 \(50\%\) 的数据，\(1\leq n\leq 10\)。
对于 \(70\%\) 的数据，\(1\leq n\leq 10^3\)。
对于 \(100\%\) 的数据，\(1\leq n\leq 10^{18}\)。
其实很简单

因为1~n不是奇数就是偶数
而偶数都不是质数，无法互质
奇数有些是质数，有些是可以互质的
所以每个偶数都必要一个堆
而奇数随便选几个互质的塞进任意一个堆就可以了
所以答案是偶数的个数
注：n=1要特判，不然输出n/2就是0了,还有记得用long long防爆
ACcode:

[code]#includeusing namespace std;long long n; //数据是1e8不要忘记long longint main(){        ios::sync_with_stdio(0);        cin.tie(0);        cin>>n;        if(n==1) cout