Syn BASICで作ったプログラムの例(3)

このページをスマホなどでご覧になる場合は、画面を横長にする方が読みやすくなります。
目次へ  前のページへ (1) (2) (3) (4) (5) 次のページへ
2022年11月24日 公開。以前はSyn BASIC(オンラインBASICインタプリタ)のページのコンテンツであったSyn BASICで作ったプログラムの例を、独立させて当ページにした。

前のページから引き続き、Syn BASICで作ったプログラムの例を紹介します。

2-3.素数を見つけるプログラム(1)

素数とは、2以上の自然数で、正の約数が1と自分自身のみであるものを指します。例えば13は、正の約数が1と13以外にありませんから素数です。15は、正の約数が1と3と5と15です。1と15以外にも正の約数があるので、15は素数ではありません。

リスト7は、素数の定義に従って素数を見つけるプログラムです。2、3、5、7、11、…と、小さい順に素数を見つけ続けます。数が大きくなると、約数を確認するために行う割り算の回数が増え、時間がかかる様になります。

リスト7、定義に従って素数を見つけるプログラムCOPY
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

リスト7のプログラムは、画面6のRUNボタン(青い三角形のボタン)をクリックすると、実際に実行できます。

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
画面6、定義に従って素数を見つけるプログラム

リスト7のプログラムは、定義に従って素数を見つける単純なプログラムなので、プログラムが短くて、理解しやすいという利点がありますが、次に紹介する2つのプログラムより、かなり素数を見つけるのが遅いです。

2-4.素数を見つけるプログラム(2)

リスト8は、入力した数以下の全ての素数を求めるプログラムです。

このプログラムは、エラトステネスのふるいと呼ばれる、高速に素数を見つけられる方法を使います。エラトステネスのふるいを簡単に説明すると、次の様な素数探索法です。

2から素数を探査する最大の数までのフラグの配列を設け、最初はフラグを下ろしておきます。

次に2から順に3、4、…と、最大の数まで、フラグの状態を見ていきます。もしフラグが立っていたら、その値はそれより小さい数の倍数で、素数ではありません。フラグが下りていたら、その数は素数です。画面にその素数を表示するとともに、その素数の倍数のフラグを全て立てます。

エラトステネスのふるいは、上記の方法で素数を見つけますが、2以外の素数が奇数である事を利用すると、計算量を減らす事ができます。リスト8のプログラムは、この計算量を減らしたプログラムです。

エラトステネスのふるいは、フラグ用の配列がメモリを消費するという欠点はあるものの、高速に素数を探索できる特長があります。

リスト8、入力した数以下の全ての素数を求めるプログラムCOPY
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

リスト8のプログラムは、画面7のRUNボタン(青い三角形のボタン)をクリックすると、実際に実行できます。

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
CLS:LIST
画面7、入力した数以下の全ての素数を求めるプログラム

2-5.素数を見つけるプログラム(3)

リスト9のプログラムも、リスト8のプログラムと同様、小さい順に素数を見つけていきます。リスト8が入力した数以下の素数を見つけるプログラムだったのに対し、リスト9は入力した数と同じ個数の素数を見つけます。

リスト9のプログラムでは、見つかった素数を、配列Pに記録しておきます。新しい数が素数かどうかを判定するには、その数より小さい素数で割ってみて、あまりが出るかどうかを調べます。素数判定をしたい数以下の全ての素数で割ってみなくても、素数判定をしたい数の平方根以下の全ての素数で割れば素数判定ができるので、これにより計算量を減らしています。

リスト8のプログラムでは、素数の探索をしたい範囲と同じサイズの配列が必要だったので、メモリをたくさん消費していましたが、リスト9のプログラムでは、見つかった素数の数とおなじサイズの配列を確保すればよく、メモリの消費を抑えられます。ただし、素数の探査速度は遅くなります。

参考:リスト9のプログラムでは採用していませんが、見つけた素数全部を配列に記録しておく必要はなく、見つける最大の素数の平方根以下の素数だけを記録すればいいので、工夫次第でさらにメモリ消費を押さえる事もできます。ただし、プログラムが複雑になります。

リスト9、入力した数と同じ個数の素数を見つけるプログラムCOPY
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  :'次の数を探索

リスト9のプログラムは、画面8のRUNボタン(青い三角形のボタン)をクリックすると、実際に実行できます。

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 :'次の数を探索
CLS:LIST
画面8、入力した数と同じ個数の素数を見つけるプログラム

次のページでは、円周率を求めるプログラムを紹介します。

目次へ  前のページへ (1) (2) (3) (4) (5) 次のページへ

関連ページ

Arduino 電子工作
このサイトの記事が本になりました。
書名:Arduino 電子工作
ISBN:978-4-7775-1941-5
工学社の書籍の内容の紹介ページ
本のカバーの写真か書名をクリックすると、Amazonの書籍購入ページに移動します。