##### Short Problem Definition:

A Smith number is a composite number, the sum of whose digits is the sum of the digits of its prime factors obtained as a result of prime factorization (excluding 1). The first few such numbers are 4, 22, 27, 58, 85, 94, and 121.

##### Link

##### Complexity:

time complexity is O(sqrt(N))

space complexity is O(sqrt(N))

##### Execution:

There are many ways how to compute the prime composition of a number. I selected one with two optimization steps, there are many more. If there were many numbers to check I would use the Sieve of Eratosthenes to pre-compute the primes. The rest of the solution is straight forward. *Do not forget that prime factors can also contain multiple digits.*

##### Solution:

#!/usr/bin/py def factors(n): f, fs = 3, [] while n % 2 == 0: fs.append(2) n /= 2 while f * f <= n: while n % f == 0: fs.append(f) n /= f f += 2 if n > 1: fs.append(n) return fs def getIntLetterCount(n): return sum([int(l) for l in list(str(n))]) def isSmithNumber(n): return sum([getIntLetterCount(f) for f in factors(n)]) == getIntLetterCount(n) if __name__ == '__main__': n = input() if isSmithNumber(n): print 1 else: print 0

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.