Question

一道数学题，我不会心疼分的

1到120，求合数与素数的个数

[不提倡列出再数！！！]

希望有讲解

Answer 1

　　解法1：120以内：

　　① 既不是素数又不是合数的数有一个，即“1”；

　　② 素数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97、101、103、107、109、113、共30个。

　　所以不超过120的合数有120－1－30＝89(个)

　　(附：筛法：从小到大按顺序写出1－120的所有自然数：

　　先划掉1，保留2，然后划掉2的所有倍数4,6，…120等；保留3，再划掉所有3的倍数6,9…117、120等；保留5，再划掉5的所有倍数10,15，…120；保留7，再划掉7的所有倍数，…这样，上面数表中剩下的数就是120以内的所有素数，这种方法是最古老的寻找素数的方法，叫做“埃斯托拉‘筛法’”)

　　说明：当n不很大时，计算1－n中的合数的个数困难不大；但当n很大时，利用筛法就很困难、很费时了，必须另觅他途。

　　[分析2]受解法1的启发，如果能找出1－n中质数的个数m，则n－1－m就是不超过n的合数的个数。由初等数论中定理：a是大于1的整数。如果所有不大于√a的质数都不能整除a，那么a是质数。因为120<121＝112，√120<11，所以不超过120的合数必是2或3或5或7的倍数，所以只要分别计算出不超过120的2、3、5、7的倍数，再利用“容斥原理”即可。

　　解法2：设S1＝{a∣1≤3≤120,2∣a}；S2＝{b∣1≤b≤120,3∣b}；S3＝{c∣1≤3≤120,5∣c}；S4={d∣1≤d≤120,7∣d}，则有：

　　card(S1)＝[120/2]=60，card(S2)＝[120/3]＝40，card(S3)＝[120/5]＝24，card(S4)＝[120/7]＝17；

　　([n]表示n的整数部分，例如[2,4]＝2，…)

　　card(S1∩S2)＝[120/2×3]＝20，card(S1∩S3)＝[120/2×5]＝12，
　　card(S1∩S4)＝[120/2×7]＝8，card(S2∩S3)＝[120/3×5]＝8，
　　card(S2∩S4)＝[120/3×7]＝5，card(S3∩S4)[120/5×7]＝3，
　　card(S1∩S2∩S3)[120/2×3×5]＝4，card(S1∩S2∩S4)＝[120/2×3×7]＝2，
　　card(S1∩S3∩S4)＝[120/2×5×7]＝1，card(S2∩S3∩S4)＝[120/3×5×7]＝1，
　　card(S1∩S2∩S3∩S4)＝[120/2×3×5×7]＝0

　　∴card(S1∪S2∪S3∪S4)＝card(S1)＋card(S2)＋card(S3)＋card(S4)－card(S1∩S2)－card(S1∩S3)－card(S1∩S4)－card(S2∩S3)－card(S2∩S4)－card(S3∩S4)＋card(S1∩S2∩S3)＋card(S1∩S2∩S4)＋card(S1∩S3∩S4)＋card(S2∩S3∩S4)－card(S1∩S2∩S3∩S4)＝(60＋40＋24＋17)-(20+12+8+8+5+3)+(4+2+1+1)-0＝141-56＋8＝93

　　∵2，3，5，7是质数

　　∴93－4＝89

　　即不超过120的合数共有89个。

Answer 2

楼上的太强了，这么详细！！

Answer 3

呵呵