Lucas-Lehmer test: Difference between revisions

=={{header|Bracmat}}==

Only <code>exponent</code>s that are prime are tried. The primality test of these numbers uses a side effect of Bracmat's attempt at

computing a root of a small enough number. ('small enough' meaning that the number must fit in a computer word, normally 32 or 64 bits.)

To do that, Bracmat first creates a list of factors of the number and then takes the root of each factor. For example, to compute <code>54^2/3</code>,

Bracmat first creates the expression <code>(2*3^3)^2/3</code> and then <code>2^2/3*3^(3*2/3)</code>, which becomes <code>2^2/3*9</code>.

If a number cannot be factorized, (either because it is prime or because it is to great to fit in a computer word) the root expression doesn't change much.

For example, the expression <code>13^(13^-1)</code> becomes <code>13^1/13</code>, and this matches the pattern <code>13^%</code>.

<lang bracmat> ( clk$:?t0:?now

& ( time

= ( print

=

. put

$ ( str

$ ( div$(!arg,1)

","

( div$(mod$(!arg*100,100),1):?arg

& !arg:<10

& 0

|

)

!arg

" "

)

)

)

& -1*!now+(clk$:?now):?SEC

& print$!SEC

& print$(!now+-1*!t0)

& put$"s: "

)

& 3:?exponent

& whl

' ( !exponent:~>12000

& ( !exponent^(!exponent^-1):!exponent^%

& 4:?s

& 2^!exponent+-1:?n

& 0:?i

& whl

' ( 1+!i:?i

& !exponent+-2:~<!i

& mod$(!s^2+-2.!n):?s

)

& ( !s:0

& !time

& out$(str$(M !exponent " is PRIME!"))

|

)

|

)

& 1+!exponent:?exponent

)

& done

);</lang>

Output (after 4.5 hours):

<pre>0,00 0,00 s: M3 is PRIME!

0,00 0,00 s: M5 is PRIME!

0,00 0,00 s: M7 is PRIME!

0,00 0,00 s: M13 is PRIME!

0,00 0,00 s: M17 is PRIME!

0,00 0,01 s: M19 is PRIME!

0,00 0,01 s: M31 is PRIME!

0,00 0,01 s: M61 is PRIME!

0,01 0,02 s: M89 is PRIME!

0,01 0,03 s: M107 is PRIME!

0,00 0,04 s: M127 is PRIME!

0,50 0,54 s: M521 is PRIME!

0,29 0,84 s: M607 is PRIME!

6,81 7,65 s: M1279 is PRIME!

38,35 46,01 s: M2203 is PRIME!

6,32 52,33 s: M2281 is PRIME!

116,01 168,34 s: M3217 is PRIME!

293,09 461,44 s: M4253 is PRIME!

64,61 526,05 s: M4423 is PRIME!

8863,90 9389,95 s: M9689 is PRIME!

1101,12 10491,08 s: M9941 is PRIME!

5618,45 16109,53 s: M11213 is PRIME!</pre>