所谓最简真分数是一个分数的分子小于分母,且分子分母无公因数。
2010年湖北省小学奥林匹克数学竞赛(小学六年级组)有这样一道试题:以2010为分母的最简真分数有多少个?
这道小学奥数试题考察的是学生对集合包含和容斥知识的掌握情况。
由于2010=2*3*5*67(分解质因数),因此以2010为分母的最简真分数的分子必须小于2010且不能被2、3、5或67整除。
小朋友解决这个问题的计算过程如下:
在1~2010共2010个数中,
能被2整除的数有 2010÷2=1005
能被3整除的数有 2010÷3=670
能被5整除的数有 2010÷5=402
能被67整除的数有 2010÷67=30
能同时被2和3整除的数有 2010÷(2×3)=335
能同时被2和5整除的数有 2010÷(2×5)=201
能同时被2和67整除的数有 2010÷(2×67)=15
能同时被3和5整除的数有 2010÷(3×5)=134
能同时被3和67整除的数有 2010÷(3×67)=10
能同时被5和67整除的数有 2010÷(5×67)=6
能同时被2、3和5整除的数有 2010÷(2×3×5)=67
能同时被2、3和67整除的数有 2010÷(2×3×67)=5
能同时被2、5和67整除的数有 2010÷(2×5×67)=3
能同时被3、5和67整除的数有 2010÷(3×5×67)=2
能同时被2、3、5和67整除的数有 2010÷(2×3×5×67)=1
这样,1~2010中能被2或3或5或67整除的数有
(1005+670+402+30)-(335+201+15+134+10+6)+(67+5+3+2)-1
=2107-701+77-1 =1482
因此,1~2010中既不能被2整除,也不能被3整除,也不能被5整除,也不能被67整除的数有 2010-1482=528 个。
即以2010为分母的最简真分数有528个。
我们可以看出,上面的计算过程是比较繁琐的,需要认真仔细。
学习过程序设计后,可以编写了一个简单的循环程序解决这个问题。
用一个变量cnt来保存最简真分数的个数,初始值为0。
对1~2010中的每一个数num,进行判断,这是一个循环,写成
for(num=1; num<=2010;num++)
循环体中的判断方法为:如果num既不能被2整除,也不能被3整除,也不能被5整除,也不能被67整除,则计数。写成
if(num%2!=0 && num%3!=0 && num%5!=0 && num %67!=0)
cnt++;
最后,输出结果cnt。 一个简单的程序,就得到问题的答案。
? 编写的源程序如下:
#include <stdio.h>
int main()
{
int cnt,num;
cnt=0;
for (num=1; num<=2010;num++)
if (num%2!=0 && num%3!=0 && num%5!=0 && num %67!=0)
cnt++;
printf("%d\n",cnt);
return 0;
}
需要说明的是,当时竞赛的真题是:所有以2010为分母的最简真分数的和为多少?
瞧瞧,作为大学生的你还能像小朋友一样做出来吗?
当然,你学过程序设计,将上面的程序简单改写一下,可以很快得到答案的。何须像小朋友一样苦苦思考和运算呢。
#include <stdio.h>
int main()
{
int num;
double sum;
sum=0;
for (num=1; num<=2010;num++)
&nb