パンの木を植えて

主として数学の話をするブログ

トップ > シルヴァーマン『はじめての数論』 > 素数判定をする - Ex 7.7(a)

素数判定をする - Ex 7.7(a)

シルヴァーマン『はじめての数論』
\[ %%% 黒板太字 %%% \newcommand{\A}{\mathbb{A}} %アフィン空間 \newcommand{\C}{\mathbb{C}} %複素数 \newcommand{\F}{\mathbb{F}} %有限体 \newcommand{\N}{\mathbb{N}} %自然数 \newcommand{\Q}{\mathbb{Q}} %有理数 \newcommand{\R}{\mathbb{R}} %実数 \newcommand{\Z}{\mathbb{Z}} %整数 %%% 2項演算 %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \]

おはようございます．

最近引っ越し先で体調を崩し，

  • 体調を回復するためには何か食べないといけない

  • 何か食べるには，あまりにも頭痛と吐き気が強すぎる

という悪循環にハマって死にかけました．

幸い電話で人を呼ぶことができたのでなんとかなりましたが，今後はこういうことのないよう気を付けていこうと思います．


さて今回は，『はじめての数論』の演習問題をやっていきます．

はじめての数論 原著第4版

はじめての数論 原著第4版

Amazon

今回のテーマは素因数分解です．

\[ %%% 黒板太字 %%% \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} %%% カリグラフィー %%% \newcommand{\calf}{\mathcal{F} } \newcommand{\calg}{\mathcal{G} } %%% 引数を取るもの %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \newcommand{\im}{\operatorname{im} } \]

問題文（共通）

この練習問題ではあなたは，正の整数 $n$ を素数の積に分解するプログラムを書くことを求められている．（もし $n=0$ であれば，無限ループに入らずにエラーを返すことを忘れずに！）$n$ の素因数分解を表現する便利な方法は $2 \times r$ 行列として表すことである．つまり，

$$ n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} $$

のとき，$n$ の分解を行列

$$ \begin{pmatrix} p_1 & p_2 & \cdots & p_r \\ k_1 & k_2 & \cdots & k_r \end{pmatrix} $$

で表す．（もしあなたのコンピュータが動的な記憶割付を許さないときは，実行前にどれだけ多くの因数を許すか決めておく必要がある．）

問a の問題文

考えうる因数 $d=2,3,4,5,6, \ldots$ のそれぞれで割ってみることで $n$ の因数を見つけるプログラムを書け．（この方法はきわめて効率が悪いが，ウォーミングアップの練習問題として役立つであろう．）

問a の回答

この方法では素因数分解は求めることができない気がします．因数が素数とは限らないですからね．

与えられた数 $n$ が素数だと返すか，あるいは因数分解 $n = a \times b$ を返して合成数であることを示すか，どちらかの挙動をするアルゴリズムを書けということでしょう．

まず疑似コードを書くとこんな感じ．

ここで青字で書かれている find? というのは変数の名前です．因数が見つかったか？ということを記憶させるためのもので，forループを抜けたときに因数が見つかっていなければ「$n$ は素数です」と返せるように準備しました．

コード中にある break という命令は，一つ外側にあるforループを（途中であっても）抜けなさいという指示です．


さて，それでは Python で実装していきましょう．いつも通り VSCode＋JupyterNoteBook を環境として使用します．

とりあえず何も考えずに書くとこんな感じでした．

# 素数判定
## 入力
n = 
## 手続き
find = 0
for d in range(2,n):
    if n % d == 0:
        a = d
        b = n // d
        print(a,b)
        find = 1
        break
if find == 0:
    print("nは素数")

ひとつ注意点があります．for d in range(2,n):と書いてあるのが見えるでしょうか．これは $2 \leq d \leq n-1$ に対して繰り返せという指示です．

つまりループの繰り返しを $2 \leq d \leq n-1$ に対して行っているので一見すると計算時間が $O(n)$ であるように見えますが，因数がひとつでも見つかったら停止するので，実際の計算時間は $O(\sqrt{n})$ になります．


動かしてみると素数判定はうまく行きますが，$n=0$ のときに「$n$ は素数」とトチ狂ったことを言ってしまうという欠陥があります．とりあえず入力を $2$ 以上に限定することで回避しましょう．

というわけで最初に

if n <= 1:
    print("エラー nは２以上の整数としてください")

という節を追加してみたのですが，どうやらこれもまずい様子．

このままだとエラーになってもやっぱりアルゴリズムの残りの部分が実行されてしまって，相変わらず「$n$ は素数」という狂ったメッセージが出てしまいます．まずいなぁ．

「アルゴリズムの残りの部分を実行しない」という強制終了コマンドがあれば解決するのですが，調べた限りそんなものは見つからなかったので，if文に分岐を足すことで解決することにしました．

# 素数判定
## 入力
n = 
## 手続き
find = 0
for d in range(2,n):
    if n % d == 0:
        a = d
        b = n // d
        print(a,b)
        find = 1
        break
if find == 0 and n >= 2:
    print("nは素数")
elif find == 0 and n <= 1:
    print("エラー. nは2以上とせよ")
else:
    pass

ここでpassというのは何もしないという命令で，文法上if文の各分岐には何か書かないといけないので書いているだけです．


感想とまとめ

今回は，単純な約数の全探索によって素数判定をするアルゴリズムを書きました．

まだ練習問題をやっただけですが，コードを貼っていたら記事が長くなってしまったのでこの辺りで切ります．