IPB
ЛогинПароль:

> Внимание! Действует предмодерация

Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.

> Замечательные числа
сообщение
Сообщение #1


Гость






Числа и СуперЧисла Смита
Цитата
Составное число называется Числом Смита, если сумма его цифр равна сумме всех чисел, образующихся разложением исходного числа на простые множители. Число Смита называется СуперЧислом Смита, если сумма его цифр является Числом Смита.


Приведенная ниже программа ищет СуперЧисло Смита с номером X...
{
Функция для подсчета суммы цифр числа N
}
function GetOneDigits(n: LongInt): Integer;
var s: Integer;
begin
s := 0;
while n <> 0 do begin
Inc(s, n mod 10);
n := n div 10;
end;
GetOneDigits := s
end;

{
Эта функция считает сумму цифр разложения исходного числа N
на простые множители и возвращает в Amount число простых множителей
}
function GetSimpleDigits(n: LongInt; var amount: Integer): Integer;
var
s, factor: Integer;
begin
s := 0; factor := 2;
amount := 0;
repeat
if n mod factor = 0 then begin
s := s + GetOneDigits(factor); Inc(amount);
n := n div factor
end
else Inc(factor)
until n = 1;
GetSimpleDigits := s
end;

{
Функция возвращает N-ное число Смита
}
function GetSmith(n: Integer): LongInt;
var
i, amount: Integer; od, sd: Integer;
count: LongInt;
Found: Boolean;
begin
i := 0; count := 2;
while i <> n do begin
repeat
Inc(count);
Found :=
(GetOneDigits(count) = GetSimpleDigits(count, amount))
and
(amount > 1)
until Found;
Inc(i)
end;
GetSmith := Count
end;

{
Функция проверяет, является ли N числом Смита
}
function IsSmith(n: LongInt): Boolean;
var
i: Integer;
next: LongInt;
begin
i := 0;
repeat
Inc(i); next := GetSmith(i)
until next >= n;
IsSmith := (next = n)
end;

{
Функция возвращает N-ное суперчисло Смита
}
function Super(n: Integer): LongInt;
var
i, count: Integer;
smith: LongInt;
Found: Boolean;
begin
i := 0; count := 0;
while i <> n do begin
Inc(i);
repeat
Inc(count);
smith := GetSmith(count);
Found := IsSmith( GetOneDigits(smith) );
until Found;
end;
Super := smith
end;

var
X: Integer;
{
Пример использования:
}
begin
Write('X = '); ReadLn(X);
WriteLn('Smith super number (X) = ', Super(X));
end.


**********

Update: поскольку вышеприведенная функция поиска Суперчисел Смита работает очень медленно - выкладываю обновленную версию:

Спойлер (Показать/Скрыть)

Немного информации о скорости работы:
СуперСмит5. Старая версия: 62 мс., новая: 1 мс.
СуперСмит100. Старая версия: 7653 мс., новая: 63 мс.
СуперСмит200. Старая версия: 43891 мс., новая: 220 мс.

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Поиск совершенных чисел.
Цитата
Определенный интерес для любителей представляет программа поиска совершенных чисел. Ее схема проста: в цикле для каждого числа проверять сумму его делителей и сравнивать ее с самим числом, - если они равны, то это число совершенное.


Код
Var
  I,N,Summa: LongInt;
  Delitel: Integer;
Begin
  For I := 3 To 34000000 Do Begin
    Summa := 1;
    For Delitel := 2 To Trunc(Sqrt(I)) Do Begin
      N := (I Div Delitel);
      If N * Delitel = I Then Summa := Summa + Delitel + (I Div Delitel);
    End;

    If Int(Sqrt(I)) = Sqrt(I) Then Summa := Summa - Trunc(Sqrt(I));

    If I = Summa Then WriteLn(I, ' - ', Summa);
  End;
End.


Добавлено (volvo):
  • Количество кандидатов на роль совершенных чисел можно значительно сократить, пользуясь тем фактом, что во всех Совершенных числах в двоичной записи сначала идут n единиц, а потом (n - 1) нулей. Это позволяет организовать поиск подобных чисел вот таким, например, образом:
    var
    I, N, Summa: LongInt;
    Delitel: Integer;

    bin, bs: integer; { Счетчики для работы со строками }
    bin_s: string; { Строковое представление Совершенного числа в двоичном виде }
    check: LongInt; { Число - кандидат на роль Совершенного }
    begin

    { Проверит все числа, двоичная запись которых содержит 3 .. 29 символов }
    for bin := 1 to 14 do begin
    bin_s := '';

    { Создаем бинарное представление числа-кандидата на роль Совершенного }
    for bs := 1 to bin do bin_s := '1' + bin_s + '0';
    bin_s := '1' + bin_s;

    { Переводим его из 2 представления в десятичное }
    check := 0;
    for i := 1 to length(bin_s) do check:= check * 2 + (ord(bin_s[i]) - ord('0'));
    { Распечатываем ... }
    writeln(check);

    {
    ... а теперь - проверяем ТОЛЬКО его, пропуская сотни тысяч
    чисел, проверка которых заведомо не приведет к успеху.
    (здесь еще тоже можно пооптимизировать, но результат и так
    выдается практически мгновенно)
    }

    summa := 1;
    for Delitel := 2 to Trunc(Sqrt(check)) do begin
    N := (check div Delitel);
    if N * Delitel = check then inc(Summa, Delitel + (check div Delitel));
    end;
    if Int(Sqrt(check)) = Sqrt(check) then dec(Summa, Trunc(Sqrt(check)));
    if check = Summa then WriteLn(check, ' - ', Summa);
    end;
    end.

Проверка: простое-ли число.
(вполне подходит для не самых больших чисел)
Код

function isPrime(X: word): boolean;
var
i: integer;
Begin
isPrime:=false;
for i:=2 to trunc(sqrt(x)) do
if x mod i = 0 then Exit;
isPrime:=true
End;


Реализация вероятностного алгоритма Миллера-Рабина с 20 раундами.

Для примера выдает простые на отрезке [1000000000,1000100000]

Код

function mulmod(x,y,m:longint):longint; assembler;
asm
mov eax,x
mul y
div m
mov eax,edx
end;

function powmod(x,a,m:longint):longint;
var
r:longint;
begin
r:=1;
while a>0 do
begin
if odd(a) then r:=mulmod(r,x,m);
a:=a shr 1;
x:=mulmod(x,x,m);
end;
powmod:=r;
end;

function isprime(p:longint):boolean;
var q,i,a:longint;
const rounds=20;
begin
if odd(p) then
begin
isprime:=true;
q:=p-1;
while not odd(q) do q:=q shr 1;
for i:=1 to rounds do
begin
a:=Random(p-2)+2;
if powmod(a,p-1,p)<>1 then
begin
isprime:=false;
break;
end;
a:=powmod(a,q,p);
if a<>1 then
begin
while (a<>1) and (a<>p-1) do a:=mulmod(a,a,p);
if a=1 then
begin
isprime:=false;
break;
end;
end;
end;
end else isprime:=(p=2);
end;

var t:longint;
begin
Randomize;
for t:=1000000000 to 1000100000 do if isprime(t) then writeln(t);
end.


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 22.01.2022 2:48
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name