Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2005.11.13;
Скачать: CL | DM;

Вниз

Совершенное число   Найти похожие ветки 

 
Хацкеренок   (2005-10-23 21:58) [0]

uses crt;
{===============================}
procedure sov;
var i,s,k:longint;dd:array[1..100] of longint;z:word;
begin
z:=0;
 for i:=1 to 999999 do
  begin
   gotoxy(3,3);
   write("-",i);
   writeln;
    s:=0;
    for k:=1 to i do
      if i mod k=0 then s:=s+k;
   if s=i then begin inc(z);dd[z]:=i; end;
  end;
 for i:=1 to z do
  write(dd[i]," ");
end;
{===============================}
begin
clrscr;
highvideo;
textcolor(lightgreen);
sov;
readln;
end.


Это прога на паскале находит совершенное число от 1 до 999999, а совершенное число это число, у которого если сложить все его делители, то она будет равна самому числу. Беда в том он проработала 2 с пол. часа, у меня  машина : DDR - 256 MB, AMD 1,62 ГГц, не могу понять почему, не поможете...


 
Kerk ©   (2005-10-23 22:00) [1]

мой давний вариант:

program PerNum; // (c) 2004 Roman Jankovski aka Kerk

{$APPTYPE CONSOLE}

var
 P,Cnt: Byte;
 Num: Int64;
 Tmp: LongWord;

function IsPrime(N: LongWord; Mersenne: Boolean): Boolean;
var
 B: Int64;
 Counter: Byte;
begin
 if N and 1 = 0 then
 begin
   IsPrime := N = 2; Exit;
 end;
 if N mod 3 = 0 then
 begin
   IsPrime := N = 3; Exit;
 end;
 if N mod 5 = 0 then
 begin
   IsPrime := N = 5; Exit;
 end;

 if ((N-1) mod 6 <> 0) and ((N+1) mod 6 <> 0) then
 begin
   IsPrime := False;
   Exit;
 end;

 if not Mersenne then
 begin
   for Counter := 7 to Round(Sqrt(N)) do
     if N mod Counter = 0 then
     begin
       IsPrime := False;
       Exit;
     end;
   IsPrime := True;
   Exit;
 end;

 Counter := 0;
 B := 4;
 while Counter < P do
 begin
   Inc(Counter);
   B := (B*B-2) mod N;
   if B = 0 then
   begin
     IsPrime := True;
     Exit;
   end;
 end;
 IsPrime := False;
end;

begin
 WriteLn("p - Prime Number");
 WriteLn("MersennePrime = 2^p - 1 (* is a Prime Number too *)");
 WriteLn("PerfectNumber = MersennePrime * 2^(p-1)");
 Tmp := 2{=2^1}; Cnt := 0;
 for P := 2 to 31 do
 begin              
   Tmp := Tmp shl 1;
   if IsPrime(P,False) then
   begin
     Num := Tmp - 1;
     if not IsPrime(Num,True) then Continue;
     Inc(Cnt);
     WriteLn("#",Cnt," | p = ",P:2," | MersennePrime = ",
       Num:10," | PerfectNumber = ",(Num * (Tmp shr 1)):20);
   end;
 end;
 Write("Press ENTER..."); ReadLn;
end.


 
SergP.   (2005-10-23 22:06) [2]


> Хацкеренок   (23.10.05 21:58)  


А что есть делителем числа?
1 и само это число являются его делителями?


 
Kerk ©   (2005-10-23 22:07) [3]

SergP.   (23.10.05 22:06) [2]
1 и само это число являются его делителями?


1 - является
само число - нет


 
Хацкеренок   (2005-10-23 22:09) [4]

SergP.   (23.10.05 22:06) [2]

Керк прав, просто забыл, об этом


 
Kerk ©   (2005-10-23 22:10) [5]

На моем AthlonXP 2200+ программа из [1] выполняется где-то за 0.05-0.06 сек


 
palva ©   (2005-10-23 22:21) [6]

> само число - нет
тогда неправильно в программе автора написано
for k:=1 to i do
нужно
for k:=1 to i-1 do
а для экономии я бы написал
for k:=1 to i div 2 do
Это сократит время работы раза в два.


 
Хацкеренок   (2005-10-23 22:25) [7]

