kfujitoの徒然（ｂｙ浮沈子）

math compiler


Ｃ言語で、完全数を求めるプログラムを動かしたことは、既に書いた。

（速さは正義）
http://kfujito2.asablo.jp/blog/2017/05/10/8552087

しかし、これでは満足できない。

（８インチも1703へ）
http://kfujito2.asablo.jp/blog/2017/05/12/8555194

「完全数を求めるのに、エラトステネスのふるいを応用して、高速に計算するプログラムを見つけた。
（完全数）
http://www.saoyagi2.net/integer/perfect.html 」

このソースを読めない。

勉強不足だ。

で、とりあえず、エラトステネスのふるいを実装しているプログラムを探す。

（第 06 章　配列と文字列）
http://www.is.titech.ac.jp/compview/clang/chap6.html

このプログラム（つーか、演習問題）では、どうしてもwhileの外に出られなかったし、ｊとか怪しかったので、独自に書き直す。

#include <stdio.h>
#include <math.h>

int main() {
int i, j, n;
n = 1000;
/* 各整数が素数かどうかを記録する配列
0～nまでの値を管理するためn+1の要素の配列を定義している */
int flag[n + 1];

/* 最初はすべて素数とみなす
（フラグの値で）1は素数 0は素数でないと定義する */
for (i = 0; i <= n; i = i + 1) {
flag[i] = 1;
}

/* 0, 1は素数ではない */
flag[0] = 0;
flag[1] = 0;
/*ふるいはnの平方根まで*/
for (i = 0; i <= sqrt(n); i = i + 1) {
/* 1になっている最初の値を探す */
if (flag[i] == 1) {
/* iは素数のため素数の倍数の値をすべて0にする */
for (j = 2; (i * j) <= n; j = j + 1){
flag[i * j] = 0;
}
}
}

/* この時点で1となっている要素は素数である */
for (i = 0; i <= n; i = i + 1) {
if (flag[i] == 1){
printf("%d ", i);
}
}
printf("\n");

return 0;
}

突っ込みどころはあるんだろうが、とりあえず動くところまで持ってきた。

出力の整形とかは、全く考えていない。

問題だったのはコンパイルだ。

gcc -o hoge hoge.c

これだと、sqrtの引数に変数を入れるとコンパイルエラーになる。

自然数を引数にするとエラーを吐くとか、いろいろ調べたが、どうやらmathを読み込んでくる時にlmというオプションを付ける必要があるということが分かった。

しかもだ、ウブンツの場合（バージョンにもよるようですが）、末尾に付ける必要がある。

gcc -o hoge hoge.c -lm

これで、ようやく探索範囲の最大値を変数にぶち込んで、ふるいを掛けることが出来るようになった。

（C言語のコンパイルについて）
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12108453907

「試してみました。
ubuntu
$ cc -v
gcc バージョン 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
×cc -lm hoge.c
○cc hoge.c -lm」

ちなみに、浮沈子のＢＵＷの現在の環境では、gccのバージョンは5.4.0、ウブンツは16.04.4になっている。

Ｃのコード自体のミスもあって、見つけ出すのに苦労したが、なんとかmath使ってコンパイラーを通すことに成功した。

マスかいて、疲労こんぱい（らー）・・・。

子供は、分かんなくていいです！。

まあ、どうでもいいんですが。

さて、この先は、いよいよ本丸の完全数の探索に、この仕掛けを応用するという話になる。

先が思いやられるな・・・。