2 3 5 7的倍数

基准时间限制：1 秒空间限制：131072 KB

给出一个数N，求1至N中，有多少个数不是2 3 5 7的倍数。例如N = 10，只有1不是2 3 5 7的倍数。

Input

输入1个数N(1 <= N <= 10^18)。

Output

输出不是2 3 5 7的倍数的数共有多少。

Input示例

Output示例

1

离散中包含排斥原理

 1 #include <stdio.h>
 2 #define ll long long
 3 /*
 4 只需要分别知道2的倍数个数，3的倍数个数，5的倍数个数，7的倍数的个数，
 5 之后通过容斥原理
 6 （先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，
 7 然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，
 8 这种计数的方法称为容斥原理
 9 */
10 int main(){
11     ll n;
12     scanf("%lld",&n);
13     ll a, b, c, d, ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, abcd;
14     a = n / 2;
15     b = n / 3;
16     c = n / 5;
17     d = n / 7;
18     ab = n / 6;
19     ac = n / 10;
20     ad = n / 14;
21     bc = n / 15;
22     bd = n / 21;
23     cd = n / 35;
24     abc = n / 30;
25     abd = n / 42;
26     acd = n / 70;
27     bcd = n / 105;
28     abcd = n / 210;
29     ll num = a + b + c + d - ab - ac - ad - bc - bd - cd + abc + abd + bcd + acd - abcd;
30     printf("%lld",n - num);
31 }