by konisi » 2005年10月15日(土) 10:54
あってもあまり意味がないかもしれませんがまぁ大量に必要な場合もあるかもしれないので載せます。
コード: 全て選択
'比較的小さな素数を列挙する場合
#N88BASIC
Const K=10000'素数かどうか調べる数の最大値
Dim A As Long,B As Long,A$ As String,N As Long
A$=Str$(K)+".txt"
kill A$
N=0
*A
A=1
*B
A=A+1
IF B=A then goto *C
IF B Mod A=0 then goto *D
goto *B
*C
Locate 9,0'←省いても構わない。下の行を省くなら省いた方がいい。
PRINT C'←省いても構わない。
N=N+1
Open A$ For Append As #1
Print #1,Str$(B)
Close #1
*D
B=B+1
if B<K then goto *A
Open A$ For Append As #1
A$=Str$(K)+"までの数の素数の総数:"+Str$(N)
Print #1,A$
Close #1
End
コード: 全て選択
'比較的大きな素数を大量に列挙する場合
Const K=10000 '素数かどうか調べる数の最大値 千万くらいまでなら平気。
Dim A(K) As Byte,A$ As String
Dim I As Long,J As Long 'ループ用変数
Dim N As Long
A$=Str$(K)+".txt"
kill A$
A(1)=1
For I=2 To Int(Sqr(K))
If A(I)=0 Then
for J=I To Int(K/I)
A(I*J)=1
Next J
'2以上Kの平方根以下の素数を順次打ち出し
A$=Str$(K)+".txt"
Open A$ For Append As #1
A$=Str$(I)
Print #1,A$
N=N+1
Close #1
Print I'←省いても構わない。
End If
Next I
A$=Str$(K)+".txt"
'Kの平方根以上K以下の数を追加打ち出し
Open A$ For Append As #1
For I=Int(Sqr(K))+1 To K
If A(I)=0 Then
A$=Str$(I)
Print #1,A$
N=N+1
Print I'←省いても構わない。
End If
Next I
Close #1
A$=Str$(K)+".txt"
Open A$ For Append As #1
A$=Str$(K)+"までの数の素数の総数:"+Str$(N)
Print #1,A$
Close #1
End
簡単に説明すると、上のコードは片っ端から数値を割っていって約数がその数に来るまで出なければ素数と判断する方法。効率は悪いが使用メモリは少ない。
下のコードは「エラストテネスの篩」と呼ばれ、一部の数学の教科書にも載っているかと思われるが、(調べるのは大変だと思うので)一応解説しておく。
まず、たとえば100までの表を用意する。(紙面上で書きながらやると分かりやすいかと思われる。)
そして、1を斜線などで消す。(1は素数に含まれない為。)
この時、消されていない最小の数値は2なので、2に丸(赤丸推奨)をつけ、2以外の全ての2の倍数を全て消していく。
この時、消されても丸が付いてもいない最小の数は3なので、3に丸をつけ、3以外の3の倍数を全て消していく。
このように消されてもいなくて丸が付いてもいない数のうち最小の数に丸を付け、その数以外のその数の倍数を消していく を繰り返す。
100までの表の場合、100の平方根である10までの数全てに丸あるいは斜線が付いた時点で、10以上で消されていない数全てが(もちろん100までだが。)素数になる。
あってもあまり意味がないかもしれませんがまぁ大量に必要な場合もあるかもしれないので載せます。
[code]
'比較的小さな素数を列挙する場合
#N88BASIC
Const K=10000'素数かどうか調べる数の最大値
Dim A As Long,B As Long,A$ As String,N As Long
A$=Str$(K)+".txt"
kill A$
N=0
*A
A=1
*B
A=A+1
IF B=A then goto *C
IF B Mod A=0 then goto *D
goto *B
*C
Locate 9,0'←省いても構わない。下の行を省くなら省いた方がいい。
PRINT C'←省いても構わない。
N=N+1
Open A$ For Append As #1
Print #1,Str$(B)
Close #1
*D
B=B+1
if B<K then goto *A
Open A$ For Append As #1
A$=Str$(K)+"までの数の素数の総数:"+Str$(N)
Print #1,A$
Close #1
End
[/code]
[code]
'比較的大きな素数を大量に列挙する場合
Const K=10000 '素数かどうか調べる数の最大値 千万くらいまでなら平気。
Dim A(K) As Byte,A$ As String
Dim I As Long,J As Long 'ループ用変数
Dim N As Long
A$=Str$(K)+".txt"
kill A$
A(1)=1
For I=2 To Int(Sqr(K))
If A(I)=0 Then
for J=I To Int(K/I)
A(I*J)=1
Next J
'2以上Kの平方根以下の素数を順次打ち出し
A$=Str$(K)+".txt"
Open A$ For Append As #1
A$=Str$(I)
Print #1,A$
N=N+1
Close #1
Print I'←省いても構わない。
End If
Next I
A$=Str$(K)+".txt"
'Kの平方根以上K以下の数を追加打ち出し
Open A$ For Append As #1
For I=Int(Sqr(K))+1 To K
If A(I)=0 Then
A$=Str$(I)
Print #1,A$
N=N+1
Print I'←省いても構わない。
End If
Next I
Close #1
A$=Str$(K)+".txt"
Open A$ For Append As #1
A$=Str$(K)+"までの数の素数の総数:"+Str$(N)
Print #1,A$
Close #1
End
[/code]
簡単に説明すると、上のコードは片っ端から数値を割っていって約数がその数に来るまで出なければ素数と判断する方法。効率は悪いが使用メモリは少ない。
下のコードは「エラストテネスの篩」と呼ばれ、一部の数学の教科書にも載っているかと思われるが、(調べるのは大変だと思うので)一応解説しておく。
[quote]
まず、たとえば100までの表を用意する。(紙面上で書きながらやると分かりやすいかと思われる。)
そして、1を斜線などで消す。(1は素数に含まれない為。)
この時、消されていない最小の数値は2なので、2に丸(赤丸推奨)をつけ、2以外の全ての2の倍数を全て消していく。
この時、消されても丸が付いてもいない最小の数は3なので、3に丸をつけ、3以外の3の倍数を全て消していく。
このように消されてもいなくて丸が付いてもいない数のうち最小の数に丸を付け、その数以外のその数の倍数を消していく を繰り返す。
100までの表の場合、100の平方根である10までの数全てに丸あるいは斜線が付いた時点で、10以上で消されていない数全てが(もちろん100までだが。)素数になる。[/quote]