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

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

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

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2007/06/11 22:55:53
  • 終了:2007/06/12 21:07:27

回答(5件)

id:Vacuum No.1

Vacuum回答回数54ベストアンサー獲得回数42007/06/11 23:19:35

ポイント25pt

UNIX 系なら、long long

WINDOWS系なら __int64 ですね。

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

id:Moow

あれ、そんなもの有ったんですか。

恥ずかしながら知りませんでした。

2007/06/12 05:54:37
id:keisukefukuda No.2

keisukefukuda回答回数14ベストアンサー獲得回数02007/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/

id:Moow

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

2007/06/12 05:56:35
id:Kumappus No.3

くまっぷす回答回数3784ベストアンサー獲得回数1852007/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

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

id:Moow

2番の方と同じですね。

ありがとうございます!

2007/06/12 05:57:19
id:dev_zer0 No.4

dev_zer0回答回数332ベストアンサー獲得回数252007/06/12 00:18:21

ポイント27pt

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

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

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

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

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

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

id:Moow

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

参考になります。

2007/06/12 05:58:10
id:Vacuum No.5

Vacuum回答回数54ベストアンサー獲得回数42007/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

id:Moow

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

2007/06/12 21:03:15

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません