pythonのライブラリの一つsympyを使えば、簡単に素因数分解ができるということを知った。
import sympy sympy.factorint(1000) #{2: 3, 5: 3}
ちなみに、因数分解も簡単にできる!!
凄い。
import sympy x = sympy.Symbol('x') eqn = x**2 - 3*x + 2 print(sympy.factor(eqn)) # (x - 2)*(x - 1)
これを使って、オイラー関数と約数関数を書いてみた。
オイラー関数
自然数に対して、未満でと互いに素な自然数の個数をで表し、オイラー関数と呼ぶ。
例えば、未満でと互いに素な自然数はなので
def euler(n): factors = sympy.factorint(n) rst = 1 for i,j in factors.iteritems(): rst *= (pow(i,j) - pow(i,j-1)) return rst
約数関数
自然数の約数の和をと表し、約数関数と呼ぶ。
例えば、の約数はなので
def divisor(n): factors = sympy.factorint(n) rst = 1 for i,j in factors.iteritems(): rst *= (pow(i,j+1) - 1)/(i-1) return rst
数え上げ
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 | |
1 | 3 | 4 | 7 | 6 | 12 | 8 | 15 | 13 | 18 | 12 | 28 | 14 | 24 | 24 | 31 | 18 | 39 | 20 |
参考:
wikipedia:オイラー関数
wikipedia:約数関数
オイラー関数に関して:
RSA暗号を実装してみる(理論編) - 技術メモ
関連記事: