効率化された試し割りによる素数判定【細かすぎるコード解説：C言語編】

14622回の除算で1000以下の素数を求める

手がかり

• 以外の素数はすべて奇数
• 以外の正の整数はどれも素数の倍数といえる（素因数分解）
• 素数で割り切れない整数は、より大きいの倍数でも割り切れない

とでしか割り切れない整数（素数）を探すとき、それより小さい素数で割り切れないものは、その他の整数（素数の倍数）でも割り切れない。

そのため、より小さいすべての素数で割ってみて割り切れるかのみ調べればよい。

プログラムのソースコード【細かすぎる注釈つき】

#include <stdio.h>

int main(void)
{
    //2以上1000以下の整数をnと表すことにする
    //つまり、整数nの中から素数を探すことになる
    int n;

    //除算回数を数えるカウンターを用意
    unsigned long counter=0;/*unsigned long…長い桁数の非負整数を格納できる箱の名称(型)*/

    //素数を入れる箱を500個用意する
    //2以外の素数はすべて奇数であり、1から1000までの数の中に奇数は500個しかない
    //そのうち1は素数ではなく、代わりに2は素数であるから、
    //結局素数を入れる箱は500個で足りる
    int prime[500];

    //i番目の素数をprime[i]と表すことにする
    int i;

    //既に見つけた素数の個数をptrとする。現時点ではまだ0である
    int ptr=0;

    //2と3は素数である
    prime[ptr++]=2;/*prime[0]=2と記憶した後に、ptrの値を1つ増やす(見つけた素数の個数が1になる)*/
    prime[ptr++]=3;/*prime[1]=3と記憶した後に、ptrの値を1つ増やす(見つけた素数の個数が2になる)*/

    //このように、小さい数から順に素数を探していくから、
    //番号が若い素数の方が小さい素数である

    //現時点で見つかっている素数2個(prt=2)のうち最大のものはprime[1]=3であるように、
    //これまで見つけたptr個の素数のうち最大のものは、prime[ptr-1]で表される

    //5以上1000以下の数の中から素数を探す
    for (n=5 ; n <= 1000; n+=2)/*5から始まって2ずつ増やしていくことで、奇数のみが対象になる*/
    {
        //これまで見つけた素数prime[0]～prime[ptr-1]すべてで割ってみる
        //しかし、これから見つける素数はすべて奇数であるので、2で割り切れる数(偶数)は最初から除外してよい
        //よってprime[0]である2で割る必要はないので、3=prime[1]～prime[ptr-1]で割ってみる
        for ( i = 1; i < ptr; i++)
        {
            counter++;/*除算回数が1増える*/

            if (n % prime[i] ==0)/*もし整数n(>4)がそれより小さい素数で割り切れたなら*/
            {
                break;           /*nは素数ではないので、もう他の数で割る必要はない⇒このforから追放*/
            }

            //ここでi++が実行され、iの値が1増える

            //割り切れなかったものはこのforの冒頭に戻り、iが1大きな値に書き換えられたforの中身を繰り返す
            //                                       (つまりより大きい素数で割られる)

        }
        
        //途中でforを追放されたものはここに到達している
        //まだiの値がptrよりはるかに小さい段階で中断されているので、
        //ptr=iという条件を満たさず、if(ptr==1){}はスルーしてこのまま外側のforからも抜けることになる

        //最大素数prime[ptr-1]までのすべての素数で割り切れなかったものは、
        //最後までbreakで抜けることなく、後処理i++を受けてここに到達する
        //つまり、最大素数での最後の除算をする段階ではi=ptr-1だが、その後のi++によって今はi=ptrとなっている
        //これは次のif文も実行されることになる

        if (ptr == i)/*i=ptrなら(これまで見つけたprime[ptr-1]までのすべての素数で割り切れなかったら)*/
        {
            prime[ptr++]=n;/*そんな整数nを新たな素数prime[ptr]として登録する
                            *(登録した後に、登録済み素数の数が1増える)       */
        }

        //ここでn+=2が実行され、nの値が2増える
        //外部forの冒頭に戻り、2大きな整数nについて全体の処理が再度行われる
        //このようにして、1000以下の整数をすべて登録済み素数で割って、選別する
        
    }

    //1000以下の整数すべての選別が終わると、ここに到達する
    //最終的に登録された素数すべて(prime[1]～prime[ptr-1])を一覧で表示する
    for ( i = 0; i < ptr; i++)
    {
        printf("%d\n",prime[i]);
    }
    
    //除算回数を表示する
    printf("乗除を行った回数:%lu\n",counter);

    return (0);
 }

