C言語関係掲示板

過去ログ

No718 大きな数の素数を求める方法

[戻る] [ホームページ]
No.8687

大きな数の素数を求める方法
投稿者---ばらばら(2003/07/30 16:40:02)


素数の質問のレスNo.8630で
intの最大値を超えてしまうと述べられていますが
最大値を超えてしまうような数の素数(素数はたくさんあるのでその中でも最大の素数)を
求めるようなプログラムってありませんか?
配列使って多倍長見たいな感じでやってみたんですが上手く行かず、、、
気になって眠れません! よろしくお願いしますm(_ _)m


No.8689

Re:大きな数の素数を求める方法
投稿者---たいちう(2003/07/30 17:14:04)


> 最大値を超えてしまうような数の素数(素数はたくさんあるのでその中でも最大の素数)を

素数が無限にあることはご存知ですか?
最大の素数というものは存在しません。

> 求めるようなプログラムってありませんか?
> 配列使って多倍長見たいな感じでやってみたんですが上手く行かず、、、
> 気になって眠れません! よろしくお願いしますm(_ _)m

どの素数を求めたいのか判りませんが、100億を超えない最大の素数を
求めることなどは難しくありません。100億-1、-2、-3、、、を
多倍長で表して候補とし、素数かどうかの判定をします。
最初にみつかった素数が100億を超えない最大ですので。

多倍長でその判定はできますので、上手くいかなかったのは多倍長を使いこなせて
なかったか、前提がどこか間違っていたんでしょう。

これで眠れます?

No.8690

Re:大きな数の素数を求める方法
投稿者---ばらばら(2003/07/30 17:33:19)


最大値を超えてしまうような数を90億と設定して試してました。
説明不足でした、申し訳無い。

その「多倍長での素数判定」というのを見せてもらえませんか?
配列を使うのは知っているのですが、イマイチ実装方法というか実現するのが難しくて、、、
各桁ごとの数を見て割っていく、という感じなんでしょうか、、、

No.8692

Re:大きな数の素数を求める方法
投稿者---たいちう(2003/07/30 17:46:20)


> その「多倍長での素数判定」というのを見せてもらえませんか?

アルゴリズムはint型の場合と同じで、変数が多倍長になるだけ。
プログラムも作れるという強い確信はあるけど、
作ったこともないし作るつもりもありません。興味はないもので。
上手くいかなかったソースを見せてもらえれば、アドバイスは
できると思いますが。

# int型と同じアルゴリズムっていっても、間違っても篩なんか
# 使わないように。

No.8695

Re:大きな数の素数を求める方法
投稿者---かずま(2003/07/30 18:20:47)


> 最大値を超えてしまうような数を90億と設定して試してました。

double を使うと、9007兆1992億5474万0992までの整数を扱えます。
#include <stdio.h>
#include <math.h>

int main(void)
{
    double i, j, k;

    for (i = 9000000000.0; ; i--) {
        k = sqrt(i);
        for (j = 2; j <= k; j++)
            if (fmod(i, j) == 0) break;
        if (j > k) break;
    }
    printf("%.f\n", i);
    return 0;
}


No.8792

Re:大きな数の素数を求める方法
投稿者---塗り壁(2003/08/04 13:15:20)


>
>double を使うと、9007兆1992億5474万0992までの整数を扱えます。

この数字の根拠を教えてもらえますか。それから、浮動小数点の扱える範囲は
処理系依存のはずですがどの処理系での話でしょうか。
あと、先頭の質問と重なるかもしれませんが誤差が出ない事は度のように保証されるのでしょうか。

No.8794

Re:大きな数の素数を求める方法
投稿者---かずま(2003/08/04 19:29:09)


>> double を使うと、9007兆1992億5474万0992までの整数を扱えます。
>
> この数字の根拠を教えてもらえますか。それから、浮動小数点の扱える範囲は
> 処理系依存のはずですがどの処理系での話でしょうか。

9007兆1992億5474万0992 は、 2 の 53乗です。
IEEE754規格を採用している処理系なら、仮数部が 52ビットで、さらに隠れた
1ビットがあるので、精度は 2進で 53ビットです。
53ビットがすべて 1 の整数は、9007兆1992億5474万0991 です。
9007兆1992億5474万0992 は、1 のあとに 0 が 53個ついて、全部で 54ビット
ですが、最後の桁が 0 なので、浮動小数点数としては表現可能です。
9007兆1992億5474万0993 は、1 と 1 の間に 0 が 52個ついて、全部で 54ビット
なので、IEEE754規格では表現できません。

指数が 16のべき乗である IBM のメインフレームではそうなりません。
また、DEC の PDP-11 や VAX-11 も IEEE754 とは異なるフォーマットです。

現在では、ほとんどすべての PC やワークステーション、PDA に IEEE754規格が
採用されています。


> あと、先頭の質問と重なるかもしれませんが誤差が出ない事は度のように
> 保証されるのでしょうか。

浮動小数点で誤差が出るのは、小数部分についてです。
精度の範囲内の整数部分に誤差はありません。もちろん、精度以上の桁数を
持つ整数は下位の部分が 0 になるので、正確な値にはなりません。

No.8795

Re:大きな数の素数を求める方法
投稿者---たいちう(2003/08/04 19:55:22)


> > あと、先頭の質問と重なるかもしれませんが誤差が出ない事は度のように
> > 保証されるのでしょうか。
>
> 浮動小数点で誤差が出るのは、小数部分についてです。

失礼ながら少しナイーブなのではないかと思います。
double型で一時的に9000兆以上の数字を誤差なく表せるということと、
fmodを使って剰余を誤差なく計算できるということとは違うでしょう。

でも反論の根拠が希薄なので、考察・調査・実験してみます。
補足説明いただけるならよろしくお願いします。

No.8868

Re:大きな数の素数を求める方法
投稿者---塗り壁(2003/08/07 19:43:34)


たいちうさん、フォロー有り難う御座います。
適当にサンプルを作ってやってみたところでは
fmodは誤差無しで動いたようです。
中間ワークの問題が有りそうな気がしたのですが
どうやら杞憂のようですね。
(よく考えたらこれで誤差が出たらfmodの存在価値は無いですよね)
私は、誤差の無い計算は整数演算に限るという思い込み
に捕らわれていたみたいですので、必要に応じて
(勿論誤差には気を付けながら)浮動小数点計算も
併用していこうと思っています。
かずまさん、御教授どうもありがとう御座いました。