OPTION ARITHMETIC decimal_HIGH
PRINT
PRINT "ある自然数数を超えないで、その数と互いに素な 自然数"
PRINT
INPUT PROMPT "自然数は？ ":n
PRINT
LET C=0
FOR i=1 TO n-1
   IF gcd(i,n)=1 THEN
      PRINT i;
      LET C=C+1
   END IF
NEXT i
PRINT
PRINT
PRINT "以上";C;"個 あります。"
PRINT
END

EXTERNAL FUNCTION gcd(s,t)
OPTION ARITHMETIC decimal_HIGH
DO
   LET m=MOD(s,t)
   IF m=0 THEN EXIT DO
   LET s=t
   LET t=m
LOOP
LET gcd=t
END FUNCTION



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




FUNCTION PrimeQ(n)       ! 素数判定   1 : 素数、  0 : 素数でない
   LET PrimeQ=0
   IF n<2 OR n<>INT(n) THEN EXIT FUNCTION 
   IF MOD(n,2)=0 THEN
      IF n=2 THEN LET PrimeQ=1
   ELSE
      LET k=3
      DO WHILE k*k<=n
         IF MOD(n,k)=0 THEN EXIT FUNCTION 
         LET k=k+2
      LOOP
      LET PrimeQ=1
   END IF
END FUNCTION

PRINT
PRINT "ある自然数と互いに素で、その自然数を超えない自然数"
PRINT
INPUT PROMPT "自然数は？ ":n
PRINT
LET NN=n
DIM Q(20),R(20)
LET f=2
LET x=1
DO UNTIL n=1
   IF PrimeQ(f)=0 THEN GOTO 10
   LET C=0   
   DO WHILE MOD(n,f)=0
      IF C=0 THEN
         LET Q(x)=f
      END IF
      LET n=n/f
      LET C=C+1
   LOOP
   IF C=0 THEN GOTO 10
   LET R(x)=C
   LET x=x+1
10    LET f=f+1
   LOOP
    
   LET Z=O
   FOR i=1 TO NN
      LET W=0
      FOR j=1 TO x-1
         IF MOD(i,Q(j))=O THEN
            LET W=W+1
         END IF
      NEXT j
      IF W=0 THEN
         PRINT i;
         LET Z=Z+1
      END IF
   NEXT i
   PRINT
   PRINT
   PRINT "以上";Z;"個 あります。"
   PRINT
END