1～270までの自然数のうち、素因数3の個数を求める場合、3だけでなく3²や3³などの倍数も求める理

1～270までの自然数のうち、素因数3の個数を求める場合、3だけでなく3²や3³などの倍数も求める理由が分かりません(･_･、)

No.2 回答者： sasa-san 回答日時： 2017/11/13 15:31

3の倍数を求めるのであれば、

nを整数として 3n とおけるので、
1≦3n≦270 を満たすnの個数を求めるだけです。
3×90=270なので、3の倍数は90個あることがわかります。

しかし、問題は因数の個数なので
9の場合は3²だから因数3が2つ、
27の場合は3³なのでだから因数3が3つあることを考慮する必要があります。
つまり、この分だけ多く数えなければなりません。

一つ一つ取り上げて因数3の個数を数えるのは大変なので、
次のような手法を取ります。
3の倍数の個数を求める
9の倍数の個数を求める
27の倍数の個数を求める
81の倍数の個数を求める
243の倍数の個数を求める
これらをすべて足し合わせるとすべての因数3の個数となります。

仮に162という数で考えてみましょう。
162=2×81=2×3×3×3×3
なので、因数3が4個あります。
162は、3の倍数、9の倍数、27の倍数、81の倍数でもあるので、
上の手法から4回カウントされ、因数3が4個あるのと同じことになります。

したがって、1～270までの自然数の場合、
3の倍数の個数：90個
9の倍数の個数：30個
27の倍数の個数：10個
81の倍数の個数：3個
243の倍数の個数：1個
より、因数3の個数は
90+30+10+3+1 =134
だとわかるのです。


----------
一方で、因数の個数が多いものから数えるやり方だと、
243の倍数の個数：1個
81の倍数であるが、243の倍数を含まない個数：2個
27の倍数であるが、81の倍数を含まない個数：7個
9の倍数であるが、27の倍数を含まない個数：20個
3の倍数であるが、9の倍数含まない個数：60個
5×1+4×2+3×7+2×20+1×60 =5+8+21+40+60 =134
となります。
解答は同じになりますが、含まない個数を考えるよりも
倍数の個数を足し合わせたほうが簡単だと思いませんか？

No.1 回答者： kairou 回答日時： 2017/11/13 13:21

「素因数3の個数を求める」この言葉の意味が曖昧ですが、3²や3³の場合を含めることは当然でしょう。

①「素因数3を含む自然数の個数を求める」場合は、3,6,9,12、…、24,27、…、とカウントしますね。
②「素因数3 そのものの個数を求める」場合は、3,6、は１個づつですが、9は２個ありますよね。