# Searches for perfect numbers among the integers 1 - 1,000,000.
# This version has an optimization to compute the sum of
# n's factors more quickly by examining only up to sqrt(n).

import math   # for sqrt
import time

# returns the sum of the proper divisors of n
def sum_divisors(n):
    root = int(math.sqrt(n))
    result = sum((k + n // k for k in \
             range(2, root + 1) if n % k == 0)) + 1
    if n == root * root:
        result -= root
    return result

# Runs the given function f, measuring how long it took to run.
# Returns the elapsed runtime at the end of the call.
def measure_runtime(f):
    start_time = time.time()
    f()
    elapsed_time = time.time() - start_time
    return elapsed_time

# Finds and prints all perfect numbers from 1-1000000.
def find_perfect_numbers():
    print("Searching for perfect numbers:")
    perfects = filter(lambda n: n == sum_divisors(n), \
                      range(1, 1000001))
    for p in perfects:
        print(p)

def main():
    runtime = measure_runtime(find_perfect_numbers)
    print("time =", runtime, "sec")

main()