素数の計算

１から１０００の間にある素数の数を表示させるやり方を教えてください。

No.4 回答者： BLUEPIXY 回答日時： 2004/11/02 23:30

あんまりいいとは言えないけど

'1～1000までの素数の数を求める
dim prime(200)
dim count
dim i

count=0
prime(0)=2
count=count+1

for i=3 to 1000 step 2
if(isPrime(i)) then
prime(count)=i
count = count +1
end if
next
MsgBox count

function isPrime(n)
dim i,result
i=0
result = true
do while(prime(i)^2 <= n)
if(n mod prime(i) =0) then result=false : exit do
i=i+1
loop
isPrime = result
end function

この回答へのお礼

ありがとうございました！

お礼日時：2004/11/09 19:29

No.3 回答者： JaritenCat 回答日時： 2004/11/02 00:13

エラトステネスのふるいで、偶数の素数は２だけなので、２だけ特別扱いして奇数だけで考えると配列の数を半分にできます。

配列０から４９８を用意する。配列０が３、１が５・・・配列ｎが2*n+3に相当する。
ビット演算を使えばさらに省メモリ化できますが。。。面倒ですね。

ちなみに、１は素数ではありません。

この回答へのお礼

ありがとうございました！

お礼日時：2004/11/09 19:29

No.2 回答者： imogasi 回答日時： 2004/11/01 22:35

（１）１から１０００までの配列を用意する。

（２）２について、その２の２倍、３倍、４倍の数に「記し」をつける（４、８、１６、３２、・・）。１０００まで。印とは「素数でない」という記しになる。
（３）次に２の隣の、印しが付いていない３について、（２）と同じことをする。（６、９、１２、１５、１８、・・に印をつける。１０００を越えないまで）
（４）１０００の平方数まで行ったら止める。
理由：
http://www.hokuriku.ne.jp/fukiyo/math-obe/eratos …参照
（５）印のついていない数１，２，３，５，７、・・を拾う。
これを「エラトステネス（ギリシャの学者人名に由来）の篩（ふるい）」といい、これ以上よいアルゴリズムは見つかっていないようです。
参照
http://www.arch.kumamoto-u.ac.jp/hagane/yamanari …

この回答へのお礼

ありがとうございました！

お礼日時：2004/11/09 19:30

No.1 回答者： ceita 回答日時： 2004/11/01 22:07

http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0
指で数えてください。

宿題なら、
エラトステネスのふるい
で検索してみてください。

この回答へのお礼

ありがとうございました！

お礼日時：2004/11/09 19:30