十進BASIC 第2掲示板 過去ログ

!カーマイケル数

OPTION ARITHMETIC RATIONAL !有理数モード（多桁整数）

LET M=10000 !検索範囲

FOR n=2 TO M
   IF PrimeQ(n)=0 THEN !合成数nが

      FOR a=2 TO n-1 !底
         IF GCD(a,n)=1 THEN !自身と互いに素である任意の自然数aに対して
            IF MOD(a^(n-1),n)<>1 THEN EXIT FOR !a^(n-1)≡1 mod n を満たす
         END IF
      NEXT a
      IF a=n THEN PRINT n !最後までなら

   END IF
NEXT n

END

EXTERNAL FUNCTION PrimeQ(n) !素数判定　1:素数、0:素数でない
OPTION ARITHMETIC RATIONAL !有理数モード（多桁整数）
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 !３～√nの奇数のみで検証する
      IF MOD(n,k)=0 THEN EXIT FUNCTION !ひとつでも割り切れるものがあれば素数でない
      LET k=k+2
   LOOP
   LET PrimeQ=1 !最後まで割り切れなければ、素数である
END IF
END FUNCTION

!カーマイケル数

LET M=10000 !検索範囲

FOR n=2 TO M
   IF PrimeQ(n)=0 THEN !合成数nが

      FOR a=2 TO n-1 !底
         IF GCD(a,n)=1 THEN !自身と互いに素である任意の自然数aに対して
            IF modpow(a,n-1,n)<>1 THEN EXIT FOR !a^(n-1)≡1 mod n を満たす
         END IF
      NEXT a
      IF a=n THEN PRINT n !最後までなら

   END IF
NEXT n

END

EXTERNAL 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 !３～√nの奇数のみで検証する
      IF MOD(n,k)=0 THEN EXIT FUNCTION !ひとつでも割り切れるものがあれば素数でない
      LET k=k+2
   LOOP
   LET PrimeQ=1 !最後まで割り切れなければ、素数である
END IF
END FUNCTION

EXTERNAL FUNCTION modpow(a,n,b) !a^n≡x mod b のxを返す　※nは非負整数
LET S=MOD(1,b)
DO WHILE n>0 !べき乗nを２進展開する
   IF MOD(n,2)=1 THEN LET S=MOD(S*a,b) !ビットが１なら計算する
   LET a=MOD(a*a,b)
   LET n=INT(n/2)
LOOP
LET modpow=S
END FUNCTION

EXTERNAL FUNCTION gcd(a,b) !最大公約数
DO UNTIL b=0
   LET t=b
   LET b=MOD(a,b)
   LET a=t
LOOP
LET gcd=a
END FUNCTION

FOR n=1 TO 10000
   IF PrimeQ(n)=0 AND MOD(n,carmichaelLambda(n))=1 THEN PRINT n
NEXT n

END


EXTERNAL 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 !３～√nの奇数のみで検証する
      IF MOD(n,k)=0 THEN EXIT FUNCTION !ひとつでも割り切れるものがあれば素数でない
      LET k=k+2
   LOOP
   LET PrimeQ=1 !最後まで割り切れなければ、素数である
END IF
END FUNCTION

EXTERNAL FUNCTION gcd(a,b) !最大公約数
DO UNTIL b=0
   LET t=b
   LET b=MOD(a,b)
   LET a=t
LOOP
LET gcd=a
END FUNCTION


EXTERNAL FUNCTION lcm(a,b) !最小公倍数
LET lcm=a*b/gcd(a,b)
END FUNCTION

EXTERNAL FUNCTION carmichaelLambda(n) !カーマイケルのλ関数
!与えられた数nに対し、a^m ≡ 1 (mod n) が
!任意のnと互いに素なaについて成立するような最小のmを返す。
LET ans=1
IF MOD(n,8)=0 THEN LET n=n/2
FOR d=2 TO n
   IF MOD(n,d)=0 THEN
      LET y=d-1
      LET n=INT(n/d)
      DO WHILE MOD(n,d)=0
         LET n=INT(n/d)
         LET y=y*d
      LOOP
      LET ans=lcm(ans,y)
   END IF
NEXT d
LET carmichaelLambda=ans
END FUNCTION