| 2022年11月24日 | 公開。以前はSyn BASIC(オンラインBASICインタプリタ)のページのコンテンツであったSyn BASICで作ったプログラムの例を、独立させて当ページにした。 |
前のページから引き続き、Syn BASICで作ったプログラムの例を紹介します。
素数とは、2以上の自然数で、正の約数が1と自分自身のみであるものを指します。例えば13は、正の約数が1と13以外にありませんから素数です。15は、正の約数が1と3と5と15です。1と15以外にも正の約数があるので、15は素数ではありません。
リスト8は、素数の定義に従って素数を見つけるプログラムです。2、3、5、7、11、…と、小さい順に素数を見つけ続けます。数が大きくなると、約数を確認するために行う割り算の回数が増え、時間がかかる様になります。
10 I=2 :'2以上の数が素数かどうか調べる
20 F=1 :'素数かどうかのフラグ
30 FOR J=2 TO I-1 :'2～I-1の範囲に約数があるかを調べる
40 IF I MOD J=0 THEN F=0:BREAK :'約数を見つけた
50 NEXT
60 IF F=1 THEN PRINT I, :'素数を見つけたので表示
70 I=I+1 :'次の数が素数かどうかを調べる
80 GOTO 20リスト8のプログラムは、画面7のRUNボタン(青い三角形のボタン)をクリックすると、実際に実行できます。
リスト7のプログラムは、定義に従って素数を見つける単純なプログラムなので、プログラムが短くて、理解しやすいという利点がありますが、次に紹介する2つのプログラムより、かなり素数を見つけるのが遅いです。
リスト9は、入力した数以下の全ての素数を求めるプログラムです。
このプログラムは、エラトステネスのふるいと呼ばれる、高速に素数を見つけられる方法を使います。エラトステネスのふるいを簡単に説明すると、次の様な素数探索法です。
2から素数を探査する最大の数までのフラグの配列を設け、最初はフラグを下ろしておきます。
次に2から順に3、4、…と、最大の数まで、フラグの状態を見ていきます。もしフラグが立っていたら、その値はそれより小さい数の倍数で、素数ではありません。フラグが下りていたら、その数は素数です。画面にその素数を表示するとともに、その素数の倍数のフラグを全て立てます。
エラトステネスのふるいは、上記の方法で素数を見つけますが、2以外の素数が奇数である事を利用すると、計算量を減らす事ができます。リスト9のプログラムは、この計算量を減らしたプログラムです。
エラトステネスのふるいは、フラグ用の配列がメモリを消費するという欠点はあるものの、高速に素数を探索できる特長があります。
10 'エラトステネスのふるいにより素数を求めるプログラム
20 PRINT "指定した数以下の素数を全部求めます。"
30 INPUT "素数を探索する最大の数:",MAX
40 IF MAX<2 THEN PRINT "2以上の数を入力してください":GOTO 30
50 IF MAX<>INT(MAX) THEN PRINT "整数を入力してください。":GOTO 30
60 DIM F(MAX) :'ふるいに使うフラグ配列の宣言(配列の初期値は0)
70 PRINT 2, :'2は無条件に素数として表示
80 FOR I=3 to MAX STEP 2 :'3以上MAX以下の数を素数かどうか判定
90 IF F(I)=1 THEN GOTO 140 :'フラグが立っていたのでIは素数でなかった
100 PRINT I, :'見つかった素数を表示
110 FOR J=I*3 TO MAX STEP I*2 :'Iの奇数倍のフラグを立てる
120 F(J)=1
130 NEXT J
140 NEXT I
150 PRINT
160 ENDリスト9のプログラムは、画面8のRUNボタン(青い三角形のボタン)をクリックすると、実際に実行できます。
リスト10のプログラムも、リスト9のプログラムと同様、小さい順に素数を見つけていきます。リスト9が入力した数以下の素数を見つけるプログラムだったのに対し、リスト10は入力した数と同じ個数の素数を見つけます。
リスト10のプログラムでは、見つかった素数を、配列Pに記録しておきます。新しい数が素数かどうかを判定するには、その数より小さい素数で割ってみて、あまりが出るかどうかを調べます。素数判定をしたい数以下の全ての素数で割ってみなくても、素数判定をしたい数の平方根以下の全ての素数で割れば素数判定ができるので、これにより計算量を減らしています。
リスト9のプログラムでは、素数の探索をしたい範囲と同じサイズの配列が必要だったので、メモリをたくさん消費していましたが、リスト10のプログラムでは、見つかった素数の数とおなじサイズの配列を確保すればよく、メモリの消費を抑えられます。ただし、素数の探査速度は遅くなります。
参考:リスト10のプログラムでは採用していませんが、見つけた素数全部を配列に記録しておく必要はなく、見つける最大の素数の平方根以下の素数だけを記録すればいいので、工夫次第でさらにメモリ消費を押さえる事もできます。ただし、プログラムが複雑になります。
10 PRINT "素数を小さい順に、指定した個数だけ見つけます。"
20 INPUT "個数:",CNT :'見つける素数の個数を入力
30 DIM P(CNT) :'見つけた素数を記録する配列の宣言
40 IF CNT<1 THEN END :'個数が1個未満なら直ちに終了
50 N=1 :'Nはすでに見つけた素数の数
60 P(N)=2 :'2は無条件に素数とする
70 PRINT N;"番目: ";P(N) :'2を表示
80 IF CNT<2 THEN END :'見つける素数が1個だけの場合はここで終了
90 I=3 :'3以降の数を探索
100 FOR J=2 to N :'Iが素数か確かめるためのループ
110 IF P(J)*P(J)>I THEN GOTO 140 :'P(J)がIの平方根より大きいので、Iが素数であることが確定
120 IF I MOD P(J)=0 THEN GOTO 180 :'IがP(J)で割り切れたので、Iは合成数
130 NEXT
140 N=N+1
150 P(N)=I :'見つかった素数を配列に記録
160 PRINT N;"番目: ";I :'見つかった素数を表示
170 IF N>=CNT THEN END :'素数をN個見つけたので終了
180 I=I+2 :'奇数のみを探索するので、2刻みで探索
190 GOTO 100 :'次の数を探索
リスト10のプログラムは、画面9のRUNボタン(青い三角形のボタン)をクリックすると、実際に実行できます。
次のページでは、円周率を求めるプログラムを紹介します。