Я больше математик чем программист, поэтому наверное  я не смогу создать такую оптимальную прогу, но не смог бы ты Керк, ябяснить в чем причина столь долгой работы моей программки

ради интереса переписал его на PHP(версия 5.0.1) и запустил, так мой комп через 20 минут завис

<?php
function soovv(&$h)
 {
   $s=0;
   for($k=1;$k<=$h;$k++)
   {
    if ($h % $k==0){$s=$s+$k;};
   }
   if( $s==$h)
   {$soov=1;}
   else
   {$soov=0;};
   return $soov;
 }
//==============================
$z=0;
 for($j=1;$j<=999999;$j++){
   if (soovv($j)==1){$z=$z+1;$dd[$z]=$j;};
}
 for($j=1;$j<=$z;$j++){
  echo($dd[$j]." ");};
$end; ?>


 
Kerk ©   (2005-10-23 22:28) [8]

Хацкеренок   (23.10.05 22:25) [7]
Я больше математик чем программист


Вот только подход у тебя более кодерский, чем математический. Посчитай сколько раз у тебя выполняется ну хотя бы это:

     if i mod k=0 then s:=s+k;

Раскопал вариант [1] с комментариями. На оптимальность не претендую, но это максимум чего я в данной теме добился.

{
 Совершенное число - это число, сумма делителей которого (исключая само число,
 но включая 1) равняется самому числу. Например: 1+2+3=6.
 Эта программа находит первые 8 совершенных чисел.
 Компилируется Delphi или FreePascal.
----------------------------------------------
 (c)2002 Роман Янковский
}
program PerNum;

{$APPTYPE CONSOLE}

var
 P,Cnt: Byte;
 Num: Int64;
 Tmp: LongWord;

function IsPrime(N: LongWord; Mersenne: Boolean): Boolean;
{ является ли число N простым? используется два различных способа:
 один для чисел Мерсенна, другой для остальных. }
var
 B: Int64;
 Counter: Byte;
