Nickolay.info. Алгоритмы. Совершенные числа

Написать программу вычисления совершенных чисел, не превосходящих заданного числа N. Совершенным называется такое число, сумма делителей которого совпадает с самим числом (учитываются все положительные делители, отличные от самого числа, например, 6=1+2+3).

var n,s,i,j:longint;
begin
 n:=10000;
 writeln;
 for i:=1 to n do begin
  s:=0;
  for j:=1 to i div 2 do begin
   if i mod j = 0 then s:=s+j;
  end;
  if s=i then write (i,' ');
  if i mod 1000 = 0 then write ('.');
 end;
end.

Программа довольно примитивна и не использует признаков делимости, так что вложенные циклы будут выполняться всё дольше с ростом N. Следовало бы количество проверяемых делителей каждого числа менять до квадратного корня из этого числа. Подумайте, почему это так. Чтоб не было скучно, каждые 1000 шагов внешнего цикла программа выдаёт на экран символ точки.

Кстати, в пределах до 1 000 000 000 000 существует всего 7 таких чисел:

6 28 496 8128 33550336 8589869056 137438691328

Если интересно, дальше следуют

2305843008139952128
2658455991569831744654692615953842176
191561942608236107294793378084303638130997321548169216

Кроме того, все известные на сегодня 47 совершенных чисел - чётные.

Похожая программа на консольном C++:

/*
 Найти совершенные числа в диапазоне от 1 до 1000
 Совершенным называется натуральное число, равное сумме своих делителей
 Пример: 6=1+2+3
*/
#include <conio.h>
#include <iostream.h>
 
int soversh (int n) {
 int s=0;
 for (int j=1; j<=n/2; j++) {
  if (n%j==0) s+=j;
 }
 return (s==n?1:0);
}
 
void main () {
 clrscr();
 for (int n=1; n<=1000; n++) {
  if (soversh(n)!=0) cout << n << ' ';
 }
}

Рейтинг@Mail.ru

вверх гостевая; E-mail