others - 在python中,找到亲和数(amicable numbers)最有效的方法是什么?

我用python编写了一段代码来计算10000以下的亲和数(amicable numbers)之和:


def amicable(a, b):


 total = 0


 result = 0


 for i in range(1, a):


 if a % i == 0:


 total += i


 for j in range(1, b):


 if b % j == 0:


 result += j


 if total == b and result == a:


 return True


 return False



sum_of_amicables = 0


for m in range (1, 10001):


 for n in range (1, 10001):


 if amicable(m, n) == True and m != n:


 sum_of_amicables = sum_of_amicables + m + n



代码在python 2.7.11中的运行时间超过20分钟,我要怎么改进?

时间:

优化到O(n)


def sum_factors(n): 


 result = []


 for i in xrange(1, int(n**0.5) + 1):


 if n % i == 0:


 result.extend([i, n//i])


 return sum(set(result)-set([n]))



def amicable_pair(number):


 result = []


 for x in xrange(1,number+1):


 y = sum_factors(x)


 if sum_factors(y) == x and x != y:


 result.append(tuple(sorted((x,y))))


 return set(result)



运行


start = time.time()


print (amicable_pair(10000))


print time.time()-start



结果


set([(2620, 2924), (220, 284), (6232, 6368), (1184, 1210), (5020, 5564)])


0.180204153061



macbook pro 仅需要0.2秒

添加到答案:


def sum_factors(self, n): 


 s = 1


 for i in range(2, int(math.sqrt(n))+1):


 if n % i == 0:


 s += i


 s += n/i


 return s



def amicable_pair(self, number):


 result = 0


 for x in range(1,number+1):


 y = self.sum_factors(x)


 if self.sum_factors(y) == x and x != y:


 result += x


 return result



不需要集合或数组。提高存储和清晰度。


#fetching two numbers from the user


num1=int(input("Enter first number"));


num2=int(input("enter the second number"));


fact1=[];


fact2=[];


factsum1=0;


factsum2=0;



#finding the factors of the both numbers


for i in range(1,num1):


 if(num1%i==0):


 fact1.append(i)



for j in range(1,num2):


 if(num2%j==0):


 fact2.append(j)



print ("factors of {} is {}".format(num1,fact1));


print ("factors of {} is {}".format(num2,fact2));


#add the elements in the list


for k in range(len(fact1)):


 factsum1=factsum1+fact1[k]



for l in range(len(fact2)):


 factsum2=factsum2+fact2[l]



print (factsum1);


print (factsum2);



#compare them


if(factsum1==num2 and factsum2==num1 ):


 print"both are amicable";


else:


 print"not amicable";




this is my owm understanding of the concept

...