Pebble Coding

ソフトウェアエンジニアによるIT関連技術の備忘録

B-smooth と B-power-smooth

B-smooth と B-power-smooth の概念を押さえておきます。

B-smooth

任意の自然数Nを素因数に分解すると次の形になります。
 N = p_{1}^{e_1} p_{2}^{e_2} p_{3}^{e_3}  \cdot \cdot \cdot p_{i}^{e_i}  \cdot \cdot \cdot p_{m}^{e_m}
ここで、 p_{k}はk番目の素数 {2, 3, 5, 7, 11, …}を表します。
 e_{k}は0以上の整数です。
ここで最も大きい素数 p_m =Bとして、
NをB-smoothであるといいます。

例:
16=2^{4}は2-smoothです。
 9800 = 2^{3} 5^{2} 7^{2}は7-smoothです。

B-power-smooth

任意の自然数Nを素因数に分解すると次の形になります。
 N = p_{1}^{e_1} p_{2}^{e_2} p_{3}^{e_3}  \cdot \cdot \cdot p_{i}^{e_i}  \cdot \cdot \cdot p_{m}^{e_m}
ここで、 p_{k}はk番目の素数 {2, 3, 5, 7, 11, …}を表します。
 e_{k}は0以上の整数です。
このm個の値  p_{1}^{e_1}, p_{2}^{e_2},  p_{3}^{e_3},  \cdot \cdot \cdot,  p_{i}^{e_i},   \cdot \cdot \cdot , p_{m}^{e_m} のうちの最大の値をBとする時、
NをB-power-smoothであるといいます。

例:
 2520= 2^{4} 3^{2} 5 \cdot 7で、  2^{4}, 3^{2}, 5, 7のうち最も大きな値は 2^{4} = 16ですから、
2520は16-power-smoothであるといいます。

NがB-power-smoothであるとき、NはBで割り切れることを覚えておいてください。

参考:

Smooth Number -- from Wolfram MathWorld

Smooth number - Wikipedia