DjangoBB LoFi version

Начало » Python для экспертов » Совершенные числа

Art-master

Окт. 6, 2015 20:22:11

Появилась проблема. Необходимо вывести первые несколько совершенных чисел (число называется совершенным если оно равно сумме его делителей без самого числа). Если просто перебирать все натуральные числа один за другим, будет слишком медленно, даже получаса не хватит чтобы дойти до пятого числа. Поэтому было решено воспользоваться Началами Евклида (кто не знает). Получился следующий код:

def sdel(x): # сумма делителей числа x
	sum = 1
	for i in range(2, int(x**0.5)+1):
		if x % i == 0:
			sum += i
			if i != x / i:
				sum += x / i
	return sum
i = 2
while i < 10*40:
	if sdel(2**i-1) == 1: # если оно простое
		print (2**i-1) * (2**(i-1))
		f = open("perfects.log", "a") # мы еще и в файлик выводили
		f.write(str((2**i-1) * (2**(i-1))) + " ")
		f.close()
	i+=1

Получился такой вот вывод:

6 28 496 8128 33550336 8589869056 137438691328 2305843008139952128

Объясните, почему алгоритм останавливается на 9-ом числе?

Master_Sergius

Окт. 6, 2015 22:35:58

Ну, не совсем останавливается. Вы попробуйте выводить значение i в вашем цикле, да что-то увидите. Да и почему такое странное условие:

while i < 10*40

, почему не сразу 400?

Art-master

Окт. 6, 2015 23:14:15

Да решили число побольше поставить. Т.е. получается, что просто вычислительной способности компа не хватает? А есть какие-то способы еще оптимизировать алгоритм?

PooH

Окт. 7, 2015 06:12:22

Art-master
А есть какие-то способы еще оптимизировать алгоритм?

Если учесть, что к настоящему времени найдено 48 совершенных чисел, предлагаю вбить их в список в программе:)