3774回の乗算・除算で1000以下の素数を求める

強力な武器

• の平方根以下の素数で割り切れることがなければ、は素数である

改良版プログラムのソースコード【細かすぎる注釈つき】

変更した箇所にのみ補足説明を加えている。

#include <stdio.h>

int main(void)
{
    int n;

    //乗算・除算回数を数えるカウンターを用意
    unsigned long counter=0;

    int prime[500];

    int i;

    int ptr=0;

    prime[ptr++]=2;
    prime[ptr++]=3;

    for (n=5 ; n <= 1000; n+=2)
    {
        //2つの状態のどちらか(ONかOFFか)を判定するために使う変数をフラグという
        //今回は割り切れたか否かを判定する用に使う
        int flag = 0;/*初期値は0(フラグを下ろしておく)*/

        //nの平方根以下のすべての素数で割ってみる
        //『素数pがnの平方根以下』という条件は、両辺2乗して『pの2乗がn以下』と言い換えられる
        for ( i = 1; counter++ , prime[i]*prime[i] <= n; i++)
                     /*《A,B …AとBを順に実行し、Bの値を返す》
                      *for内部を実行するかの判定をするのはprime[i]*prime[i] <= nだが、
                      *判定の度に乗算*をカウントするということ　　　　　　　　　　　　　*/
        {
            counter++;

            if (n % prime[i] ==0)/*割り切れたなら*/
            {
                flag = 1;        /*フラグを上げる*/
                break;           
            }

        }

        if (!flag)         /*flag=0(フラグが下がったまま)なら*/
        {
            prime[ptr++]=n;/*割り切れなかったということなので、素数として登録*/
        }
        
    }

    for ( i = 0; i < ptr; i++)
    {
        printf("%d\n",prime[i]);
    }
    
    printf("乗除を行った回数:%lu\n",counter);

    return (0);
 }

コード引用元

今回掲載したコードのベースとなっているのは、柴田望洋先生の著書明解C言語入門編の109・111ページに掲載されているサンプルコードです。 説明の都合上、変数の名称や変数宣言の順序を変えています。また、括弧のレイアウトは自分好みに変えています。

定理の証明に関する参考文献

現在LaTeXで制作中の整数論ノートに今回素数判定に用いた定理の証明も掲載予定です。 厳密な証明ではないですが、コード引用元の書籍では正方形の図によってわかりやすく導出されています。 厳密な証明を追いかけたい方にはモノグラフ 整数をオススメします（が、絶版なんだよなあ…）。

Dimention too large対策【minipage環境でTeXを騙せ】

xymatrixを使用していると、しょっちゅうdimention too largeエラー地獄に陥る。
最終的なエラーメッセージの少し上には、
Overfull \vbox (数字pt too high) has occurred while \output is active
という記述がある。
数字の部分は場合によって異なるらしく、10未満であれば

\setlength\headheight{10pt}

をプリアンブルに加えることで改善するらしい。
私が直面したエラーでは約15000だったため、ダメもとで\setlength\headheight{16000pt}と書き加えてみたが、まあそりゃ無理である。
ちなみに\setlength\headheight{16000pt}と加えてタイプセットしたときに出たエラーは
! Huge page cannot be shipped out.（直訳：巨大なページは出荷できません。）
…そりゃそうよね。
そんなわけで別な解決策を探した結果、次のようにしたらうまくいった。

