!---------------------------------------------------------------------------
!
SOSUU.BAS for (仮称)十進BASIC
!
エラトステネスの篩で素数をリストアップするするプログラム。
! 5000個の素数テーブルを篩として用意する。このときテーブルの最大の
! 素数は48611なので、48611^2（約23億）までの数値を篩にかけることが
! できる。実際には配列の添字が32ビット整数の制限を受けるので、上限
! は 2147000000
までとしてある。出力可能な素数の個数は1億強である。
!
探索範囲に配列を設定して、これを篩にかける。この探索範囲を順に
! ずらせていく。配列サイズは TabSize
で設定する。TabSizeは実行環
!
境に合わせて変更する事ができるが、偶数でなければならない。
!
結果は、指定したファイルにテキストファイルとしてに出力される。
!
同名のファイルがあっても無条件に上書きするので注意のこと。
!
ファイル名入力時にリターンキーのみ押すと画面に出力する。
! Maxを21億にしたときには、出力するファイルサイズは1GB強になる｡
!---------------------------------------------------------------------------
! 初期設定
option arithmetic native
! 十進BASICの数値モードの指定
! 変数の宣言
declare string FileName$
! 出力するファイル名
declare numeric TabSize, PSize
! 配列サイズの設定値
declare numeric Max
! 求める素数の上限値
declare numeric StartTime
! 計算開始時刻
declare numeric i, j, k
! ループカウンタ
declare numeric Count
! 素数の数のカウンタ
declare numeric ArrayEnd, ArrayEndSqr !
配列の最後の添字とその平方根
declare numeric StartPoint
! 消去すべき素数の倍数の開始点
! 配列サイズの設定
let PSize = 5000
! 篩として使う素数テーブルの大きさ
let TabSize = 10000
! 探索対象にする配列の大きさ（偶数）
! 配列の宣言
dim p(PSize)
! 篩となる素数テーブルの配列の宣言
dim tab(TabSize)
! 探索に使う配列
!--------------------------------------------------------
!
求める素数の最大値と出力ファイル名を受け取る
!--------------------------------------------------------
input prompt "求める素数の最大サイズを指定してください":
Max
let Max = TabSize*(int((Max-1)/TabSize)+1)
if Max > 2147000000 then
print "指定された値が大きすぎます。Max=2147000000
に設定します"
let Max = 2147000000
end if
print Max; "までの素数を探索します"
Line input prompt "ファイル名を入力してください":
FileName$
if Filename$ = "" then print "ファイルではなく画面に出力します"
let StartTime = Time
! 計算開始時間の記録
!-----------------------------------------------------------------------
!ファイル名が指定されているときはファイルを開いておく。無条件に上書き。
!-----------------------------------------------------------------------
if Filename$ <> "" then
OPEN #1: NAME FileName$, RECTYPE INTERNAL
ERASE #1
end if
!----------------------------------------------------------------------
! 篩の作成。√Maxまでの素数の値を、篩として使う配列
p に代入する
!----------------------------------------------------------------------
let P(1) = 2
let Count = 1
let i = 3
do while P(Count)^2 < Max
let j = 1
do while (P(j)^2 <= i) and (mod(i, P(j)) <>
0)
let j = j+1
loop
if P(j)^2 > i then
let Count = Count + 1
let P(Count) = i
end if
let i = i + 2
loop
print "Sieve constructed."
!---------------------------------------------------------------------------
!
ここからがメイン処理。篩を使って、素数を求めていく
!---------------------------------------------------------------------------
let Count = 0
! リストした素数の個数の数えるカウンタ
for i = 1 to Max step TabSize
let ArrayEnd = i + TabSize - 1
let ArrayEndSqr = Int(SQR(ArrayEnd))
redim tab(i to ArrayEnd)
! 添字範囲を変更、配列要素は０に初期化
for j = i to ArrayEnd step 2
! 奇数のみ候補として残す（１を代入する）
let tab(j) = 1
next j
if i = 1 then
! i = 1 のときだけの例外処理
let tab(1) = 0
! 1 は素数でないので tab(1)には 0 を代入
let tab(2) = 1
! 2 は素数なので tab(2)には 1
を代入
end if
!
合成数（＝素数の倍数）をふるい落とす（＝０を代入する）処理
let j = 2
do while p(j) <= ArrayEndSqr
if i = 1 then
let StartPoint =
p(j)^2
else
let StartPoint =
p(j) * (int((i-1) / p(j)) + 1)
if
mod(StartPoint,2)=0 then
let Startpoint = StartPoint + p(j)
end if
end if
for k = StartPoint to ArrayEnd
step 2*p(j)
let tab(k) = 0
next k
let j = j + 1
loop
!
素数の出力。配列の添字が素数であるときその配列要素は１になっている。
for j = i to ArrayEnd
if tab(j) = 1 then
! tab(j)=1 のとき j は素数
let Count =
Count + 1
if FileName$ =
"" then !
ファイル名が指定されていないときは画面出力
print j;
if Mod(Count,10)=0 then print
else
! 指定されたファイルに出力
write #1: j,
if Mod(Count,10)=0 then write #1:
end if
end if
next j
!
素数をファイルに出力するときは画面に途中経過を表示
if FileName$ <> "" then
print ArrayEnd; "integers
checked. "; Count; "primes found."
end if
next i
! 終了メッセージの出力
if FileName$ <> "" then
! ファイル出力の終了処理
write #1:
write #1: Count, "primes found."
close #1
end if
print
print "Finished. "; Count; "primes found.
";
print using "-----%.#": Time - StartTime;
! 計算所用時間の表示
print " sec."
END