Всем привет   Уважаемые пользователи помогите решить задачу (С + + или Visual C + +) если не трудно. Вот у меня произошла проблема в написать программы:    
 Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением самого себя. Данное натуральное число N. Используя тылькы елементарны арифметичны операцыъ (+, -, *, /) определить все совершенные числа меньше N.   
  Буду очень благодарен. 
  Кто может то посоветуйте учебник чтобы я самостоятельно научился писать программы такого типа.   Спасибо за внимание.

Это сообщение отредактировал(а) Saninho - 4.2.2013, 00:52

Создать массив int[N+1]; (можно размерности N или N-1 если индексироваться от 1 или 2)
Решетом Эратосфена определить простые числа, а для составных - наименьший делитель.
А дальше перебирай числа, находи делители и проверяй на совершенность.

Так довольно сложно. Потом придётся перебирать комбинации простых делителей... Из двух делителей, потом из трёх и т.д. Потом тут будет нужен массив, а есть сомнение, что они разрешены:


Понятно, что тут чем проще, тем не оптимальнее. И самое простое, но совершенно не оптимальное решение    задачи, является ли число n совершенным, заключается в переборе всех чисел, меньших n. Если n делится на такое число без остатка, то его можно добавить в сумму делителей. А после перебора проверить, совпадает ли сумма с самим числом n. Если да, то n - число совершенное. Ну и поверх всего этого сделать цикл по числам n от 1 до N.


Это сообщение отредактировал(а) feodorv - 11.2.2013, 19:32

всех чисел меньших или равным sqrt(n)

Нет, но можно <= n/2 для чётных чисел и <= n/3 для нечётных. Речь ведь идёт о любых делителях, не только простых.

feodorv,
Пыц.

Qu1nt, 
Тыч 

Добавлено через 3 минуты и 7 секунд
Я понимаю, о чём идёт речь, но 

Можно проверять до квадратного корня, для этого извлечение квадратного корня не нужно:


Это сообщение отредактировал(а) math64 - 12.2.2013, 13:47

Можно)))) Но тогда нужно быть осторожнее:

Здесь d*d опасная конструкция с точки зрения переполнения, хотя, конечно, по заданию вряд ли N дадут достаточно большим....

Наверное, имелось в виду 

math64, хороший вариант оптимизации, однако до всякой оптимизации:
...

d * d >= N можно заменить на q >= d; переполнение d * d возможно когда N > 0x80000000 (при 32 битном int; при другой разрядности другое число нулей)
в связи с этим далее условие q > d эквивалентно q != d

Это сообщение отредактировал(а) math64 - 13.2.2013, 07:45

Я не спорю. Просто написано

вместо q > d...



Поскольку d и N - просто int, переполнение возникает уже при N = 0x7ffea811 (46340 * 46340 < 0x80000000u; 46341 * 46341 > 0x80000000u), хотя


Я имел в виду, что, на мой взгляд, лучше написать в таком стиле: