Anonymous user
Perfect numbers: Difference between revisions
m
→Lucas-Lehmer + other optimizations: changed indentations in the isPerfect function.
(→traditional method: replaced with the appropriate REXX program.) |
m (→Lucas-Lehmer + other optimizations: changed indentations in the isPerfect function.) |
||
Line 1,858:
===Lucas-Lehmer + other optimizations===
This version uses the Lucas-Lehmer method, digital
<br>also utilizes a check for the last-two-digits as per François Édouard Anatole Lucas (in 1891).
Line 1,882:
/*──────────────────────────────────────────────────────────────────────────────────────*/
isPerfect: procedure expose @. !. ? /*expose (make global) some variables. */
/*╔═════════════════════════════════════════════╗
║ Lucas─Lehmer know that perfect numbers can ║
║ be expressed as: [2^n -1] * {2^(n-1) } ║
╚═════════════════════════════════════════════╝*/
if @.0<x then
end /*@.1*/ /* [↑] uses memoization for formula. */
/*[↓] perfect numbers digital root = 1*/
parse var y d 2; do k=2 for length(y)-1;
q=1; do while q<=z; q=q*4 ; end /*while q≤z*/
r=0 /* [↓] R will be the integer √ X */
do while q>1; q=q%4;
/*
do j=3 to r until s>x
if x//j==0 then s=s+j+x%j
end /*j*/
'''output''' is the same as the traditional version and is about '''500''' times faster (testing 34,000,000 numbers). <br><br>
|