最近ACM时遇到个题，题意如下、
问题描述:
有个1到n的数列，数一下其中能够被 2，3，5 整除的数字的个数。例如当n = 6 的时候有 2，3，4，5，6.这5个数满足条件，所以我们应该输出 5 。
输入
多组输入到文件尾，每组输入一个 n (n < 1e9)
输出
输出对应的个数
样例输入
1 2 6
样例输出
0 1 5
一眼看上去，很简单呀，想都没想就写上了以下代码
#include <stdio.h> long long main(void) { long long n, i, flag = 0; while(scanf("%lld", &n)) { for(i = 1; i <= n; i ++) if(i % 2 == 0 || i % 3 == 0 || i % 5 == 0) flag ++; printf("%lld\n", flag); flag = 0; } }
一提交 时间超限 ,我就在本地编译器上调试了一下，看了一下题目 (n < 1e9) 便输入 99999999 结果半天没有计算出结果，这肯定超时啦，题目限定时间为 1000 ms 时间不超限就怪了。
既然这样不行，那就要优化算法，思来想去也没有什么头绪。后来看到了这篇博客 http://blog.csdn.net/u010885899/article/details/48022633 文章内容就讲的是利用容斥原理计算出 1<=N 中是 2、3、5、7 倍数的整数的数量。
受此启发，百度百科了一下 容斥原理 :
在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。（A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）
由此定义，可以照着葫芦画瓢了。
能被 2 整除的事件记为 A 类， 能被 3 整除的事件记为 B 类， 能被 5 整除的事件记为 C 类。 那能被 2 3 5 整除的整数数量可以这样表示: A 类元素个数 + B 类元素个数 + C 类元素个数 — 既是 A 类又是 B 类元素的个数 — 既是 B 类又是 C 类元素的个数 — 既是 A 类又是 B 类元素的个数 + 既是 A 类 又是 B类而且是 C 类元素的个数 （即 能被 2 或 3 或 5 整除的个数 = 能被 2 整除的个数 + 能被 3 整除的个数 + 能被 5 整除的个数 — 能同时被 2 3 整除的个数 — 能同时被 2 5 整除的个数 — 能同时被 3 5 整除的个数 + 能同时被 2 3 5 整除的个数）
那么就可以写出对应代码
#include <stdio.h> int main(void) { int n, num; int a, b, c; int ab, ac, bc; int abc; while(scanf("%d", &n)) { a = n / 2; b = n / 3; c = n / 5; ab = n / (2 * 3); ac = n / (2 * 5); bc = n / (3 * 5); abc = n / (2 * 3 * 5); num = a + b + c - ab - ac - bc + abc; printf("%d\n", num); } }
提交， Bingo 没问题，本地也测试了一下输入稍微大于 1 e 9 的数也是不到 1000 ms就出计算结果。