mirror of
https://bitbucket.org/Mattrixwv/projecteulerlua.git
synced 2025-12-06 09:33:58 -05:00
95 lines
2.8 KiB
Lua
95 lines
2.8 KiB
Lua
--ProjectEuler/lua/Problem21.lua
|
|
--Matthew Ellison
|
|
-- Created: 03-19-19
|
|
--Modified: 06-19-20
|
|
--Evaluate the sum of all the amicable numbers under 10000
|
|
--All of my requires, unless otherwise listed, can be found at https://bitbucket.org/Mattrixwv/luaClasses
|
|
--[[
|
|
Copyright (C) 2020 Matthew Ellison
|
|
|
|
This program is free software: you can redistribute it and/or modify
|
|
it under the terms of the GNU Lesser General Public License as published by
|
|
the Free Software Foundation, either version 3 of the License, or
|
|
(at your option) any later version.
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU Lesser General Public License for more details.
|
|
|
|
You should have received a copy of the GNU Lesser General Public License
|
|
along with this program. If not, see <https://www.gnu.org/licenses/>.
|
|
]]
|
|
|
|
|
|
require "Stopwatch"
|
|
require "Algorithms"
|
|
|
|
LIMIT = 10000; --The top number that will be evaluated
|
|
|
|
|
|
--Setup the timer
|
|
local timer = Stopwatch:create();
|
|
|
|
--Setup the variables
|
|
local divisorSum = {}; --Holds the sum of the factors of the subscript number
|
|
|
|
--Start the timer
|
|
timer:start();
|
|
|
|
--Generate the factors of all the numbers < 10000, get their sum, and add it to the list
|
|
for cnt = 1, LIMIT do
|
|
local divisors = getDivisors(cnt); --Get all the divisors of a number
|
|
if(#divisors > 1) then
|
|
table.remove(divisors); --Remove the last entry because it will be the number itself
|
|
end
|
|
divisorSum[#divisorSum + 1] = getSum(divisors); --Add the sum of the divisors to the vector
|
|
end
|
|
--Check every sum of divisors in the list for a matching sum
|
|
local amicable = {};
|
|
for cnt = 1, #divisorSum do
|
|
local sum = divisorSum[cnt];
|
|
--If the sum is greater than the number of divisors then it is impossible to be amicable. Skip the number and continue
|
|
if(sum >= #divisorSum) then
|
|
--We know that divisorSum[cnt] == sum, do if divisorSum[sum] == cnt we have found an amicable number
|
|
elseif(divisorSum[sum] == cnt) then
|
|
--A number can't be amicable with itself, so skip those numbers
|
|
if(sum == cnt) then
|
|
--Add the number to the amicable vector
|
|
else
|
|
amicable[#amicable + 1] = cnt;
|
|
end
|
|
end
|
|
end
|
|
|
|
--Stop the timer
|
|
timer:stop();
|
|
|
|
--Sort the vector for neatness
|
|
table.sort(amicable);
|
|
|
|
--Print the results
|
|
io.write("All amicable numbers less than " .. LIMIT .. " are \n");
|
|
--Print the list of amicable numbers
|
|
for location = 1, #amicable do
|
|
io.write(amicable[location] .. '\n');
|
|
end
|
|
io.write("The sum of all of these amicable numbers is " .. getSum(amicable) .. '\n');
|
|
io.write("It took " .. timer:getMilliseconds() .. " milliseconds to run this algorithm\n");
|
|
|
|
--[[ Results:
|
|
All amicable numbers less than 10000 are
|
|
220
|
|
284
|
|
1184
|
|
1210
|
|
2620
|
|
2924
|
|
5020
|
|
5564
|
|
6232
|
|
6368
|
|
The sum of all of these amicable numbers is 31626
|
|
It took 46.0 milliseconds to run this algorithm
|
|
]]
|