Moow回答ポイント 101pt

C言語で、unsigned longでも格納できないサイズの正の整数を扱う場合の一般的な方法を教えてください。

できれば、①コーディングが簡単、②計算量が少ないの両方か片方を満たす物が良いです。

【背景】
プログラムで数学・算数の問題を解くProject Eulerと言うサイトに挑んでいるのですが、100万未満の素数の総和を求めるプログラムをRubyで組んだら全く処理が終わりませんでした。
やむなく慣れないC言語でトライし結果が出たと思ったら答えが合いません。
検算すると、総和がunsigned longに格納できず桁あふれが起きていたようです。

※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。

ログインして回答する

みんなの回答

Vacuum2007/06/11 23:19:35
満足25pt

UNIX 系なら、long long

WINDOWS系なら　__int64 ですね。

http://seclan.dll.jp/c99d/c99d05.htm

スター
- Moow 2007/06/12 05:54:37
  
  あれ、そんなもの有ったんですか。
  
  恥ずかしながら知りませんでした。

keisukefukuda2007/06/12 00:10:55
満足24pt

条件を満たすかどうかはわかりませんが、メジャーなものとして

GNU GMP (GNU Multi Precision)があります。

任意精度で実数や整数の演算ができます。

http://www001.upp.so-net.ne.jp/tklab/linux/sci1a.html

http://gmplib.org/

スター

Moow 2007/06/12 05:56:35

任意精度数演算ライブラリですか、すばらしい！

くまっぷす2007/06/12 00:11:56
満足15pt

http://gmplib.org/

普通は多倍長演算ライブラリを使います。

http://taylor.gotdns.org/gmp.html

http://ayapin.film.s.dendai.ac.jp/~matuda/TeX/PDF/27th.pdf

などにちょっとだけですが使い方が出ています。

スター

Moow 2007/06/12 05:57:19

２番の方と同じですね。

ありがとうございます！

dev_zer02007/06/12 00:18:21
満足27pt

http://www.sra.co.jp/people/miyata/algorithm/multprec.txt

上記URLのように数値型の配列をあたかも一つの数値をして扱う

多倍長演算というのが一般的な方法です。

# 上記のソースはかなり古いものでintが16bitと仮定して

# shortと同じ16bitなのでshortの配列として組まれていますが、

# intかlongの配列にした方がよいと思います。

スター

Moow 2007/06/12 05:58:10

アルゴリズム的なアプローチですね。

参考になります。

Vacuum2007/06/12 09:15:07
満足10pt

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);

}

http://yahoo.co.jp

スター

Moow 2007/06/12 21:03:15

参考にします。ありがとうございます。

C言語で、unsigned longでも格納できないサイズの正の整数を扱う場合の一般的な方法を教えてください。

みんなの回答