Текущий архив: 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.055 c
