はじめに

C言語初学者でもわかるように、素数判定プログラムを書きながらC言語を理解できるように解説したつもりです。
令和の時代にC言語を学ぶ方なんて数少ないと思いますので、この文章を読んでくださっているだけでめちゃくちゃ嬉しいです。

対象者

C言語で四則演算、hello worldはなんとなくわかる
素数判定プログラムの書き方を知りたい
関数の書き方がわからない
main関数ってなに
コマンドライン引数って何
ポインタって何、配列って何
オーバーフローって何
計算量って何

な人です。全部に当てはまらなくても大丈夫です。

結構長いかも知れません。素数判定のプログラムは一番下にあるので、時間ない方は一番下にある完成コードだけ見ていってください。
時間がある方も、リラックスして、テキトーに興味ある章から見ていってください。

C言語実行環境

主はMacBookAirにデフォルトで入っているやつを使っています。
下記コマンドでバージョン情報が出てきたら一緒の方法でできます。

$ clang --version

コンパイルオプションはclang ファイル名

$ clang test.c

デフォルトではa.outという実行ファイルができるので、

$ ./a.out

で実行します。
clangコンパイラがない,方、特にwindowsユーザの方は別のやり方をしましょう。
コンパイラをインストールするのは手間なので、paiza.ioを用いてWEBブラウザ上で実行できるので試してみてください。

変数とか型について

変数ってのは、何かしらの値を入れておく場所？みたいなものです。
コンピュータでは、何かしらの値をメモリっていう場所のどこかしらに保存します。
C言語では、変数の型名変数名というふうに宣言をします。

char c;

これは、char型の大きさの領域をメモリ上に確保して、その領域にcっていう名前をつけていることになります。
char型には1文字だけ入れることができます。シングルクオーテーションで囲ってあげましょう。

char c;
c = 'a';

c言語ではもともと実装されているデータ型が複数あります。これを組み込みデータ型といいます。
ここに書くのが面倒だったので、気になる人は下記の記事など見てみてください。
今回は基本的にcharとintしか使いません。

素数とは

念の為、素数っていうのは、１か自分以外の数で割り切れない数字のことです（多分）
例）2,3,5,7,13,17,23,57

基本ロジック

プログラムを使わずに素数かどうか愚直に判定しようとするのであれば、
まずは頭の中でやっていることを書き起こします。
例えば11を判定したい時、
11 % 2 != 0 (11を2で割ったあまりが0出ないので、2は11の約数ではない)
11 % 3 != 0
11 % 4 != 0
.
.
.
11 % 10 != 0
結果、一度も11と1以外の数で割り切れてないので11は素数！と言える。
つまり、Nという数字が与えられたときに、2からN未満の数字までで割り続けて、途中で一回も割り切れなかったら素数と言えるってことです。
途中で同じ動作を繰り返しているので、これをfor文を使って実装すれば良いです。

「％」という記号が出てきました。
a % b
と書くことで、a を bで割った余りを求めることができます。

素数判定用の関数

これが、先ほどの日本語をプログラムに直したものになります。

int	is_prime(int n)
{
	for (int i = 2; i < n; i++)
	{
		if (n % i == 0) return (0);
	}
	return (1);
}

今、関数ってものを作りました。関数の書き方について説明します。
まず、左上には、返り値の型を書きます。今回は、素数なら1、素数でないなら0というふうに整数値を返したいと思うので、intとします。
次に関数名 (引数の型名引数名)を書きます。
あとは波括弧{}で囲って大枠の完成です。
大枠ができたら中に好きなようにプログラムを書いて、最後にreturn 値で値を返します。
引数っていう何かしらの値を受け取って、こねくり回します。その後こねくり回した結果の値(=返り値)を、元のプログラムに返します。
関数内でreturn文を書くと、その時点でその関数は終了します。
そのため、以下の関数は1を返します。

int tadanoichi(int n)
{
    n = 1;
    return (n);
    //ここから先は実行されませーん
    n = 19411208
    return (n);
}

関数によっては、引数も返り値も不要な時があります。その時はvoidと書きます。

