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という法則も関係しているそう。
  • Chinese remainder theoremという法則も関係しているそう。
• Modular Divisionというトピックも紹介されていました。
  • TopCoder Forums

• 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();

• メールの送信には、sendmailというソフトを使っている模様
  • ログが/var/log/mail.logにある。
  • 見てみるとOperation timed outってなってる。
  • sendmailの設定の問題か。
• ぐぐる
  • こちらや、Mac OS X で Postfix(sendmail) を使って CLI でメールを送る - EAGLE 雑記
  • こちらを読む。Mac Leopard環境でActionMailerでメール送信できない時に見直すこと - func09
• とりあえず理解もそうそうに、こちらのやり方（Mac OS X で Postfix(sendmail) を使って CLI でメールを送る - EAGLE 雑記）をそのままやってみたらできた。

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