In-progress solution for Interview Street challenge: "Unfriendly Numbers"

gistfile1.py

import sys


def find_factors(n):
    factors = [1, n]
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            factors.append(i)
            factors.append(n / i)
    if factors[-1] == factors[-2]:
        factors.pop()
    return factors


def find_number_good_factors(unfriendlys, friendly_factors):
    friendly_factors.remove(1)  # don't need it, maybe a slight perf boost
    for factor in friendly_factors:
        for unfriendly in unfriendlys:
            if unfriendly % factor == 0:
                friendly_factors.remove(factor)
                factors_of_factor = find_factors(factor)
                for i in factors_of_factor:
                    try:
                        friendly_factors.remove(i)
                    except ValueError:
                        pass
                break

    return len(friendly_factors)


if __name__ == "__main__":
    lines = sys.stdin.readlines()
    friendly = int(lines[0].split()[1])
    unfriendlys = list(set([int(x) for x in lines[1].split()]))

    friendly_factors = sorted(find_factors(friendly))
    friendly_factors.reverse()

    print find_number_good_factors(unfriendlys, friendly_factors)

currently times out on the last 3 test cases, either in factors(n) (which seems unlikely because n is always < 10^13 so it shouldn't take >15 seconds even in the worst case) or more likely in finding the good factors