void nyaa(void)
{
    /*
    ここに何かしらの処理を書く。
    */
}

C言語のコメントアウトについて

１行のみのコメントアウトであれば//をつけます。

// この文章は実行されません

複数行コメントアウトしたい場合は、/*と*/で囲ってあげれば良いです。

/*
ここは
実行されません
*/

main関数とコマンドライン引数

先ほど、せっかく素数判定プログラムを作ったので実行してみたいです。ただ先ほどのプログラムのみをコンパイルしても動きません。
C言語の特徴として、プログラムを動かすにはmain関数が必要だからです。
main関数は基本的には数値の0を返り値としています。
0を返すことで正常にプログラムが終了したことを意味します。(多分)
引数はあってもなくても良いです。
なので以下のような形になることが多いです。

int main(void)
{
    /*
    ここに何かしらの処理を書く。
    */
    return (0);
}

では実際に、素数判定用のis_prime関数を実行できるよう、main関数を書いてみます。

#include <stdio.h>
#include <stdlib.h>

int	is_prime(int n)
{
	for (int i = 2; i < n; i++)
	{
		if (n % i == 0) return (0);
	}
	return (1);
}

int	main(int argc, char **argv)
{
	if (argc != 2) return (0);

	int n = atoi(argv[1]);
	if (is_prime(n))
	{
		printf("%d is prime number\n", n);
	}
	else
    {
        printf("%d is not prime number\n", n);
    }
	return (0);
}

ここで、よくわからないargcだの**argvだのが出てきました。
今回は、コマンドライン引数ってやつで数値を受け取って、その数値が素数かどうか判定しようとしています。
main関数の引数が2個あって、それぞれがint argc, char **argvってなってます。
変数ってのは型名名前で定義されるので、argcもargvも自由に変更できる名前です。
今回は
argc == argument count(引数の数)
argv == argument vector (引数の配列)
という意味で名付けています。
C言語ではコンパイルした後にa.outのようなファイルが生成されます。
実行するには、./a.outと書きます。
この際に、./a.out 57としたら、./a.outという引数と、57という引数の合計2つの引数が与えられるので、int argcの中身は2になります。
この2つの引数こそが、コマンドライン引数です。
この時、./a.outも57も、両方とも文字列として扱われています。

Question : main関数がないと実行できないなら、いちいち別の関数を書かずにmain関数の中に全て処理を書けばいいのでは？
Answer : 「今だけ、自分だけ」のコードならそれでも良いです。
main関数に全部書いてしまうと、コードが見た目上汚いです。
チーム開発を行う際は、他人にとってみやすいコードを心がける必要があります。
他人っていうのは未来の自分も含まれます。
自分が書いたコードでも、数ヶ月経てば解読に時間がかかってしまうことがあります。

main関数の返り値について、下記サイトでめちゃくちゃわかりやすく記述されていました。興味のあるかたは是非。

C言語の文字と文字列

そもそも文字列って何でしょう？
文字列は、文字の配列を意味します。
C言語での文字は、charという型を使って表現できます。char型のデータには、1バイトの大きさのデータを入れることができます。
1バイトっていうのは8bitの大きさのデータになります。
じゃあ1bitではどんな情報が表せるのかっていうと、0か1の2つになります。これが8個あると、2の8乗 = 256個の情報を表すことができます。
00000000~11111111つまり、10進数で0~255までの合計256通りの整数値を表すことができます。
asciiコードと呼ばれる文字の対応表には、0番から127番までの文字が対応付されています。

char c = 'a';
のように、シングルクオーテーションで囲うことで、文字を代入することができます。
コンピュータの内部的に何が起こっているかっていうと、
char cって宣言したときに、メモリ上に1バイト分の領域が確保されて、その領域の名前をcとしています。
その後、cっていう名前の場所に、'a'を入れたいのですが、コンピュータは数値しか扱えないので、asciiコード上で'a'は97番目にあることから、cっていう場所には97っていう数値が保存されます。(正確には2進数に変換されたもの)

