题目

1到1000中所有不能被2、3、5整除的自然数有多少个?算式怎么列?

提问时间：2021-04-01

答案

1到1000中所有不能被2、3、5整除的自然数有多少个?算式怎么列?
以下用[]表示取整数部分,即高斯取整函数.
计算过程是将下面{}内的各行的计算项取代数和.
{
1000,
-[1000/2]-[1000/3]-[1000/5] = -500 -333-200 =-1033
+[[1000/2]/3] +[[1000/2]/5] +[[1000/3]/5] =[500/3]+[500/5]+[333/5]=166+100+66=332
-[ [[1000/2]/3]/5 ]=-[166/5] =-33
}
=1000-(500+333+200) +(166+100+66)-33
=-33+332-33=266
原理:容斥原理 (又称作包含排除原理或逐步淘汰原则,可参考百度百科-容斥原理)
推广:
1到X中所有不能被2,3,5,...,p(i),...,p(n)整除的自然数的个数
=sum{
+X,
-{ [X/2]+[X/3]+...+...+[X/p(n)] }
+{
+[X/2/3]+[X/2/5+.+[X/2/p(n)]
+ [x/3/5]+...+[x/2/p(n)]
+ ...+...
+ +[X/p(n-1)/p(n)]
}
-...
+...
+ (-1)^n * [X/2/3/.../p(n)]
}
注#1:这里的[]表示取整数部分,即高斯取整函数.
注#2:计算时可以使用 [X/(2*3)]=[ [X/2] /3 ]= [ [X/3] /2 ]
注#3:在数论中,欧拉函数有类似的形式与性质
注#4:代数和的正负号=(-1)^数的奇次方质因子的个数(或者说,去除平方因数之后的剩下质因子的个数为奇则取负,为偶数包括0则取正).这在数论中称作mobius函数(莫比乌斯),参考百度百科-数论函数-积性函数.