素数を探すプログラム…。

質問

今作っているプログラムで素数を使用したいのですが、素数を探すプログラムが分からなくて困っています。

どなたか初心者の私にも分かるプログラムを教えていただけませんか？
（VB自体には素数を探す関数とか持っていないのでしょうか…？）

お願いします。

(P.S)本当は出来るだけ多く探したいのですが確か無限にあるんですよね…。

回答No.2

wolv · ベストアンサー

とても大きな数字について、素数であるかどうかを判定するのは、効率のよい方法はなかったと思います。現在でもときどき、
「「2の63乗-1」が素数であることが確認された」
などのような素数に関することがニュースになることがあるぐらいです。
（上の値は適当に書いた値なので、本当に素数かどうかは知りません。）

ある程度小さい数字が素数かどうか判定する場合は、その数の平方根程度までの奇数で割り切れるかどうかを順にすべて調べていくのが単純でいいでしょう。
（ルーチン１）

ある大きさ以下の数が素数であるかどうかを調べ、リストとして出力するのなら、チェックリストを作っておき、ある数の倍数であったら、チェックしていき、最後にチェックされていない数を出力するのがいいでしょう。
（ルーチン２）

上記の実際のコードはたとえば次にようになります。
（別回答とします。）

お礼

本当に丁寧な回答ありがとうございました！！
C言語はよく知っていますのでかなり参考になりました。
素数というものは難しいものなんですね…。
２つのルーチンしっかり理解します！！

回答No.5

imogasi

(1)VBには、素数を出す関数はありません。
（２）エラトステネス（注）、「エラトステネスのふるい」でＷＥＢ上で検索してください。沢山素数関連の著述が出てきます。
（３）いくつぐらいの素数がいるのですか。１０００までの数のうちの素数は下記にのっています。
（３）素数は無限にあります。証明は高校教科書に載っていて、背理法の応用で有名です。
しかしｎを指定して、Ｆ（ｎ）が必ず素数になる、初等的な関数Ｆ（）は見つかっていないようです。発見したら
歴史に名が残る？
（４）エラトステネスの篩のアルゴリズムをプログラム化することは難しくないが、数が大きくなると計算時間が無視できなくなります。
（ベンチマークテストにも使われたくらい計算負荷大）
それで充分な数の素数を本で調べ、メモ帳ででも打ちこんで、保存しファイル化し、プログラムの始めにファイルを読んでメモリーに読みこむのがいいのではないでしょうか。
（エラトステネスの篩のプログラム－Ｃ言語）
http://www.kashi.info.waseda.ac.jp/~kashi/lec1999/pro/rep4/g99p0266-1.txt
（エラトステネスの篩のプログラム－旧Ｂａｓｉｃ）　　
http://www.geocities.com/Tokyo/Flats/9390/basic_3.html#basic37
（注）１．紀元前３世紀のギリシア人地理学者エラトステネスの地球の大きさに関する著述も出てきますが、それは捨ててください。
２。「SIEVE」はふるいの意味。

お礼

回答ありがとうございました！！
エラトステネスのふるいなんて考え方があったんですね…、参考にします！

回答No.4

wolv

回答No.2のルーチン２のコードは以下のようになります。

（VBは知らないのでＣ（のようなもの）で書かせていただきますが、アルゴリズムは分かると思います。 ）

（回答No3.では上記の部分がわけわかんない文章になってしまってます。ごめんなさい。）

void sosuu2(){
　MAX=10000;/*ＭＡＸ未満の素数を調べる。*/
　int list[MAX];

　/*全ての数は素数の候補*/
　for(i=0;i<MAX;i++)list[i]=0;

　j=2;/*２の倍数は素数ではない。*/
　for(i=j;i<MAX;i+=j)list[i]=1;

　/*３以上の奇数の倍数は素数ではない。ただし、チェックしている数ｊ自身は素数かもしれない。*/
　for(j=3;j<MAX;j+=2){
　　for(i=2*j;i<MAX;i+=j) list[i]=1;
　}

　/*素数の出力：２以上でチェックから漏れているものは素数*/
　for(i=2;i<MAX;i++){
　　if(list[i]==0)printf("%d wa sosuu.\n",i);
　}
}

回答No.3

wolv

回答No.2のルーチン１のコードは、VBは知らないのでＣ（のようなもの）で書かせていただきますが、アルゴリズムは分かると思います。

int sosuu(int n){
　/*n が素数だったら１を、素数でなかったら、最小の因数を返す*/
　/*エラーなら-1を返す。*/

　int i, max;

　if(n<1) return -1;
　if( mod(n,2) == 0) return 2;/*２で割り切れる？*/
　max=sqrt(n);
　for(i=3;i<=max;i++){
　　if( mod(n,i) == 0) return i;/*ｉで割り切れる？*/
　}
　return 1;
}

回答No.1

noname#12673

候補の数字を一つ用意して、それが素数の定義に当てはまっているか判定すればよいのではないでしょうか？

１からｎまでの中で素数はどれか、という場合は１からｎまでの数字を総当りする。なんでもいいから、とにかく素数を使いたいなら、乱数で整数を１個発生させて、それが素数か判定し、素数でなかったらもう１個発生させる・・・というふうにやってみては？

何桁の素数を見つけたい・・・っていう条件あります？

お礼

さっそくの回答ありがとうございました！
何桁の素数を見つけたいというのはないんです…。
とりあえずどんなものでもいいから数多く知りたかったんです。
考え方参考にしたいと思います！！