文字列は文字の配列です。
配列っていうのは、メモリ上の連続した領域に場所を確保して、順番に値を入れることができるデータの形です。（厳密な言葉の定義は特に意識せず書いてます）
C言語で配列のデータをどうやって管理するかというと、連続した領域にメモリを確保した際に、その先頭の場所の情報(=アドレス)を保存することで対応します。
場所の情報をどうやって保持するかっていうと、ポインタっていう変数の型を使います。

char * pointer;

これで、pointerっていう名前の変数が出来上がって、さらにいうと、char型のデータの場所の情報を格納することができます。
つまり、あるデータのアドレス(=住所)を格納することができる変数を、ポインタっていいます。多分。
ポインタ変数の宣言は、型名と変数名の間にアスタリスク*をつけるだけです。スペースの位置とかはどうでもよくて、以下3つは同じ意味です。

char* pointer;
char *pointer;
char*pointer;

じゃあ場所の情報をどうやって渡すのかっていうと、変数名に&をつけてあげます。
もしくは、ダブルクオーテーション""で文字を直接囲ってやることでできます。

char c = 'a';
char *pointer;
pointer = &c;
//または
pointer = "a";

このように、char * pointerでポインタ変数を宣言した時、char *までは変数の型名だと思っておけば大丈夫です。

配列の話をする際にポインタの話をしてしまいました。
それは先ほど伝えた通り、
配列っていうのはメモリ上の連続した領域に場所を確保して、順番に値を入れることができるデータの形であって、C言語で配列のデータをどうやって管理するかというと、連続した領域にメモリを確保した際に、その先頭の場所の情報(=アドレス)を保存することで対応する。
からです。

また、以下２つはほぼ同義で、stringという名前の変数には、連続して確保されたメモリの先頭のアドレスが格納されます。

char *string;
char string[];

[]の中に数値を入れることで、何個の領域を確保すればいいか教えてあげることができます。
以下の表現では、メモリ上に連続した3バイトの領域を確保し、その先頭のアドレスの情報を格納する変数にstringという名前をつけています。

char string[3]

文字の配列をC言語で表現すると、下記のような書き方ができます。

char *string1 = "aiueo";
char string2[] = "aiueo";
char string3[5];
string3[0] = 'a';
string3[1] = 'i';
string3[2] = 'u';
string3[2] = 'e';
string3[2] = 'o';

//string1 : aiueo
//string2 : aiueo
//string3 : aiueo

こうなります。文字の並びをダブルクオーテーションで囲うことによって、文字が格納されている場所の先頭アドレスを意味します。
文字列の説明をしたのは、コマンドライン引数で受け取った際に、その入力を文字列として扱うからでした。
でも今回は
char *argcではなく、char **argvです。
前者は文字列の先頭アドレスを格納することができ、後者は文字列の先頭アドレスのアドレス等を格納することができます。
ポインタのポインタってことです。説明しようとすると骨が折れたのでまた今度にします。
例として、日本語の50音の表を配列で表現してみたいと思います。
string1 = "aiueo";
string2 = "kakikukeko";
string3 = "sasisuseso";
...
string10 = "wawonn";
これらのstring{number}ってのはそれぞれが文字の配列です。なのでこれらの情報をまとめて扱おうと思ったら、配列の配列を用いる必要があります。
どうやって実装するかっていうと、string1のアドレスからstring10までの全ての場所の情報＝＝アドレスを格納すれば良いです。
アドレスを格納するときに、場所の情報も順番通りに格納したいです。
順番通りに格納したい時は配列っていうデータ構造を使います。
配列っていうのは、メモリ上の連続した領域にデータを保存できるからです。
配列ってどうやって実装するかっていうと、それぞれのデータのアドレスを保存するんでした。
つまりポインタのポインタってことです。
ポインタ変数は変数の型名と変数の間に*を入れてました。
ポインタのポインタ変数は、型名と変数の間に*を2つ入れれば良いです。
以下の3つはほぼ同じ意味です。文字の配列の配列のデータを入れることができます。

char **c;
char *c[];
char c[][];

見覚えがあるやつがありますね。
char **argvです。
コマンドライン引数で、./a.outっていう文字列と57っていう文字列を受け取って、
char **argvっていう文字列の配列に格納することができます。
./a.outっていう文字列と57っていう文字列にどうやってアクセスするかっていうと、下記になります。

