Question

ゲスト

「216以下の自然数で、216と互いに素である自然数の個数を求めよ。」
この問題を教えてください。
216を素因数分解→216=(2^3)×(3^3)して、2の倍数、2^2の倍数.......と個数を求めていくと思うのですが答えが合いません。
やり方が間違っているのか計算ミスか分かりません
ちなみに答えは72個みたいです
よろしくお願いします

整数の個数

Answer 1

Knight

ちなみに、互いに素な整数の個数はオイラーのφ関数（オイラーのファイかんすう）と呼ばれていて簡単に公式化されているから覚えておくといいよ！

Answer 2

Knight

> 2の倍数、2^2の倍数.......と個数を求めていく
のはよくよく考えたら無駄なんよね。
なぜなら、2の倍数⊃4の倍数⊃8の倍数⊃...だから、一番おっきい（個数が多い）2の倍数だけ考えればいいんね。
同様の理由で、3の倍数, 9の倍数, ...って考えるのは無駄で、3の倍数だけ考えればいい。

だから、[2の倍数]または[3の倍数]であるような整数の個数をカウントすればいいよ！
その個数を216から引くと答えになるよ〜

ゲスト

計算の手間が省ける方法を教えてくださり、ありがとうございます。
オイラーのφ関数、必ず覚えます。