PRINT
PRINT "２つの自然数が互いに素であるかどうか判定します。"
PRINT
INPUT PROMPT "１つ目の自然数は？ ":a
INPUT PROMPT "２つ目の自然数は？ ":b
PRINT
LET c=GCD(a,b)
IF c=1 THEN
   PRINT "２つの自然数は互いに素である。"
ELSE
   PRINT "２つの自然数は互いに素である。"
   PRINT "なぜなら、";c;"で割り切れるから。"
END IF
PRINT
END

EXTERNAL FUNCTION GCD(s,t)      ! 最大公約数を求める関数
DO
   LET m=MOD(s,t)
   IF m=0 THEN EXIT DO
   LET s=t
   LET t=m
LOOP
LET gcd=t
END FUNCTION



########################################################################



PRINT
PRINT "＜互いに素かどうかの判定＞"
PRINT "２つの自然数をカンマで区切って入力してください。"
PRINT
INPUT PROMPT "２つの自然数は？  ":x,y
PRINT
DIM T(1000)
IF x>y THEN
   LET Q=x
   LET x=y
   LET y=Q
END IF
CALL Divisors(x,W,T)
LET z=0
FOR i=1 TO W
   IF T(i)>1 THEN
      IF MOD(y,T(i))=0 THEN    ! x のそれぞれの約数で y が割り切れるか？
         LET z=1
      END IF
   END IF
NEXT i
IF z=0 THEN
   PRINT "互いに素です。"
ELSE
   PRINT "互いに素ではありません。"
END IF
PRINT
END

EXTERNAL SUB Divisors(N,C,D())  ! 山中和義/電脳遊戯団さんの 約数.BAS より
LET C=1
LET D(1)=1
LET i=2
DO WHILE i*i<=N
   IF MOD(N,i)=0 THEN
      LET C=C+1
      LET D(C)=i
   END IF
   LET i=i+1
LOOP
LET M=C
IF D(C)*D(C)=N THEN LET M=M-1
FOR i=1 TO M
   LET D(C+i)=N/D(M-i+1)
NEXT i
LET C=C+M
END SUB



########################################################################



PRINT
PRINT "＜互いに素かどうかの判定＞"
PRINT "２つの自然数をカンマで区切って入力してください。"
PRINT
INPUT PROMPT "２つの自然数は？  ":x,y
PRINT
DIM R(1000)
FOR i=1 TO x
   LET R(i)=MOD(i*y,x)     ! ここがこのプログラムのアルゴリズムの核心
NEXT i
CALL KOTONAR(R,x,H) 
IF H=1 THEN
   PRINT "互いに素です。"
ELSE
   PRINT "互いに素ではありません。"
END IF
PRINT
END

EXTERNAL SUB KOTONAR(D(),W,M)   !すべて異なる数ならば M=1
CALL SORT(D,W)
LET M=1
FOR i=1 TO W-1
   IF D(i)=D(i+1) THEN
      LET M=0
      EXIT FOR
   END IF
NEXT i
END SUB

EXTERNAL SUB SORT(a(),m)     ! m個の数を小さい順に並べ替える
FOR i=1 TO m-1
   FOR j=i+1 TO m
      IF a(i)>a(j) THEN
         LET t=a(j) 
         LET a(j)=a(i)
         LET a(i)=t
      END IF
   NEXT j
NEXT i
END SUB