argv[0] 
// ., /, a, ., o, u, tっていう文字がメモリ上に連続して並んでいて、それの先頭アドレスを表している状態。
argv[1] // 57が入ってる
// 5, 7って文字がメモリ上に連続して並んでいて、それの先頭アドレスを表している状態。

argv[0][0]
// 「.」を意味しています。0番目の文字列の0番目の要素にアクセスしています。
argv[1][1]
// 「57」を意味しています。1番目の文字列の1番目の要素にアクセスしています。

深くは言及しませんが、C言語では文字列を扱う際に、文字を連続してメモリ領域に並べた際の、先頭のアドレスを用いて処理を行っています。

ポインタと配列について。
ポインタ(*)があれば配列が扱える。
ダブルポインタ(**)があれば二次元配列が扱える。
ざっくりこんな認識で良いのではないでしょうか。

入出力

少し話を戻します。先ほど書いたmain関数のプログラムです。

#include <stdio.h>
#include <stdlib.h>

int	main(int argc, char **argv)
{
	if (argc != 2) return (0);

	int n = atoi(argv[1]);
	if (is_prime(n))
	{
		printf("%d is prime number\n", n);
	}
	else
    {
        printf("%d is not prime number\n", n);
    }
	return (0);
}/.-.

ここでは、
#include <stdio.h>
#include <stdlib.h>
という2つのヘッダファイルをインクルードしています。
インクルードすることで、このヘッダの中に定義された関数を使えるようになります。
今回stdio.hでprintf関数を、stdlib.hでaoti関数を使えるようになっています。
printf関数はいろんなものを文字として扱って、出力することができます。
プログラマーが使ってる黒い画面があるじゃないですか。その画面に表示されている場所を標準出力っていいます。入力する際の場所を標準入力っていいます。どちらの場所にも、文字の情報が表示されます。
今回素数判定プログラムということで数値を入力したいんですが、入力した値は文字列として扱われちゃうので、整数に変換したいです。そのときにatoi関数の出番です。
atoi("12345");
とすると、12345っていう文字列が12345っていう数値として扱えるようになります。
出力をするときはprintf関数を使います。

printf("%d is prime number\n", n);

ここで、基本的にはダブルクオーテーションで囲った文字列を表示させることができます。
その文字列の中に、%dと入れることで、数値の情報を出力させることができます。
カンマで区切った右側に、出力したい整数の情報が入っていたnを書いてやることでおkです。

休憩

ここまで読んでくださった方、お疲れ様です。今日はもう寝て大丈夫です。しっかり休んでください。

実行してみる

プログラムは書いたけど実行するの忘れてました。先程書いたやつが下で、これを実行したのがさらに下です。

#include <stdio.h>
#include <stdlib.h>

int	is_prime(int n)
{
	for (int i = 2; i < n; i++)
	{
		if (n % i == 0) return (0);
	}
	return (1);
}

int	main(int argc, char **argv)
{
	if (argc != 2) return (0);

	int n = atoi(argv[1]);
	if (is_prime(n))
	{
		printf("%d is prime number\n", n);
	}
	else
    {
        printf("%d is not prime number\n", n);
    }
	return (0);
}

実行結果

$ ./a.out 4
4 is not prime number
$ ./a.out 7
7 is prime number
$ ./a.out 57
57 is not prime number

最初に例で挙げた57が素数じゃないと判定されてしまいましたね。これはコードが間違っているのでしょうか？
57が素数かどうか手で計算するのもしんどいので、プログラムを改変して約数を表示させるようにしてみます。

#include <stdio.h>
#include <stdlib.h>

int	is_prime(int n)
{
	for (int i = 2; i < n; i++)
	{
        //下記の返り値を0ではなくiに変更
		if (n % i == 0) return (i);
	}
	return (1);
}