begin
 if N and 1 = 0 then
 begin
   IsPrime := N = 2; Exit;
 end;
 if N mod 3 = 0 then
 begin
   IsPrime := N = 3; Exit;
 end;
 if N mod 5 = 0 then
 begin
   IsPrime := N = 5; Exit;
 end;

 { Используется теория, что любое простое число можно представить
   в виде 6n+1 или 6n-1. Теория не доказана. }
 if ((N-1) mod 6 <> 0) and ((N+1) mod 6 <> 0) then
 begin
   IsPrime := False; //Число не соответствует теории - значит не простое.
   Exit;
 end;

 if not Mersenne then
 { тут можно было сделать что-то по круче (например, использовать
   ту теорию (см. выше)), но, по-моему, здесь нет смысла в оптимизации,
   т.к. проверяем маленькие числа <= 31 }
 begin
   for Counter := 7 to Round(Sqrt(N)) do
     if N mod Counter = 0 then
     begin
       IsPrime := False;
       Exit;
     end;
   IsPrime := True;
   Exit;
 end;

 Counter := 0;
 { тест Лукаса-Лемье. Число 2^p-1 простое, если число B:
     B[n+1] = (B[n]^2-2) mod (2^p-1), где B[0] = 4
   при каком-то n станет равным нулю (если оно вообще станет нулем,
   то сделает оно это при n < p }
 B := 4;
 while Counter < P do
 begin
   Inc(Counter);
   B := (B*B-2) mod N;
   if B = 0 then
   begin
     IsPrime := True;
     Exit;
   end;
 end;
 IsPrime := False;
end;

begin
 { Число Мерсенна - число вида 2^p-1, когда оно простое. Кто-то там
   доказал, что необходимое условие этого - число p должно быть простым.
   Еще кто-то доказал, что формула (2^p-1)*2^(p-1), (где 2^p-1 - число
   Мерсенна) содержит все четные совершенные числа. Нечетных совершенных
   чисел науке неизвестно. }
 WriteLn("p - Prime Number");
 WriteLn("MersennePrime = 2^p - 1 (* is a Prime Number too *)");
 WriteLn("PerfectNumber = MersennePrime * 2^(p-1)");
 Tmp := 2{=2^1}; Cnt := 0;
 for P := 2 to 31 do
 begin              
   Tmp := Tmp shl 1;
   if IsPrime(P,False) then
   begin
     Num := Tmp - 1;
     if not IsPrime(Num,True) then Continue;
     Inc(Cnt);
     WriteLn("#",Cnt," | p = ",P:2," | MersennePrime = ",
       Num:10," | PerfectNumber = ",(Num * (Tmp shr 1)):20);
   end;
 end;
 Write("Press ENTER..."); ReadLn;
end.


 
SergP.   (2005-10-23 22:33) [9]


> а для экономии я бы написал
> for k:=1 to i div 2 do
> Это сократит время работы раза в два.


А я бы для экономии написал бы
for k:=1 to trunc(sqrt(i)) do
     if i mod k=0 then s:=s+k+(i div k);
s:=s-k;
// и еще затем проверить не является ли число точным квадратом. Если да, то
s:=s-sqrt(i);

Это бы сократило время в х/з сколько раз...


 
SergP.   (2005-10-23 23:09) [10]


>  { Используется теория, что любое простое число можно представить
>    в виде 6n+1 или 6n-1. Теория не доказана. }


А что тут доказывать?

Все числа можно представить в виде: 6n-1 , 6n ,  6n+1 , 6n+2 , 6n+3  , 6n+4

Отсюда видно что не могут быть простыми числа:
6n  - делится на 6
6n+2 - делится на 2
6n+3  - делится на 3
6n+4 - делится на 2

Значит все простые числа  (>3) могут быть представлены в виде 6n+1 или 6n-1


 
Хацкеренок   (2005-10-23 23:18) [11]

для n=4  уже не выполняется


 
Kerk ©   (2005-10-23 23:19) [12]

Хацкеренок   (23.10.05 23:18) [11]

Чего не выполняется?


 
DrPass ©   (2005-10-23 23:22) [13]

Все нечетные числа - простые:
1 - простое
3 - простое
5 - простое
7 - простое
9 - ошибка эксперимента
11 - простое
13 - простое
Количество опытов достаточно, чтобы считать теорию подтвержденной


 
Хацкеренок   (2005-10-23 23:27) [14]

Керк -

SergP.   (23.10.05 23:09) [10]
Значит все простые числа  (>3) могут быть представлены в виде 6n+1 или 6n-1

Для n=4 не выполняется условие 6n+1


 
Kerk ©   (2005-10-23 23:29) [15]

Хацкеренок   (23.10.05 23:27) [14]

Ты уверен что ты математик?
Где сказано, что все числа вида 6n+/-1 простые?


 
SergP.   (2005-10-23 23:42) [16]


> Хацкеренок   (23.10.05 23:27) [14]
> Керк -
>
> SergP.   (23.10.05 23:09) [10]
> Значит все простые числа  (>3) могут быть представлены в
> виде 6n+1 или 6n-1
>
> Для n=4 не выполняется условие 6n+1


НЕ все числа 6n+1 и 6n-1 простые
но все простые числа могут быть представлены в виде 6n+1 и 6n-1

Кстати ваш сабжевый вариант даже не въезжая в [1] можно значительно ускорить с помощью [9]


procedure TForm1.Button1Click(Sender: TObject);
var
i,k,s,d:integer;
begin
for i:=4 to 999999 do
 begin
 d:=trunc(sqrt(i));
 s:=-i;
 for k:=1 to d do if (i mod k) =0 then s:=s+k+(i div k);
 if d*d=i then s:=s-d;
 if s=i then memo1.lines.add(inttostr(s));
 end;
memo1.Lines.add("end");
end;

Выполняется за секунд 15 на моем Athlon-1000



Страницы: 1 вся ветка

Текущий архив: 2005.11.13;
Скачать: CL | DM;

Наверх




Память: 0.52 MB
Время: 0.042 c
14-1130092838
Карелин Артем
2005-10-23 22:40
2005.11.13
Рекомендуем посмотреть интересный ролик в формате Mpeg на эту тем


3-1128259959
alpine
2005-10-02 17:32
2005.11.13
Вопрос по SQL запросу


14-1129952318
boriskb
2005-10-22 07:38
2005.11.13
Москвичи, прошу помощи.


2-1129572350
eagle_ua
2005-10-17 22:05
2005.11.13
Как создать объект в Delhpi?


11-1111410054
stals
2005-03-21 16:00
2005.11.13
У меня тут несколько халявных вопросов...