Amicable pairs: Difference between revisions
Content added Content deleted
(Added Miniscript) |
(→{{header|Lua}}: Replaced time with time from TIO.RUN, added alternative version that doesn't use division/modulo) |
||
Line 3,486: | Line 3,486: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Avoids unnecessary divisor sum calculations.<br> |
|||
0.02 of a second in 16 lines of code. |
|||
Runs in around 0.11 seconds on TIO.RUN. |
|||
The vital trick is to just set m to the sum of n's proper divisors each time. That way you only have to test the reverse, dividing your run time by half the loop limit (ie. 10,000)! |
|||
<syntaxhighlight lang="lua">function sumDivs (n) |
<syntaxhighlight lang="lua">function sumDivs (n) |
||
local sum = 1 |
local sum = 1 |
||
Line 3,507: | Line 3,508: | ||
{{out}}<pre> |
{{out}}<pre> |
||
220 284 |
|||
1184 1210 |
|||
2620 2924 |
|||
5020 5564 |
|||
6232 6368 |
|||
10744 10856 |
|||
12285 14595 |
|||
17296 18416 |
|||
</pre> |
|||
Alternative version using a table of proper divisors, constructed without division/modulo.<br> |
|||
Runs is around 0.02 seconds on TIO.RUN. |
|||
<syntaxhighlight lang="lua"> |
|||
MAX_NUMBER = 20000 |
|||
sumDivs = {} -- table of proper divisors |
|||
for i = 1, MAX_NUMBER do sumDivs[ i ] = 1 end |
|||
for i = 2, MAX_NUMBER do |
|||
for j = i + i, MAX_NUMBER, i do |
|||
sumDivs[ j ] = sumDivs[ j ] + i |
|||
end |
|||
end |
|||
for n = 2, MAX_NUMBER do |
|||
m = sumDivs[n] |
|||
if m > n then |
|||
if sumDivs[m] == n then print(n, m) end |
|||
end |
|||
end |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
220 284 |
220 284 |
||
1184 1210 |
1184 1210 |