ab.com コミュニティ

ActiveBasicを通したコミュニケーション
現在時刻 - 2024年3月29日(金) 08:43

全ての表示時間は UTC+09:00 です




新しいトピックを投稿する  トピックへ返信する  [ 4 件の記事 ] 

どう思ったか
必要ない。or要らない。
いつ使うのかが分からない。
少し役に立った
役に立った
暇つぶしにはなった
1 個までオプションを選択できます

投票結果を見る
作成者 メッセージ
投稿記事Posted: 2005年10月15日(土) 10:54 
オフライン

登録日時: 2005年7月25日(月) 13:27
記事: 893
お住まい: 埼玉県東松山市
あってもあまり意味がないかもしれませんがまぁ大量に必要な場合もあるかもしれないので載せます。
コード:
'比較的小さな素数を列挙する場合
#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までだが。)素数になる。


通報する
ページトップ
 記事の件名: 追伸
投稿記事Posted: 2005年10月15日(土) 11:18 
オフライン

登録日時: 2005年7月25日(月) 13:27
記事: 893
お住まい: 埼玉県東松山市
エラストテネスの篩 の方式(下側のコード)の場合、滅茶苦茶メモリ食います。


通報する
ページトップ
 記事の件名:
投稿記事Posted: 2005年10月19日(水) 22:44 
オフライン

登録日時: 2005年5月31日(火) 09:34
記事: 141
お住まい: 北海道
上側のコードの場合,割る数は「B-1」までではなく「Sqr(B)」までで良いです。
例えば60の約数(1と60は除く)は2・3・4・5・6・10・12・15・20・30ですが
10~30の5つについては,手前の5つ(2~6)で割られる際に自動的に出現する
ためです。

ついでに構造化プログラミング的に書き換えてみました。
コード:
'比較的小さな素数を列挙する場合
#N88BASIC
Const K=10000'素数かどうか調べる数の最大値
Dim A As Long,B As Long,A$ As String,N As Long
Dim rB As Long

A$=Str$(K)+".txt"
kill A$
N=0

Open A$ For Output As #1

For B=2 To K
    rB=Sqr(B)
    For A=2 To rB
        If B Mod A=0 Then Exit For
    Next
    If A=rB+1 Then
        Locate 9,0'←省いても構わない。下の行を省くなら省いた方がいい。
        PRINT B'←省いても構わない。
        N=N+1
        Print #1,Str$(B)
    End If
Next

A$=Str$(K)+"までの数の素数の総数:"+Str$(N)
Print #1,A$
Close #1

_________________
' ============================================================
' Sinryow Game Home Page - http://www.sinryow.net/
' Sinryow ActiveBasic Center - http://ab.sinryow.net/
' ============================================================


通報する
ページトップ
 記事の件名:
投稿記事Posted: 2005年10月20日(木) 01:49 
オフライン

登録日時: 2005年7月25日(月) 13:27
記事: 893
お住まい: 埼玉県東松山市
ごくろうさま。<<構造化プログラミングしてみた件について
昔書いたもんだから、書き換えるのが面倒になっちゃってね(笑
でもスパゲッティーはまずいですよね、やっぱ。


通報する
ページトップ
期間内表示:  ソート  
新しいトピックを投稿する  トピックへ返信する  [ 4 件の記事 ] 

全ての表示時間は UTC+09:00 です


オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[7人]


トピック投稿:  可
返信投稿:  可
記事編集: 不可
記事削除: 不可
ファイル添付: 不可

検索:
ページ移動:  
cron
Powered by phpBB® Forum Software © phpBB Limited
Japanese translation principally by ocean