Smith numbers are numbers such that the sum of the decimal digits of the integers that make up that number is the same as the sum of the decimal digits of its prime factors excluding 1.

By definition, all primes are excluded as they (naturally) satisfy this condition!

Smith numbers are also known as   joke   numbers.



Example
Using the number 166

Find the prime factors of 166 which are: 2 x 83

Then, take those two prime factors and sum all their decimal digits: 2 + 8 + 3 which is 13

Then, take the decimal digits of 166 and add their decimal digits: 1 + 6 + 6 which is 13

Therefore, the number 166 is a Smith number.



Task
Write a program to find all Smith numbers below 10000.



See also
 from Wikipedia:   [Smith number].
 from MathWorld:   [Smith number]. 
 from OEIS A6753:   [OEIS sequence A6753].
 from OEIS A104170:   [Number of Smith numbers below 10^n]. 
 from The Prime pages:   [Smith numbers].


-- Returns a boolean indicating whether n is prime
function isPrime (n)
    if n < 2 then return false end
    if n < 4 then return true end
    if n % 2 == 0 then return false end
    for d = 3, math.sqrt(n), 2 do
        if n % d == 0 then return false end
    end
    return true
end
 
-- Returns a table of the prime factors of n
function primeFactors (n)
    local pfacs, divisor = {}, 1
    if n < 1 then return pfacs end
    while not isPrime(n) do
        while not isPrime(divisor) do divisor = divisor + 1 end
        while n % divisor == 0 do
            n = n / divisor
            table.insert(pfacs, divisor)
        end
        divisor = divisor + 1
        if n == 1 then return pfacs end
    end
    table.insert(pfacs, n)
    return pfacs
end
 
-- Returns the sum of the digits of n
function sumDigits (n)
    local sum, nStr = 0, tostring(n)
    for digit = 1, nStr:len() do
        sum = sum + tonumber(nStr:sub(digit, digit))
    end
    return sum
end
 
-- Returns a boolean indicating whether n is a Smith number
function isSmith (n)
    if isPrime(n) then return false end
    local sumFacs = 0
    for _, v in ipairs(primeFactors(n)) do
        sumFacs = sumFacs + sumDigits(v)
    end
    return sumFacs == sumDigits(n)
end
 
-- Main procedure
for n = 1, 10000 do
    if isSmith(n) then io.write(n .. "\t") end
end