❂ ❃ ❅ ❆ ❈ ❉ ❊ ❋ ❂ ❃ ❅ ❆ ❈ ❉ ❊ ❋
まず、\end{document}を少し上の行に移動させて、\end{document}より下にテキストがある状態でタイプセットしてみる。
正常にコンパイルされるまで、\end{document}を少し上に移動→タイプセットを繰り返す。（dimension too large以外のエラーは無視して続行）
正常にコンパイルされるときが来たら、そのときの\end{document}の直後にある部分がエラーの原因である。

エラー箇所を特定できたら、

\begin{minipage}[t]{40zw}
エラー部分（とその前後、1ページに収まる長さで）
\end{minipage}

とエラー部分を囲んで、\end{document}を一番下の行に戻してタイプセットする。

❂ ❃ ❅ ❆ ❈ ❉ ❊ ❋ ❂ ❃ ❅ ❆ ❈ ❉ ❊ ❋

難しい話はよくわからないが、この方法はエラー部分を含む段落を巨大な1文字と認識させることで、エラー部分に気づかせないようにする手法らしいな（素人の信用ならない意訳）
40zwは、その巨大な１文字の横幅である。1zwは平仮名１文字の横幅で、デフォルトでは１行に40文字並ぶため、40zwと設定した。この値を小さくすれば、ページの右端に着く前に改行されることになる。
tはtopの略で、この巨大な1文字を\begin{minipage}の直前の行のすぐ次の行に配置することを意味する。cにすれば余白の真ん中の行、bにすればページの一番下の行に沿って配置されることになるのだろう。つまり、cやbにすれば直前の行との余白が空く。普通に横書きで上の行から順に書いている状態なら、tにしておけば自然な見栄えになるはずだ。

参考にしたウェブサイトはこちら。このブログは精一杯意訳した結果なので、説明不足・解釈違いは本家を見て補ってほしい。
7.6 ボックス

数学・物理・化学のノートづくりに役立つLaTeXマクロ一覧

CTANにある数多のマクロ達。それらを隅々まで把握している者はおそらく存在しないだろう。知れば知るほどLaTeXの無限の可能性を実感できるのに、誰もが使う一部のマクロしか知られていないのはもったいない…
『こんなものをつくりたい！』と思ったときにどんなマクロを使えば効率が良いのか、迷える未来の自分と誰かのためにメモしておく。
随時更新。マクロの説明は超主観的なので、気になったものはぜひ検索してマニュアルを開いてみてほしい。

witharrows
…式変形に補足説明を加える

bchart
…棒グラフをかく

tikznetwork
…グラフ理論の図解、様々な模様を描いた平面を描画、2平面間に矢印を描画
（複素関数や多変数関数、線形代数などの図解に使えそう）

tkz-linknodes
…樹形図、式変形に補足説明を加える

tkz-euclide
…平面幾何、コンパス跡、分度器

tkz-graph
…グラフ理論

tkz-berge
…樹形図、項などを表す球（力学ノートで質点として使えそう、特に多質点系の力学で大活躍しそう）

thmtools
…定理を記述する環境を整えてくれる

rulercompass
…コンパスによる作図跡

pas-cours
…メタリック調のテカテカした枠組み、テカテカした立体、立体幾何、展開図、漸化式の図示

luamesh
…平面幾何、グラフ理論

drawmatrix
…行列の中身を表す箱

venndiagram
…ベン図

rank 2 roots
…群論の図

nicematrix
…行列中に列や行を区切る線引き、表、行列の成分を色分け、行列の横や上下に行や列の名前を表すメモ書き、一般の大きさの行列、行列の横や上に行や列の本数を表すメモ書き、掃出法の変形の補足説明、行列間の関係を表す矢印

karnaugh-map
…カルノー図

scratch3
…一行メモをパズルのように羅列

tikzorbital
…分子軌道法ダイアグラム、混成軌道のイメージ図

modiagram
…分子軌道法ダイアグラム

bohr
…ボーア模型風電子配置図

pgf-spectra
…光のスペクトル

pst-sigsys
…様々な物理の図を描く

pst-optic
…レンズの図ならなんでもかける

tikz-optics
…光の実験の装置図、物体の長さを表す矢印

