题目五、2 3 5 7的倍数
给出一个数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的倍数的数共有多少。
输入示例
10
10000
1234567890
98765
11111111111111111
输出示例
1
2285
282186946
22575
2539682539682540
解题思路：
先说我看到这题的思路，枚举1到N的所有整数用一个if判断i%2||i%3||i%5||i%7，如果为真，则ans计数器加一，时间复杂度O(n),
在1 <= N <=10^18的情况下直接GG吧。
于是我就联想到在素数打表中的欧拉筛法，可以这么想，将1到N的所有数以十为单位分组，第二个第四个第五个第六个第八个第十个数不用判断，就只需要判断每一组中，第一个元素，第三个元素，第七个元素，第九个元素是不是3和7的倍数。这个时间复杂度略低于第一个，遇到大树还是直接GG了。
第三个方法我就换了个思路，同余定理，具体的理论百度就好了。在本题中，在1到N中不是2 3 5 7的倍数的数
= N - N中是2的倍数的个数
- N中是3的倍数的个数
- N中是5的倍数的个数
- N中是7的倍数的个数
+N中是2和3的倍数的个数
+N中是2和5的倍数的个数
+N中是2和7的倍数的个数
+N中是3和5的倍数的个数
+N中是3和7的倍数的个数
+N中是5和7的倍数的个数
-N中是2,3,5的倍数的个数
-N中是2,3,7的倍数的个数
-N中是2,5,7的倍数的个数
-N中是3,5,57的倍数的个数
+N中是2,3,5,7的倍数的个数；
时间复杂度从O(n)降到了O(1),代码就是几个除法运算的加减就能算出结果，注意这里的N要以long long存储。
代码：
#include <cstdio> int main() { long long n; long long count = 0; scanf("%lld", &n); count = n - n / 2 - n / 3 - n / 5 - n / 7 + n / (2 * 3) + n / (2 * 5) + n / (2 * 7) + n / (3 * 5) + n / (3 * 7) + n / (5 * 7) - n / (2 * 3 * 5 ) - n / (2 * 5 * 7) - n / (2 * 3 * 7) - n / (3 * 5 * 7) + n / (2 * 3 * 5 * 7); printf("%lld", count); return 0; }