int型の最大値を超えた数値を扱いたい 方法を教えて下さい

Question

プログラムの勉強のために(特にこれである理由はありませんが)大きな桁の数値で素数を求めるアルゴリズムを書いてみたいです。
エラトステネスの篩は出来ました。
方針としては(これも知恵袋で見た方法なのですが笑)
①まずint配列の最大要素数分の素数をエラトステネスの篩で求める。
②それをもとにに10桁の素数判定を行う。

というようにしたいです。

そこで10桁はint型からギリギリ溢れてしまうと思うので、そういう値を扱うにはどうしたら良いんだろうと思い質問させていただきました。

正直アルゴリズムの方ももっといいのあるのであれば教えていただきたいです。

よろしくお願いします。

素数か判定するアルゴリズムでもいいです。

Answer 1

多倍長演算ライブラリーをつかうと、ものすごくたくさんの桁数の処理を行えます。

参考：

• 多倍長演算により300! - 100! + 200!を計算する http://katahiromz.web.fc2.com/c/bigfact2.html
• 多倍長整数 http://boostjp.github.io/tips/multiprec-int.html
• 多倍長浮動小数点数 http://boostjp.github.io/tips/multiprec-float.html

google 検索すると、多倍長演算ライブラリー について、たくさんの情報を得ることができます。

素数判定については、次のページを紹介しておきます。

• GMPライブラリを使ってC言語でフェルマーテスト（合成数判定関数）を実装 http://blog.enoz.jp/16

...
例えば、((2^61)-1)^2 = 5,316,911,983,139,663,487,003,542,222,693,990,401 なんていう数は、冒頭で示したような Brute Force アルゴリズムではかなり辛いものがあるが、これは合成数なのでフェルマーテストを使うと一瞬で合成数だと見抜ける。
...

Comments

[akamakku]

こういうのがほしかったんです！！！！
ありがとうございます！！！

Answer 2

long int とか有りましたね笑

Answer 3

int の代わりにlongを使えば良いと思います。
整数ではlongが一番大きな範囲だと思います。
http://www.javadrive.jp/start/var/index4.html

Comments

[akamakku]

Javaのlong型ってとてつもなくでかいんですね！