29 August 2009

素数の特訓 - Prime Numbers, Factorization and Euler Function

Prime Numbers, Factorization and Euler Function

TopCoderの素数に関するチュートリアルを読んだメモです。typoがいくつかあって悩まされた…。

言葉の定義

  • A prime number (素数): 1と自身でのみ割り切れる2以上の正の整数。
  • Composite: 2以上の整数で素数でないもの。
  • Coprime (relatively prime, 互いに素): 1か-1以外の公約数のない(最大公約数が1の)2つの数。

基本的な法則

  • 整数は、素数のみを使ってただ一つの方法で割り切れる。
  • 1は素数でもcompositeでもない。

ユークリッドの法則 (Euclid’s theorem)

  • 素数は無限に存在する。
  • p1, p2, …, pn. をそれぞれ素数とすると、N = p1 * p2 * … * pn + 1 は素数。

Diricletの算術数列の法則 (Dirichlet’s theorem about arithmetic progressions)

  • aとbが互いに素のとき、p = a + n * b (n > 0) となる素数pは無限に存在する。

Trial division (素因数分解)

  • 素因数分解のbrute-forceな求め方。
  • 2からsqrt(n)の範囲で、nをどんどん割っていく。
void factor(int n)
{
    int i;
    for(i=2;i<=(int)sqrt(n);i++)
    {
     while(n % i == 0)
     {
         printf("%d ",i);
         n /= i;
     }
    }
    if (n > 1) printf("%d",n);
    printf("\n");
}

エラトステネスの篩 (Sieve of Eratosthenes)

  • 素数の集合を求める古典的アルゴリズム
void gen_primes()
{
    int i,j;
    for(i=0;i1;
    for(i=2;i<=(int)sqrt(MAX);i++)
     if (primes[i])
     for(j=i;j*i0;
}

ゴールドバッハの予想 (Goldbach's Conjecture)

  • 4以上の整数nは、2つの素数の和で表される。p1 + p2 = n
  • 発展して、4以上の整数nが与えられ、ゴールドバッハの予想を満たす2つの素数の組み合わせがなん通りあるか調べる問題を考える。
    • 例えばn = 10の場合、(5, 5) と (3, 7) で2種類。
  • 上記のgen_primes() を使って求めることができる。
int FindSol(int n)
{
    int i,res=0;
    for(i=2;i<=n/2;i++)
     if (primes[i] && primes[n-i]) res++;
    return res;
}

オイラーのトーティエント関数 (オイラーのφ関数, Euler’s totient function)

  • オイラーのトーティエント関数φ(n)は、nより小さい整数のうち、nと互いに素のものの数を返す。
  • この関数には以下の特徴がある。
    • pを素数とすると、 φ (p) = p – 1 かつ、任意のaに対して φ (pa) = p a * (1 – 1/p)
    • mとnが互いに素のとき、 φ (m * n) = φ (m) * φ (n)
    • n = p1^a1 * p2^a2 * ... * pk^ak (素因数分解した)のとき、φ (n) = n * (1 – 1/p1) * (1 – 1/p2) * ... * (1 – 1/pk)
int fi(int n)
{
    int result = n;
    for(int i=2;i*i <= n;i++)
    {
     if (n % i == 0) result -= result / i;
     while (n % i == 0) n /= i;
    }
    if (n > 1) result -= result / n;
    return result;
}
  • ここで例題。n以下で(1 <= n <= 10^9)nと互いに素な整数の数を求める。
    • n = 12のときは4 (1, 5, 7, 11)
    • 単にφ (n) で求まる。
  • 別の例題。 ある関数Answer(x, y)を計算する。x, yは[1, n]の範囲で、1 ≤ n ≤ 50000。ここで、Answer(x, y)を求めておくと、Answer(k * x, k * y)はすぐに求められるとする。この状況で、予め計算しておくx, yの組み合わせを求めたい。
    • 例えば、n = 4のときは11通り(Answer(1, 1), Answer(1, 2), Answer(2, 1), Answer(1, 3), Answer(2, 3), Answer(3, 2), Answer(3, 1), Answer(1, 4), Answer(3, 4), Answer(4, 3), Answer(4, 1))
    • res(i)を予め計算しておく必要のある、最小の組み合わせと定義すると、次の式で求まる。
    • res(1) = 1, res(i + 1) = res(i) + 2 * j (i + 1), i > 1
    • でも理由がうまく理解できない…。
      • あとこの数式の意味が分からない。x, y Î{1, …, i}。" Î " この演算子なんなんだろ、調べにくいし、こまった。

オイラーのトーティエントの法則 (Euler’s totient theorem)

  • aとnが互いに素のとき、a φ (n) ≡ 1 (mod n)

フェルマーの小定理 (Fermat’s little theorem)

  • pが素数のとき、nと互いに素な任意の整数aに対して、
    • a p ≡ a (mod p)
    • あるいは、a p -1 ≡ 1 (mod p)

約数の数

  • 整数nの約数の数は、nを素因数分解した際の、それぞれの指数+1を掛け合わせたものに等しい。
  • n = p1^a1 * p2^a2 * ... * pk^ak のとき、(a1 + 1) * (a2 + 1) * … * (ak + 1)
    • n = 36 のときは9 (1, 2, 3, 4, 6, 9, 12, 18, 36)
  • ここで例題。整数n (0 < n < 231) に対して、1 ≤ m ≤ n, GCD(m, n) ≠ 1 , GCD(m, n) ≠ m を満たす整数mの個数を求める。
    • 例えば n = 6 のとき、m = 4
    • nから、nと互いに素な数( φ(n) )とnの約数を引けば良い。ただし、1はφ(n)と約数の両方に重複して含まれるので、それを足す。
    • n – φ(n) – (a1 + 1) * (a2 + 1) * … * (ak + 1) + 1

補足

  • Chinese remainder theoremという法則も関係しているそう。
  • Modular Divisionというトピックも紹介されていました。

Mail::Mailerでメールを送りたいので、Postfixを設定する

  • perlのスクリプトからメールを送りたい
    • Perl Cookbookいわく、Mail::Mailerを使え。
    • しかしうまくいかない。送信されていない。
    • コードは問題なさそう
my $mailer = Mail::Mailer->new("sendmail");
$mailer->open({ From => $fromAddress,
To => $toAddress,
Subject => $subject})
    or die "Can't open $!\n";

my $mailBody = 'This is test mail';

print $mailer $mailBody;
$mailer->close();

macではPostfixというソフトがメール操作で使われているようです。sendmailの代替となるソフトのようです。また上記の方法はgmailのsmtpサーバを使って送信しているようです(たぶん)。正直まだちゃんと理解できてません。

Perl Cookbook

Perl Cookbook