プログラム言語 ハンドブック DosC [富永]

Note435 約数の個数と総和の関数定義

[目次] [表紙]

[Note431] [Note432] [Note433] [Note434] [Note435] [Note436] [Note437] [Note438]

● 約数の個数   [第2部 基本]

正整数nの約数の個数を返却する。 例えば、10の約数は、1,2,5,10 であるから、div_ct(10)=4 となる。
int div_ct(int n) {
  int c = 0;
  int k;
  for ( k = 1; k <= n; k++ ) { 
    if ( n % k == 0 ) { c++; } 
  }
  return c;
}


● 約数の総和   [第2部 基本]

正整数nの約数の総和を返却する。 約数和関数といい、d(n)と書く。 例えば、10の約数は、1,2,5,10 であるから、div_sum(10)=18 となる。
int div_sum(int n) {
  int s = 0;
  int k;
  for ( k = 1; k <= n; k++ ) { 
    if ( n % k == 0 ) { s += k; } 
  }
  return s;
}
div_sum(9) の計算過程は、以下の実行状態表のようになる。
    n   9  =  =  =  =  =  =  =  =  =
    k      1  2  3  4  5  6  7  8  9
  約数    ○ × ○ × × × × × ○
    s   0  1  =  4  =  =  =  =  = 13  ⇒ 


● オイラー関数   [第2部 応用]

正整数nに対し、n以下の正整数で、nと互いに素なもの個数を求める。 これをオイラー関数といい、φ(n) と書く。 例えば、10は2と5を素因数に持つから、1,3,7,9と互いに素で、 euler(10)=4 となる。 別に定義された最大公約数を求める関数 gcd() を用いて計算する。
int euler(int n) {
  int e = 0;
  int k;
  for ( k = 1; k <= n; k++ ) { 
    if ( gcd(n, k) == 1 ) { e++; }
  } 
  return e;
}
オイラー関数は、オイラーの定理で現れる。 乱数、暗号、符号化などに、重要な役割を果たす。