pst-magneticfield
…磁場を描く

chemschemex
…反応機構を組み立てる矢印（生化学などの円形反応機構にも対応）

tikz-planets
…惑星

circuitikz
…回路図

tikz-qtree
…樹形図

forest
…樹形図（tikz-qtreeよりバリエーション豊富）

istgame
…樹形図、グラフ理論

mptrees
…樹形図

fast-diagram
…樹形図、家系図、分類表

ribbonproofs
…証明の流れや他の定理との関係を表す表

tikz-dependency
…単語と単語の間を矢印で結んで関係を表す（数列の項どうしの関係をメモするのに役立ちそう）

smartdiagram
…円形の関係図（生化学反応の概要を表すのに役立ちそう）
…横並びの関係図（作業の手順をメモするのに役立ちそう）
…縦並びの関係図
言葉で表せないが、ノート制作において本当にいろいろ使えそう

bodewgraph
…対数グラフ

tikz-3dplot
…３次元座標、３次元グラフ

pgfplots
…あらゆるグラフを描画（多変数関数の微分積分学、統計学などのノートづくりに必須）

bclogo
…可愛い枠

tikiz-page
…ページ端に装飾を施す（便箋とか作れそう）

callouts
…画像にメモを書き込む

matrix.skeleton's
…行列などを表す色分けされた表

tikzmark
…文章中に矢印メモを書き加える

DPcircling
…文章中の一部分を特殊な枠で囲んで強調する

xypic
…圏論、編み物の編み図

commutative diagram
…圏論

xlop
…筆算

underoverlap
…数式の上下に括弧で注釈、数式の一部を箱で囲んで注釈

onbraces
…数式の上下に括弧で注釈

tkz-tab
…微分でグラフをかくときの増減表、数列の増減を表す表

tabvar
…増減表

systeme
…連立方程式の記述

statistics
…グラデーション表（pH表とかに使えそう）、統計学のグラフ

spalign
…行列やベクトルの記述

short math
…複雑な数式の記述

shapes
…分数を表す円

schulmathematik
…複雑な数式、座標平面、化学定数、回路図、同位体、問題集のような空欄、計算問題集のように数式を並べる、列ベクトルを簡単に出力

rec-thy
…抽象数学で使う様々な記号

pst-vehicle
…円の幾何学（２円の関係、曲率）、坂を走る車や自転車

pst-poly
…多角形

pst-platon
…多面体

pst-ode
…３次元グラフ

pst-math
…２次元グラフ

pst-geometrictools
…三角定規、分度器、コンパス、定規などのイラスト

pst-func
…グラフと棒グラフの融合

pst-eucl
…平面幾何

polynomial
…多項式を超絶簡単にかく

polynom
…多項式の割り算の筆算、組立除法、因数分解した式を計算して出してくれる

longdivision
…数の割り算の筆算

phfthm
…定理を記述する環境を整えてくれる

perfectcut
…様々な括弧を出力（多重になったときの大きさ調整も可能）

musikui
…数字の代わりに四角を用いて筆算の手順を説明

mfpic4ode
…ベクトル場を図示

mathtools
…シグマやlimの下に数式、複数行に渡る数式を見やすく配置、連立方程式のような形式で答えを場合分けして表示

mathfont
…あらゆる数学記号を出力、手書きボールド体アルファベットの出力

mathexam
…数学試験問題プリントの作成を補助

mathdots
…記号の上にドット（微分の表示など）

mathalpha
…数学で用いる様々なフォントのアルファベット

letterswitharrows
…記号の上に矢印（ベクトルの表示）

jkmath
…整数論や組合せ論の記号、ボールド体アルファベットを簡単に出力

hf-tikz
…数式を色付き枠で囲む

halloweenmath
…数式を超絶可愛く飾る

gn-logic
…論理式

gauss
…掃出し法の手順注釈

derivative
…微分記号を簡単に出力

diffcoeff
…微分記号を簡単に出力（特に熱力学で使う固定変数を明示した偏微分記号）

