|
|
> No.3437[元記事へ]
GAIさんへのお返事です。
> 以下のアルゴリズムで素数を全て見つけることができるという。
>
> 1.赤コインを2枚と青コイン1枚をすべて裏向きに置く
> 2.赤青どちらかが全部表になるまで任意の赤と青を1枚ずつ（計２枚）を同時にひっくり返す
> 3A.青が先に全部表を向いたときには青を全て裏返して2に戻る
> 3B.赤が先に全部表になったときには青コインを1枚減らし全て裏返して2に戻る
> 3C.青赤同時に全部表になったときには各コインの枚数を何らかの方法で出力し、赤コインを1枚増やし、青コインをそれより1枚少ない枚数にして全て裏返し2に戻る
> 4.必要なだけ繰り返した後、出力から青コインの枚数が1枚となっているときの赤コインの枚数を抽出する
>
> この動きをモニターすることができるプログラムを作って頂きたい。
自分自身を除く最大の約数を求めるものですね。1の場合、素数が現れます。（赤色の部分）
LET RR=2 !赤の枚数 ※自然数n≧2
LET BB=1 !青の枚数 ※約数d=n-1
LET R=RR !赤の裏向きの枚数 step.1
LET B=BB !青の裏向きの枚数
DO
LET M=MIN(R,B) !表にする枚数 step.2
LET R=R-M !※dをひく
LET B=B-M
IF R=0 AND B=0 THEN !step.3C ※dで割り切れる
PRINT RR;BB !step.4
!!IF BB=1 THEN PRINT RR;BB !step.4
LET RR=RR+1 !次へ
LET BB=RR-1
LET R=RR
LET B=BB
ELSEIF B=0 THEN !step.3A
LET B=BB
ELSEIF R=0 THEN !step.3B
LET BB=BB-1 !※d=n-1,n-2,…,3,2,1
LET R=RR
LET B=BB
END IF
LOOP
END
実行結果
2 1
3 1
4 2
5 1
6 3
7 1
8 4
9 3
10 5
11 1
12 6
13 1
14 7
15 5
16 8
17 1
18 9
19 1
20 10
21 7
22 11
23 1
24 12
25 5
26 13
27 9
28 14
29 1
30 15
31 1
32 16
33 11
34 17
35 7
36 18
37 1
38 19
39 13
40 20
41 1
42 21
43 1
44 22
45 15
46 23
47 1
48 24
49 7
50 25
：
：
|
|