首先,我们可以明显地发现这是一个容斥问题。
在 2 ≤ i ≤ 10 2\leq i \leq 10 2≤i≤10 这 9 9 9 个数中,
只有 2 , 3 , 5 , 7 2,3,5,7 2,3,5,7 需要枚举。
于是这样我们就可以分成 4 4 4 个部分来做了。
- 一个数 减去
- 两个数 加上
- 三个数 减去
- 四个数 加上
最后输出结果即可。
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int sum,n;
signed main(){scanf("%lld",&n);sum=n; //sum初始化为n sum-=n/2;sum-=n/3;sum-=n/5;sum-=n/7;//第一部分 减去1个数 sum+=n/6;sum+=n/10;sum+=n/14;sum+=n/15;sum+=n/21;sum+=n/35;//第二部分 加上2个数 sum-=n/30;sum-=n/42;sum-=n/70;sum-=n/105;//第三部分 减去3个数sum+=n/210;//最后一步 加上4个数 printf("%lld",sum);return 0;
}