content
…あらゆる関数を簡単に出力、微分積分記号を簡単に出力、単位行列を簡単に出力、複素平面の記号を簡単に出力、組合せ論の記号を簡単に出力、整数論の記号を簡単に出力、テンソル、etc.
とにかく万能だから物理や数学のノートづくりには必須

commath
…様々な括弧つきの文字、微分記号、ノルムなどを簡単に出力

bropd
…括弧つきの文字、微分記号を簡単に出力

braket
…括弧つきの文字を簡単に出力

bigints
…ベクトルの積分記号を出力

autoaligne
…項を縦に揃えて数式をかく（式変形が分かりやすくて便利）

susy
…物理でよく使う文字を簡単に出力

physics
…あらゆる物理記号を簡単に出力
物理のノートづくりには必須

mandi
…様々な単位、ベクトル解析の定理式、熱力学の式、マクスウェル方程式を簡単に出力
物理のノートづくりには必須

simplewick
…同類項などを結ぶ線

微分法 学校で教えてくれないライプニッツ表記の基本

先日、知人から微分のライプニッツ表記に関する質問をいただき、この表記法を見直すとても良い機会となった。
素朴な疑問を抱かなくなってしまった数学人にとって、これほどためになる機会は存在しない。

そのときの解説資料を以下にまとめておく。

現在、微分法解説書を執筆している真っ最中だが、これをふまえてさらに加筆修正する予定。（草稿執筆段階で良質な質問をいただけたことは本当に幸運だ。もしも清書が終わった後だったら…orz）

『魔法をかけますよー』という合図の記号を演算子という。
演算子と何かをかけ算することは、その何かに魔法をかけることを意味する。
すなわち、演算子を『かける』ことで魔法を『かける』ことになる。日本語って秀逸ですね…

d/dxを左からかけられたものはxで微分される（微分という魔法がかかった）
d/dxを微分演算子という。

• - - - - - - - - - - - - - - - - ✄

y=f(x)のとき、(d/dx)f(x)は(d/dx)yとも表せる。
このとき、yを分子に乗せて略記したものがdy/dxである。

このように、dy/dxのyは形式的にdとは独立のものとみなすことも可能である。（本来はひとかたまりのものではあるが）

• - - - - - - - - - - - - - - - - ✄

d/dxを2回かけることは、指数の素朴な定義より、(d/dx)²をかけることとみなせる。
この意味で、2階微分はd²y/dx²と表される。

• - - - - - - - - - - - - - - - - ✄

ここで注意すべきなのは、dxはひとかたまりのものでしかないという認識の下、(dx)²をdx²と略記しているということである。
決してdを1つ、xを2つかけたというわけではない。

• - - - - - - - - - - - - - - - - ✄

以上のことをふまえると、写真のような変形が可能になる。
最後の式は、『dy/dx（xで微分して得た導関数）にさらに微分という魔法をかけた』ということを表す。
このように、2階微分とは『導関数を微分すること』ともみなせる。
上の写真の式変形を瞬時に行うには、次のように考えればよい。

• - - - - - - - - - - - - - - - - ✄

【発展事項】

『dy/dxは分数ではない』という言葉の真意は、次のようなものである。

・dyやdxは、本来ひとかたまりのものであるから、dとの積と考えてdを約分してはいけない。
・dy/dxは『dx分のdy』とは読まない。

この2点のみが重要なのであって、このことを『dy/dxは分数ではない』という言葉に含めてしまうことは適切ではない。
実際、dy/dx=f(x)の両辺にdxをかけて、dy=f(x)dxという表記をすることが大学数学ではよくある。理工学部であれば、微分方程式を解く際にこのような記法をよく用いる。このような表記を正当化する微分形式という数学の分野も存在する。（微分形式は、dy/dxというひとまとまりだけではなく、dyやdx単体にも意味をもたせようという分野である。）
そもそも、割線の傾きΔy/Δxにおいて、幅Δxを無限小にしたものがdy/dxであり、これが接線の傾きを表す以上、dy/dxはdyとdxの分数（比）なのである。…このことについては図解をつけて解説したものをClearに掲載したい。