|
|
問題
1,12,123,1234,12345,123456,1234567,12345678,123456789,1234567890,12345678901,123456789012, …
となる数字の並びの数が素数となるものを見つけよ。
答え
xは非負整数、yは1から9までの数とする。
{1234567890}がx個と1からyまでの数字が並んだ(10x+y)桁の数は、
{1234567890} … {1234567890}123…y
└── x個 ──┘
と表される。
まず、一の位が0,2,4,6,8のとき、2の倍数。 0,5のとき、5の倍数
各桁の数の和から、3,9のとき、3の倍数
よって、1,7の場合を検証すればよい。
（終り）
次の桁数が予想される。
1の場合、31, 111, 121, 141, 161, 171, 191, …
7の場合、157, 167, 187, …
OPTION ARITHMETIC RATIONAL !多桁の整数
LET y=1
FOR x=0 TO 20
!!LET K=9*x+y
!!LET N=INT(10^K*123456789/999999999) !123456789123…の一般項
LET K=10*x+y
LET N=INT(10^K*1234567890/9999999999) !1234567890123…の一般項
PRINT K;"桁"; N
LET t=prmdiv(N)
IF t=N THEN PRINT "素数" ELSE PRINT "合成数";t
NEXT x
END
EXTERNAL FUNCTION prmdiv(n) !１より大きな最小の約数（最小因数）
OPTION ARITHMETIC RATIONAL !多桁の整数
IF n<>INT(n) THEN !整数以外なら
PRINT "prmdiv関数でパラメータが不適当です。"; n
STOP
ELSEIF n=0 THEN
LET prmdiv=0
ELSE
LET n=ABS(n) !絶対値をとる
IF MOD(n,2)=0 THEN !最小因数が2である場合
LET prmdiv=2
ELSEIF MOD(n,3)=0 THEN !最小因数が3である場合
LET prmdiv=3
ELSEIF MOD(n,5)=0 THEN !最小因数が5である場合
LET prmdiv=5
ELSE !以下、7以上の奇数(2,3,5とそれぞれ互いに素な数のみ)ごとに割っていく
DATA 1,7,11,13,17,19,23,29
DIM P(0 TO 7)
MAT READ P
LET a=7
LET J=0
LET i=1
DO
IF MOD(n,a)=0 THEN !nがaで初めて割り切れれば、最小因数はaである
LET prmdiv=a
EXIT FUNCTION
END IF
LET i=i+1
IF i>=8 THEN
LET i=0
LET J=J+30
END IF
LET a=J+P(i)
LOOP WHILE a*a<=n !a≦√nの範囲が対象となる
LET prmdiv=n !最小因数がその数自身の場合、素数である
END IF
END IF
END FUNCTION
|
|