Search father (x) of the number D(x) and measure time and memory consumed

Question

We define function D(x) as following:

D(x) = x + sum of digits of x + sum of prime factors of x then call x the father of D(x)

Write a program that gets input t at the first line and then gets an input in the next t lines. If that input had father, print YES otherwise NO

For example 12 is the father of 20
20 = 12 + (1 + 2) + (2 + 3)

preferably write a separate function for each of these tasks:

1. Getting sum of the digits of a number
2. Getting prime factors of a number
3. Calculating D(x)

Notice that if you do lots of operations, you may get time limit error.

Time limit: 0.5 seconds
Memory limit: 128 MB

Input:
You get an input number t at the first line and then in the next t lines, you get number n for which you should solve the problem

Output:
Print the answer to each input in t lines.

Example:
Sample input:

2
4
20

Sample output:

NO
YES

I've written the code with python:

# function that returns the unique prime factors of number n as a list
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    factors = list(set(factors))
    return factors


# function that returns the sum of digits of number n
def sum_digits(n):
    r = 0
    while n:
        r, n = r + n % 10, n // 10
    return r


# function to calculate the offspring of number X {D(X)}
def Offspring(X):
    DX = X + sum(prime_factors(X)) + sum_digits(X)
    return DX


ChildFather = {i: Offspring(i) for i in range(4, 1001)}
ChildFatherValues = list(set(list(ChildFather.values())))
ChildFather.clear()
Fathers = [i for i in ChildFatherValues if i <= 1000]
ChildFatherValues.clear()
t = eval(input())
for i in range(0, t):
    n = eval(input())
    if n in Fathers:
        print('YES')
    else:
        print('NO')  

I guess this part of code

ChildFather = {i: Offspring(i) for i in range(4, 1001)}
ChildFatherValues = list(set(list(ChildFather.values())))
ChildFather.clear()
Fathers = [i for i in ChildFatherValues if i <= 1000]
ChildFatherValues.clear()

is the bottle-neck for time limit. since I don't know how to find x by having D(x), I've solved the problem this way:

ChildFather = {i: Offspring(i) for i in range(4, 1001)}  

for numbers 4<= n<= 1000, I've created a dictionary {n:D(n)}

ChildFatherValues = list(set(list(ChildFather.values())))
ChildFather.clear()  

created a list of unique values of the dictionary and deallocated the memory used for the dictionary

Fathers = [i for i in ChildFatherValues if i <= 1000]
ChildFatherValues.clear()  

create a list of values smaller than 1000 and deallocated memory used for the original list

t = eval(input())
for i in range(0, t):
    n = eval(input())
    if n in Fathers:
        print('YES')
    else:
        print('NO')  

If a given number exists n in the final provided list, I understand that n can be written as D(m)=m+sum of digits of m + sum of prime factors of m so n has the father m and I'll print Yes otherwise NO
But seems that the program is not efficient.

1. How can I measure the time consumed by this python program at run-time?
2. How can I measure the memory consumed by this python program at run-time?
   (I'm new to python and am coding with sublime text 3 in Linux Ubuntu)
3. Is there any more efficient way of writing the code?

Answer 1

PEP-8

Try to stick to PEP-8. So snake_case for variable and method names and a lot of other guidelines. Check any other Code Review Python post for tips from people who can explain this better than me.

Memory

Since you have 128MB of memory available, and a list of 1000 integers (l = list(range(1000)); sys.getsizeof(l) + sum(map(sys.getsizeof, l))) takes only 37kb on my system, I would not worry about clearing intermediate results.

Pre-calculate the primes to 1000

If the input number never goes beyond 1000, pre-calculating all the primes will be the fastest and most efficient. Here is method rwh_primes from this SO post adapted for Python 3:

def primes(n):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]

This takes about 50µs on my PC.

prime_factors

You do some of unnecessary calls to set and list. I would implement this as a generator, and store it further upstream as a set:

def prime_factors(n):
    for factor in PRIMES:
        if factor > n**.5:
            yield n
            return
        while not (n % factor): # n is divisible by factor
            yield factor
            n //= factor
            if n == 1:
                return

sum_digits

This one looks okay. You could use divmod, but that is a matter of taste.

offspring

No need for the intermediate DX:

def offspring(x):
    return x + sum(set(prime_factors(x))) + sum_digits(x)

Main guard

Keep the main logic behind a if __name__ == '__main__': guard.

eval

Instead of using eval, since you know it will be int, better use int(). eval can be dangerous, since it can execute arbitrary code. If you need to interpret a python literal, use ast.literal_eval.

Then you do something very inefficient by creating a dict, then take only the values, apply list, set and list again. Easiest would be to just use a set-comprehension:

all_offspring = {offspring(i) for i in range(1, 1001)}

This will include some numbers over 1000, but this extra memory should be negligible.

Test

You can spoof input on your system by something like

test_case = '''2
4
20'''
input = iter(test_case.split('\n')).__next__

main

if __name__ == '__main__':
    PRIMES = primes(1000)
    all_offspring = {offspring(i) for i in range(1, 1001)}
    t = int(input())
    for i in range(t):
        n = int(input())
        if n in all_offspring:
            print('YES')
        else:
            print('NO')

Timing

To time it you can use timeit module. There are enough posts on SO about this, and for memory usage.