help
输入fermart_prime(x)
判断x是否为质数。注意这是概率判断。
返回true时极有可能为质数。返回fale时不可能是质数。
输入fermart_prime(x,m)
以随机重复n次来判断x是否为质数。n省略时默认为200。
endh
function fermat_prime(x,...)
variable a,b,n=0,m=200
try
m=floor(abs(opt_argv[0]))
catch
endtry
x=floor(abs(x))
do
b=floor(sj(1,x))
a=modular(b,x-1,x)
if a!=1
return false
endif
n=n+1
until n==m
return true
endf
help
输入modular(a,b,n)进行模取幂.
a,b均为非负数，n>0
该函数相当于mod(a**b,n)
只不过速度特快
endh
function modular(a,b,n)
variable d=1,t=a
while b>0
if mod(b,2)
d=mod(d*t,n)
endif
b=floor(b/2)
t=mod(t*t,n)
loop
return d
endf
function sj(a,b)
variable x=a,y=b,c,d,f
c=rand()
if a>b
x=b
y=a
else
x=x
y=y
endif
d=y-x
f=d*c+x
return(f)
endf

help
@language:
输入timetest(待测用时的函数"x")返回该执行函数x用的时间单位ms
@end
endh
function timetest(x)
variable a,b,c,d
a=now()
try
c=evaluate(x)
catch
endtry
try
print(c+"\n")
catch
endtry
b=now()
d=b-a
//print("\n用时为:\n")
return d
endf

返回true时的准确率为(p)**m
其中p为对所有小于n的正整数a使得mod(a**(n-1),n)==1
的所有a占数n-1的多少保守值为1/4
当m==20时错误率为9.09e-13