できれば、①コーディングが簡単、②計算量が少ないの両方か片方を満たす物が良いです。
【背景】
プログラムで数学・算数の問題を解くProject Eulerと言うサイトに挑んでいるのですが、100万未満の素数の総和を求めるプログラムをRubyで組んだら全く処理が終わりませんでした。
やむなく慣れないC言語でトライし結果が出たと思ったら答えが合いません。
検算すると、総和がunsigned longに格納できず桁あふれが起きていたようです。
条件を満たすかどうかはわかりませんが、メジャーなものとして
GNU GMP (GNU Multi Precision)があります。
任意精度で実数や整数の演算ができます。
任意精度数演算ライブラリですか、すばらしい!
普通は多倍長演算ライブラリを使います。
http://taylor.gotdns.org/gmp.html
http://ayapin.film.s.dendai.ac.jp/~matuda/TeX/PDF/27th.pdf
などにちょっとだけですが使い方が出ています。
2番の方と同じですね。
ありがとうございます!
http://www.sra.co.jp/people/miyata/algorithm/multprec.txt
上記URLのように数値型の配列をあたかも一つの数値をして扱う
多倍長演算というのが一般的な方法です。
# 上記のソースはかなり古いものでintが16bitと仮定して
# shortと同じ16bitなのでshortの配列として組まれていますが、
# intかlongの配列にした方がよいと思います。
アルゴリズム的なアプローチですね。
参考になります。
100万未満の素数の総和を求めるプログラム
は以下のコーディングで簡単に求められます。(ご参考に)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
__int64 Souwa = 0;
void main(void) {
int ix,iy,iz,max;
char str[32];
printf("総和を求める素数の範囲を入力してください(~20億までよ");
fgets(str,sizeof(str),stdin);
max = atoi(str);
printf("2\n");
for(ix=3;ix<=max;ix+=2) {
for(iy=3,iz=0;iy<=sqrt(ix);iy+=2) {
if (!(ix%iy)) { iz=1; break; }
}
if(!iz) {
Souwa += ix;
}
}
printf("素数の総和は%I64uです。\n",ix);
}
参考にします。ありがとうございます。
あれ、そんなもの有ったんですか。
恥ずかしながら知りませんでした。