人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

C言語で、unsigned longでも格納できないサイズの正の整数を扱う場合の一般的な方法を教えてください。
できれば、?コーディングが簡単、?計算量が少ないの両方か片方を満たす物が良いです。

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

●質問者: Moow
●カテゴリ:コンピュータ 学習・教育
✍キーワード:C言語 Project Euler Ruby コーディング サイズ
○ 状態 :終了
└ 回答数 : 5/5件

▽最新の回答へ

1 ● Vacuum
●25ポイント

UNIX 系なら、long long

WINDOWS系なら __int64 ですね。

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

◎質問者からの返答

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

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


2 ● keisukefukuda
●24ポイント

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

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

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

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

http://gmplib.org/

◎質問者からの返答

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


3 ● くまっぷす
●15ポイント

http://gmplib.org/

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

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

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

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

◎質問者からの返答

2番の方と同じですね。

ありがとうございます!


4 ● dev_zer0
●27ポイント

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

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

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

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

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

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

◎質問者からの返答

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

参考になります。


5 ● Vacuum
●10ポイント

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

◎質問者からの返答

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