2017年度「プログラミング言語1」「プログラミング言語演習」のページ

練習問題

2017年5月19日出題
  1. \(a+bi\) (ただし、\(a\) と \(b\) は整数、\(i\) は虚数単位)の形で表せる複素数をガウス整数と呼ぶ。ガウス整数とガウス整数の積はガウス整数となる。ガウス整数 \(a+bi\) でガウス整数 \(m+ni\) が割り切れるとは、あるガウス整数 \(x+yi\) が存在して、\((a+bi)(x+yi)=m+ni\) が成り立つことと定義する。

    ガウス整数は以下の四種類に分類できる。

    任意のガウス整数で割り切れる。
    単数
    ちょうど4個のガウス整数で割り切れる。
    ガウス素数
    ちょうど8個のガウス整数で割り切れる。
    ガウス合成数
    8個より多くのガウス整数で割り切れる。
    1. ガウス整数を分類するプログラムを書け。整数 \(a\), \(b\) を入力し、\(a+bi\) の種類に応じて、以下の通り出力せよ。

      入力したガウス整数の種類 出力
      Z
      単数 U
      ガウス素数 P
      ガウス合成数 C
    ヒント1

    零は \(0\) のみ。 単数は \(1\), \(i\), \(-1\), \(-i\) の四つのみ。

    ヒント2

    ガウス整数 \(a+bi\), \(x+yi\), \(m+ni\) が \((a+bi)(x+yi)=m+ni\) をみたせば、\((a^2+b^2)(x^2+y^2)=m^2+n^2\) が成り立つ。

    さらに \(m+ni\neq0\) を仮定する。 \(x^2+y^2\) は整数であることに注意すると、\(x+yi\neq0\) より \(x^2+y^2\ge1\) がわかる。したがって、\(a^2+b^2\le m^2+n^2\) が成り立つ。

    ガウス整数 \(m+ni\) が零でも単数でもなければ、\(m+ni\) を割り切るガウス整数は少なくとも八つある。うち四つは単数であり、残りの四つは \(m+ni\) に単数をかけたものである。零でも単数でもないガウス整数 \(m+ni\) を割り切るガウス整数がその八つ以外になければ \(m+ni\) はガウス素数であり、あればガウス合成数である。

    この事実を利用すると、零でも単数でもないガウス整数 \(m+ni\) がガウス素数であるかどうかの判定には、\(1\lt a^2+b^2\lt m^2+n^2\) をみたすガウス整数 \(a+bi\) についてのみ試し割りをすれば良いことがわかる。すなわち、\(m+ni\) が \(1\lt a^2+b^2\lt m^2+n^2\) をみたすどのガウス整数 \(a+bi\) でも割り切れなければガウス素数であり、どれか一つの \(a+bi\) ででも割り切れればガウス合成数である。

    ヒント3(高速化を望む人のために)

    ガウス整数 \(u+vi\) は単数とする。このとき、ガウス整数 \(a+bi\) でガウス整数 \(m+ni\) が割り切れることと、ガウス整数 \((a+bi)(u+vi)\) でガウス整数 \(m+ni\) が割り切れることは同値である。

    ガウス整数 \(a+bi\) は零でないとする。\(a+bi\) に単数をかけたもの、すなわち、単数であるガウス整数 \(u+vi\) を使って \((a+bi)(u+vi)\) の形でかける四つのガウス整数のうち、ちょうど一つが \(\{x+yi\mid x\gt0 \text{ かつ } y\ge0\}\) に範囲にある。

    以上の事実をうまく利用すると、\(a \gt 0\) かつ \(b \ge 0\) をみたすガウス整数についてのみ試し割りすることで、高速化が可能である。ヒント2のみを利用するよりも試し割りの回数を約1/4にできる。

    ヒント4(さらに高速化を望み、数学が得意で、英語が苦にならない人のために)

    Weisstein, Eric W. "Gaussian Prime." From MathWorld--A Wolfram Web Resource に、ガウス整数がガウス素数である必要十分条件が説明されている。

  2. \(a+b\omega\) (ただし、\(a\) と \(b\) は整数、\(\omega=(-1+\sqrt{3}i)/2\))の形で表せる複素数をアイゼンシュタイン整数と呼ぶ。アイゼンシュタイン整数とアイゼンシュタイン整数の積はアイゼンシュタイン整数となる。アイゼンシュタイン整数 \(a+b\omega\) でアイゼンシュタイン整数 \(m+n\omega\) が割り切れるとは、あるアイゼンシュタイン整数 \(x+y\omega\) が存在して、\((a+b\omega)(x+y\omega)=m+n\omega\) が成り立つことと定義する。

    アイゼンシュタイン整数は以下の四種類に分類できる。

    任意のアイゼンシュタイン整数で割り切れる。
    単数
    ちょうど6個のアイゼンシュタイン整数で割り切れる。
    アイゼンシュタイン素数
    ちょうど12個のアイゼンシュタイン整数で割り切れる。
    アイゼンシュタイン合成数
    12個より多くのアイゼンシュタイン整数で割り切れる。
    1. アイゼンシュタイン整数を分類するプログラムを書け。整数 \(a\), \(b\) を入力し、\(a+b\omega\) の種類に応じて、以下の通り出力せよ。

      入力したアイゼンシュタイン整数の種類 出力
      Z
      単数 U
      アイゼンシュタイン素数 P
      アイゼンシュタイン合成数 C
    ヒント1

    零は \(0\) のみ。 単数は \(1\), \(1+\omega\), \(\omega\), \(-1\), \(-1-\omega\), \(-\omega\) の六つのみ。

    ヒント2

    アイゼンシュタイン整数 \(a+b\omega\), \(x+y\omega\), \(m+n\omega\) が \((a+b\omega)(x+y\omega)=m+n\omega\) をみたせば、\((a^2-ab+b^2)(x^2-xy+y^2)=m^2-mn+n^2\) が成り立つ。

    さらに \(m+n\omega\neq0\) を仮定する。 \(x^2-xy+y^2\) は整数であることに注意すると、\(x+y\omega\neq0\) より \(x^2-xy+y^2\ge1\) がわかる。したがって、\(a^2-ab+b^2\le m^2-mn+n^2\) が成り立つ。

    アイゼンシュタイン整数 \(m+n\omega\) が零でも単数でもなければ、\(m+n\omega\) を割り切るアイゼンシュタイン整数は少なくとも十二個ある。うち六つは単数であり、残りの六つは \(m+n\omega\) に単数をかけたものである。したがって、零でも単数でもないアイゼンシュタイン整数 \(m+n\omega\) を割り切るアイゼンシュタイン整数がその十二個以外になければ \(m+n\omega\) はアイゼンシュタイン素数であり、あればアイゼンシュタイン合成数である。

    この事実を利用すると、零でも単数でもないアイゼンシュタイン整数 \(m+n\omega\) がアイゼンシュタイン素数であるかどうかの判定には、\(1\lt a^2-ab+b^2\lt m^2-mn+n^2\) をみたすアイゼンシュタイン整数 \(a+b\omega\) についてのみ試し割りをすれば良いことがわかる。すなわち、\(m+n\omega\) が \(1\lt a^2-ab+b^2\lt m^2-mn+n^2\) をみたすどのアイゼンシュタイン整数 \(a+b\omega\) でも割り切れなければアイゼンシュタイン素数であり、どれか一つの \(a+b\omega\) ででも割り切れればアイゼンシュタイン合成数である。

    ヒント3(高速化を望む人のために)

    アイゼンシュタイン整数 \(u+v\omega\) は単数とする。このとき、アイゼンシュタイン整数 \(a+b\omega\) でアイゼンシュタイン整数 \(m+n\omega\) が割り切れることと、アイゼンシュタイン整数 \((a+b\omega)(u+v\omega)\) でアイゼンシュタイン整数 \(m+n\omega\) が割り切れることは同値である。

    アイゼンシュタイン整数 \(a+b\omega\) は零でないとする。\(a+b\omega\) に単数をかけたもの、すなわち、単数であるアイゼンシュタイン整数 \(u+v\omega\) を使って \((a+b\omega)(u+v\omega)\) の形でかける六つのアイゼンシュタイン整数のうち、ちょうど一つが \(\{x+y\omega\mid x\gt0 \text{ かつ } 0\le y\lt x\}\) に範囲にある。

    以上の事実をうまく利用すると、\(a \gt 0\) かつ \(0\le b\lt a\) をみたすアイゼンシュタイン整数についてのみ試し割りすることで、高速化が可能である。ヒント2のみを利用するよりも試し割りの回数を約1/6にできる。

    ヒント4(さらに高速化を望み、数学が得意で、英語が苦にならない人のために)

    Weisstein, Eric W. "Eisenstein Prime." From MathWorld--A Wolfram Web Resource に、アイゼンシュタイン整数がアイゼンシュタイン素数である必要十分条件が説明されている。


戻る
奈良女子大学生活環境学部情報衣環境学科生活情報通信科学コース