int	main(int argc, char **argv)
{
	if (argc != 2) return (0);

	int n = atoi(argv[1]);
	if (is_prime(n) == 1)
	{
		printf("%d is prime number\n", n);
	}
	else
    {
        printf("%d is not prime number\n", n);
        //約数はis_prime(n)と、n/is_prime(n)で2つわかります。
        printf("divisor are %d and %d\n", is_prime(n), n / is_prime(n));
    }
	return (0);
}

これで５７についてもう一度調べます。

$ ./a.out 57
57 is not prime number
divisor are 3 and 19

なんと、57は3と19で割り切れちゃうので、素数じゃないようです。びっくりしました。
そいういえばどこかのYoutuberが、過去の大学受験時に受験票に書いてある受験番号が2153だったので、素数なのかどうか気になって計算しまくって時間を浪費したと言っていました。一応確認してみます。

$ ./a.out 2153
2153 is prime number

素数だったようです。。。

オーバーフローと計算量

今書いてるのが深夜3時で相当眠いです。
ここでクイズです。

intは何バイトの情報を入れられる型でしょうか。
intは何ビットの情報を入れられる型でしょうか。

正解は、4バイトで32ビットです。
じゃあint型の最小値、最大値っていくらでしょうか。
int型はプラスマイナスの情報を表すので、32ビットの中の先頭のビットについてはプラスかマイナスかの情報を表します。
とすると、int型のプラス(0を含む)の情報は、2の31乗個の情報を表すことができるので、
0から2の31乗マイナス1までの数を表すことができます。
つまり、int型の最大値は2の31乗マイナス1です。
例の黒い画面でbcコマンドを使って計算してみます。

$ bc
>>> 2^31 - 1
2147483647

これで、int型の最大値は2147483647だとわかりました。
マイナスの値は、0を含まないので、1から2の31乗まで表すことができます。
よって、int型の最小値は、-2147483648です。

$i n t$ : $32 b i t 整数$
$- 2^{31}$ $\leq$ $n$ $\leq$ $2^{31} - 1$
$- 2.1 \times 10^{9}$ $\leq$ $n$ $\leq$ $2.1 \times 10^{9}$
$- 2147483648$ $\leq$ $n$ $\leq$ $2147483647$

じゃあこのint型の最大値である2147483647って素数かどうか気になりませんか？
先程素数判定プログラムを作ったので、実行してみましょう。

$ ./a.out 2147483647
2147483647 is prime number

おおお！！！素数でしたね！！！
でもなんか、実行する時ちょっと重そうでした。
timeコマンドを使って時間を測ってみます。

$ time ./a.out 2147483647
2147483647 is prime number
./a.out 2147483647  2.50s user 0.00s system 99% cpu 2.517 total

主はMacBookAirのM2チップのPCを使っていますが、2.5秒もかかっています。
話それますが、AtCoderっていうプログラミングサイトでは、実行時間が2秒以内っていう制限があります。
今回のプログラムではバツを喰らっちゃいますね。
だいぶ前に、2153が素数かどうか判定するプログラムを書いたじゃないですか。
あれってプログラム的には、2,3,4,5...って順番に割り算をしていって、
最後2152で割れないことを確認した上で2153 is prime numberって出力したんですよ。
今のプログラムの状態だと、入力した数がNだと、そのままほぼN回計算することになっちゃいます。
計算量的にいうと、 $O (N)$ (オーダーエヌと読む)ってことになります。
オーダーうんたらについては以下のような記事を明日以降読んでみてください。

愚直にN回計算するプログラムを回すと、数が大きくなったときに実行時間が長くなってしまうので、プログラムを改良してみようと思います。

そろそろ思考できない脳みそになってきたので、結論から言います。
10が素数かどうか判定するには、1から9までで割り続ける必要はなく、1から√10までで良いです。なぜかは忘れました。ネット上で証明している人がいるのでまだ体力がある人は調べてみてください。
今までN回計算していたものを、√N回しか計算しなくて良くなりました。
計算量のグラフをqiita上で見つけたので、下記の記事は絶対見てください。絶対。

ということでこれを踏まえてプログラムを改良していきます。

int	is_prime(int n)
{
    //i <= √n という表現を、i * i <= n　で表現しています
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0) return (0);
	}
	return (1);
}

改良しました。
じゃあこれでまたコンパイルして実行してみます。

