Eulerの関数を計算するCプログラムの例

Euler の関数を計算する C プログラムの例。

正の整数 n に対して、1 から n までの整数のうち n と互いに素なものの個数を対応させる写像を Euler の関数といいます。記号 φ (ファイ) で表されることが多いです。英語では、totient function と呼ばれています。

プログラム例 (1)

Euler の関数の定義に沿った素朴なプログラム。

#include <stdio.h>

unsigned gcd( unsigned a, unsigned b )
{
  int temp;

  while ( b > 0 ) {
    temp = a % b, a = b; b = temp;
  }

  return a;
}

unsigned phi( unsigned n )
{
  int i, res;

  res = 1;
  for ( i = 2; i < n; i++ ) {
    if ( gcd( i, n ) == 1 ) { res++; }
  }

  return res;
}

int main(void)
{
  unsigned n;

  for ( n = 1; n <= 20; n++ ) {
    printf( "phi(%u) = %u\n", n, phi(n) );
  }

  return 0;
}

実行結果:

phi(1) = 1
phi(2) = 1
phi(3) = 2
phi(4) = 2
phi(5) = 4
phi(6) = 2
phi(7) = 6
phi(8) = 4
phi(9) = 6
phi(10) = 4
phi(11) = 10
phi(12) = 4
phi(13) = 12
phi(14) = 6
phi(15) = 8
phi(16) = 8
phi(17) = 16
phi(18) = 6
phi(19) = 18
phi(20) = 8

プログラム例 (2)

a、b が互いに素なとき φ(ab)=φ(a)φ(b) が成り立つことから、

φ(n)=Πφ(p^{e(p)})=Πp^{e(p)-1}(p-1)

※ p は n の素因子全体にわたる。
※ e(p) は n の p 指数。

が成り立つ。このことを利用したプログラム。

#include <stdio.h>

unsigned phi( unsigned n )
{
  unsigned res, p;

  res = 1; 
  if ( n % 2 == 0 ) {
    n /= 2; 
    while( n % 2 == 0 ) { 
      n /= 2; 
      res *= 2; 
    }
  }
  p = 3;
  while ( p <= n / p ) {
    if ( n % p == 0 ) {
      n /= p; 
      res *= p - 1;
      while( n % p == 0 ) { 
        n /= p; 
        res *= p; 
      }
    }
    p += 2;
  }
  if ( n > 1 ) { res *= n - 1; }

  return res;
}

main 関数、およびプログラムの実行結果はプログラム例 (1) と同じ。

プログラム例 (3)

積公式

φ(n)=n・Π(1-1/p)

※ p は n の素因子全体にわたる。

を利用したプログラム。

#include <stdio.h>

unsigned phi( unsigned n )
{
  unsigned res, p;

  res = n;
  if ( n % 2 == 0 ) {
    res /= 2;
    do { n /= 2; } while( n % 2 == 0 );
  }
  p = 3;
  while ( p <= n / p ) {
    if ( n % p == 0 ) {
      res = res / p * ( p - 1 );
      do { n /= p; } while( n % p == 0 ); 
    }
    p += 2;
  }
  if ( n > 1 ) { res = res / n * (n - 1); }

  return res;
}

main 関数、およびプログラムの実行結果はプログラム例 (1) と同じ。

バリエーション

res = res / p * ( p - 1 ) の部分を、数式として同値な res -= res / p に変更したもの。

#include <stdio.h>

unsigned phi( unsigned n )
{
  unsigned res, p;

  res = n;
  if ( n % 2 == 0 ) {
    res /= 2;
    do { n /= 2; } while( n % 2 == 0 );
  }
  p = 3;
  while ( p <= n / p ) {
    if ( n % p == 0 ) {
      res -= res / p;
      do { n /= p; } while( n % p == 0 ); 
    }
    p += 2;
  }
  if ( n > 1 ) { res -= res / n; }

  return res;
}

main 関数、およびプログラムの実行結果はプログラム例 (1) と同じ。

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示