$ ./a.out 3
3 is prime number
$ time ./a.out 2147483647
2147483647 is not prime number
divisor are 2147483647 and 1
./a.out 2147483647  7.58s user 0.01s system 98% cpu 7.702 total

はい、なんか壊れちゃいました。。。。
3だとうまくいきましたが、2^31-1だとうまくいきません。先程は2.5秒で実行できて結果もあってたのに。。。。

ということで本題のオーバーフローってやつの説明に入ります。
今回はこのオーバーフローってやつが原因で壊れちゃいました。
先程改良したコードに注目しましょう。

for (int i = 2; i * i <= n; i++)

この部分になります。
このfor文がいつ終わるかっていうと、i * iの値が、n自身を超えた時です。
じゃあnが2147483647だったらどうなるかっていうと、
i * iの値が214783648以上になったら終わります。
でも、int型の最大値が2147483647なので、2147483648以上の数値は扱えないんですよ。
int iの中身がint型の値に収まりきらなかった時、オーバーフローってやつがおきます。
C言語の場合、
int型の最大値 + 1 => int型の最小値 つまり 2147483647 + 1 => -2147483648
int型の最小値 - 1 => int型の最大値 つまり -2147483648 - 1 => 214743548
っていうふうにループします。怖いですね。

先程のfor文に戻って解決策を提示します。

for (int i = 2; i * i <= n; i++)

解決策1

iがint型(4バイト)だからダメだったので、8バイト対応できるlong long型に変えてみる。

for (long long i = 2; i * i <= n; i++)

解決策2

i * i <= nの両辺をiで割って、i <= n / iにする。

for (int i = 2; i <= n / i; i++)

です。このどちらかで実装することで、オーバーフローを防げます。

実行結果

$ time ./a.out 2147483647
2147483647 is prime number
./a.out 2147483647  0.00s user 0.00s system 1% cpu 0.252 total

はい。totalで0.2秒で実行でき、答えもあっています。これで解説は終わりにします。(現在AM4:00)

完成コード

ちょっと今までのと変えてるとこあります。 m

#include <stdio.h>
#include <stdlib.h>

//素数の時1を返す。1以下の時は、0を返す。それ以外は、はじめに割り切れた約数を返す
int	is_prime(int n)
{
	if (n <= 1) return (0);

	for (long long  i = 2; i * i <= n; i++)
	{
		if (n % i == 0) return (i);
	}
	return (1);
}

void	print_error(void)
{
	printf("input valid error\n");
}

int	main(int argc, char **argv)
{
	if (argc != 2)
	{
		print_error();
		return (0);
	}
	int n = atoi(argv[1]);
	if (n < 0)
	{
		print_error();
		return (0);
	}
	if (n == 1)
	{
		printf("1 is not prime number\n");
		return (0);
	}

	if (is_prime(n) == 1) printf("%d is prime number\n", n);
	else
	{
		printf("%d is not prime number\n", n);
		printf("divisor are %d and %d\n", is_prime(n), n / is_prime(n));
	}
	return (0);
}

最後に

最後まで読んでいただきありがとうございます。
ちなみにint型の最大値である2147483647って $2^{31} - 1$ じゃないですか。
$2^{n} - 1$ の形で表すことのできる素数のことをメルセンヌ素数っていうらしいです。
かわいい名前ですね。
誤字脱字とか、そもそもコードのロジックとか、説明書きの文章が間違っている可能性があります。
間違い等見つけましたらコメントや編集リクエスト等よろしくお願いします。

あとがき(感想)

記事を書くときに、他サイトも引っ張ってくるんですけど、その他サイト見るたびに、これ見ればいいじゃん(自分が書く必要ないじゃん)ってなりますw
今の時代、自分で文章書く能力よりも、いろんな記事とかソースをいい感じにまとめるっていう能力の方が重要そうですね。
今回記事を書いていく中で、前に勉強したことの復習になったり、新たな発見を得られたり、今後勉強しておきたい部分が見つかったりしたので、まだqiita書いたことないって方も是非書いてみてください。

【C言語】素数判定書きながらC言語に入門してみる