Как найти максимальный делитель числа паскаль

Если сначала прикинуть, где вообще находятся делители любого числа, то вы обнаружите, что искать делители числа N следует лишь в диапазоне от 0 до N/2, плюс еще делитель N. Поясню на примере числа 36:

 Делители: 1,2,3,4,6,9,12,18 ... и 36. Как видите, все неизвестные делители находятся лишь в первой половине числа, т.е от 1 до N/2 плюс само N, т.е 36.

Это очевидно.

Следующий момент:

Раз мы ищем сумму всех делителей числа, то по логике вещей, те числа, что ближе к N будут иметь сумму делителей больше, чем те, что дальше. Но! Это не всегда так, поэтому в используемом ниже алгоритме диапазон поделен лишь поровну, чего в общем-то достаточно.

Я предложу такой алгоритм:

    int N = 20000;
    int dp_summ = 0, dp=0, ch = 0;

    for(int i=N/2;i<=N;i++)
    {
        int ost = (i%10);
        if(dp>2 && (ost==1 || ost==3 || ost==7 || ost == 9)) continue;

        int curr = 0, curr_dp=0;
        for(int j=1;j<=i/2;j++) if(i%j==0) {curr+=j; curr_dp++;}
        curr+=i;curr_dp++;
        if(curr>dp_summ) {dp_summ=curr; dp=curr_dp; ch = i;}
    }

    printf("Digit is %i   have sum of dividers = %i, diveders = %in",ch,dp_summ,dp);

Также в алгоритм можно внедрить какой-либо другой алгоритм для ускорения. Например, алгоритм Люка для проверки числа на простоту. Но это уже пускай останется вам в качестве самостоятельной работы =)

Задача ваша среднего уровня, интересная даже малость) Вот мне самому интересно найти наиболее корректное решение. Вся обоснованная критика в адрес приведенного выше алгоритма только приветствуется.

Математика и числа

Чётность/нечётность чисел

if Odd (Number) then 
  writeln (Number, ' нечётно')
else
  writeln (Number, ' чётно');

Делимость (кратность) чисел

if Number mod 3 = 0 then
  writeln (Number, ' делится на 3 без остатка');

Наибольший Общий Делитель

{ Евклид (Euclidus) }
function GCD (A: integer;  B: integer): integer;
begin
    while (a <> 0) and (b <> 0) do
       if a >= b then
         a := a mod b
       else 
         b := b mod a;
    GCD := a + b; { один - ноль }
end;

Наименьшее Общее Кратное

function LCM (A: integer;  B: integer): integer; 
begin
     LCM := a * b div GCD (a, b)
end;

Степень

function Power(Base, N: integer): longint;
{ Base - основание , N - степень }
var
   Result: longint;
   i: word;
begin
   Result := 1; { придаём начальное значение }
   for i := 1 to N do
     Result := Result * Base;
 
   Power := Result;
end;

function PowerExp (A, N: real): real;
begin
   if A > 0 then
     PowerExp := Exp ( N * Ln (A) )
   else 
     PowerExp := 0;
end;

Факториал

function Factorial(N: word): longint;
var
   Result: longint;
   i: word;
begin
   Result := 1;
   for i := 1 to N do 
     Result := Result * N;
 
   Power := Result;
end;

function Factorial (N: word): longint;
begin
   if N = 0 then
     Factorial := 1 
   else 
     Factorial := N * Factorial (N - 1);
end;

Вещественный и целый типы

   var
       r : real;
     begin
       r := Round ( 123.456);  {    123 }
       r := Round ( 123.778);  {    124 }
       r := Trunc ( 123.456);  {    123 }
       r := Trunc (-123.778);  {   -123 }
       r := Frac  ( 123.456);  {  0.456 }
       r := Int   ( 123.456);  {  123.0 }
       r := Int   (-123.456);  { -123.0 }
     end.

Случайные числа

  Randomize;
  X := Random (N + 1) - 2 * N;

Как проверить простое ли число?

function isPrime(X: word): boolean;
var
i: integer;
Begin
     isPrime:=false;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     while i <= sqrt(x) do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
 
     isPrime:=true;
End;

Разложение числа на множители

procedure Factorization(x: word);
var i: word;
 
 procedure DivX; { делим на простое число, пока делится без остатка }
 begin
      while (x>1) and (x mod i = 0) do
      begin
           write(i:4);
           x:= x div i;
      end;
 end;
 
begin
     i:=2;
     DivX;
     i:=3;
     while (i < x div 2) do
     begin
           DivX;
           inc(i,2); { <=> i:=i+2; только нечётные числа }
     end;
     if x>1 then writeln(x:4);
end;

Приближённое представление числа в виде дроби

VAR p,q,qmax:integer;
    d, r, min: real;
BEGIN
   write('r, qmax=');
   readln(r, qmax); { r - не целое число, qmax - кол-во итераций (циклов) }
   p:=0; q:=1; min:=r;
   REPEAT
     IF p / q < r
          THEN inc(p)
          ELSE inc(q);
     d:=abs(r-p/q);
     IF d < min THEN
     BEGIN
          min:=d;
          writeln(p:7,'/',q)
     END
   UNTIL (q >= qmax) OR (d = 0);
   readln;
END.

Как работать с отдельными битами?

FUNCTION IsBitOn (n: word; b : BYTE): BOOLEAN; { Проверяем, установлен ли бит }
BEGIN 
     isBitOn:=((n SHR b) AND 1) = 1
END;
 
PROCEDURE SetBitOn (VAR n: Word; b: BYTE); { Устанавливаем бит }
BEGIN
     N:= N OR (1 SHL b)
END;
 
PROCEDURE XORBit (VAR n: Word; b: BYTE); { Переключаем бит }
BEGIN
     N:= N XOR (1 SHL b)
END;

Как узнать из каких цифр состоит целое число?

Var X : Integer;
Begin
 X:=12345;
 Writeln('Число состоит из таких цифр:');
 While X <> 0 Do
  Begin
   Writeln(X Mod 10);
   X:=X Div 10;
  End;
End.

Как быстро делить/умножать числа на степень двойки ?

i:=i shl 1; { i:=i * 2^1}
i:=i shl 2; { i:=i * 2^2}
{и т.д.}
i:=i shr 1; { i:=i div 2^1}
i:=i shr 2; { i:=i div 2^2}
{и т.д.}

Более быстрое разложение числа на множители

{$N+, E+}
 
function FermaFactorization (N : Comp) : Comp;
 
var
  X, Y, R, Z, ZZ : Comp;
 
begin
 Z := Sqrt(N);
 ZZ := Trunc (Z);
 X := 2 * ZZ + 1;
 Y := 1;
 R := Sqr (ZZ) - N;
 while (R <> 0) do
  begin
   R := R + X;
   X := X + 2;
   repeat
    R := R - Y;
    Y := Y + 2;
   until R <= 0;
  end;
 FermaFactorization := (X - Y) / 2;
end;
 
begin
 Writeln (FermaFactorization(917979909) : 0 : 0);
end.

Методика
решение задания № 25 ЕГЭ 2022 в программе PascalABC.NET 3.2

Автор:

Василенко
И.А., учитель математики и информатики МБУ «Школа № 33» г. Тольятти Самарской
области

Теоретический
материал, который необходимо повторить:

1. функции
   целочисленного деления: mod, div.
2. описание
    оператора условия if … then … else …;
3. описание
   операторов повтора: с предусловием, с постусловием, с параметром;
4. описание
   алгоритма нахождения максимального и минимального числа.

Задача 1. ( Информатика.
Единый         Государственный Экзамен. Готовимся к итоговой аттестации :
[учебное пособие] / В.Р. Лещинер, С.С. Крылов. – М.: Издательство
«Интеллект-Центр», 2022)«Подготовка к ЕГЭ по информатике», 2022)

Напишите программу, которая ищет среди целых чисел,
принадлежащих отрезку [400; 450], простые числа, то есть числа, не имеющие
натуральных делителей, не считая единицы и самого числа. Запишите эти числа в
таблицу на экране с новой строки в порядке возрастания.

Описание
переменных (тип переменных: integer):

х- перебирает все
числа от 400 до 450

i –
перебирает все делители для числа х от 1 до х

n— хранит
количество делителей  числа х

Листинг
программы

var x,i,n:integer;

begin

  x:=400;{первоначальное
значение х}

  n:=0;

    while x<=450 do
begin {перебираем числа до 450 включительно}

        for i:=1
to x do begin {перебираем
делители от 1 до x}

        if (x mod
i)=0 then   n:=n+1;
{считаем число делителей для числа х}end;

     if n=2 then writeln
(‘x=’,x,‘   n=’,n);

     n:=0;{обнуляем
число делителей для следующего числа х}

     x:=x+1;{берем
следующее число}

     end;
end.

Результат
работы программы

x=401  
n=2

x=409  
n=2

x=419  
n=2

x=421  
n=2

x=431  
n=2

x=433  
n=2

x=439  
n=2

x=443  
n=2

x=449  
n=2

Ответ на
экзамене:

401

409

419

421

431

433

439

443

449

Задача 2. (Информатика. Единый          
Государственный Экзамен. Готовимся к итоговой аттестации : [учебное пособие] /
В.Р. Лещинер, С.С. Крылов. – М.: Издательство «Интеллект-Центр»,
2022)«Подготовка к ЕГЭ по информатике», 2022)

Напишите программу,
которая ищет среди целых чисел, принадлежащих отрезку [550; 600], простые
числа, то есть числа, не имеющие натуральных делителей, не считая единицы и
самого числа. Запишите эти числа в таблицу на экране с новой строки в порядке
возрастания.

Листинг
программы

var
x,i,n:integer;

begin

  x:=550;{первоначальное
значение х}

  n:=0;

    while x<=600 do begin {перебираем
числа до 600 включительно}

        for i:=1 to x do
begin {перебираем делители от 1 до x}

        if (x mod i)=0 then   n:=n+1; {считаем
число делителей для числа х}end;

     if n=2 then writeln (x);

    
n:=0;{обнуляем число делителей для следующего
числа х}

     x:=x+1;{берем
следующее число}

     end;end.

Ответ на экзамене:

557

563

569

571

577

587

593

599

Задача 3. (Демо-версия
2022)

Пусть М – сумма минимального и
максимального натуральных делителей целого числа, не считая единицы и самого
числа. Если таких делителей у числа нет, то значение М считаем равным 0.

Напишите программу, которая перебирает
целые числа, большие 700000, в порядке возрастания и ищет среди них такие, для
которых значение М оканчивается на 8. Выведите первые пять найденных чисел и
соответствующие им значения М.

Формат вывода: для каждого из пяти таких
найденных чисел в отдельной строке сначала выводится само число, затем –
значение М.

Строки выводятся в порядке возрастания
найденных  чисел.

Количество строк для ответа избыточно.

Работа
с условием задачи

1. Обратим
   внимание, что будем искать минимальный и максимальный делители, не
   считая 1 и самого числа х.
2. Сумму
   минимального и максимального делителей хранит переменная М. Необходимо
   найти первые пять чисел х (контрольная сумма s, при
   выполнении условия M mod
   10=8, должна увеличиваться на единицу, то есть включаем счетчик s:=s+1), в
   порядке возрастания, которые больше числа 700000.
3. Следует
   обратить внимание на формат вывода: для каждого
   из пяти таких найденных чисел в отдельной строке сначала выводится
   само число х, затем – значение М.

Скрытые
условия ( для нас это ошибки) следует отследить на малых числах. Рассмотрим
работу алгоритма на меньших значениях: пусть первоначальное значение х больше 5
(совершенно произвольно взяли число 5). Построим таблицу делителей для чисел
больших 5:

Для
числа 9  найдется один! делитель (в
программе необходимо предусмотреть условие, что минимальный делитель <> максимальному).
Программа завершает перебор чисел при s=5,
то есть находит пять чисел х, для которых сумма максимального (<> x)
и минимального ( <>1) делителей оканчивается на 8. На экране выводятся
пять пар в порядке возрастания х: число х и число М.

Предлагаем
разбить задачу на подзадачи:

1)    
составим программу, которая находит
делители (согласно условию) для одного числа, среди них находит максимальный и
минимальный делитель (min<>max), сумму минимального и максимального
делителя (М) и проверяет условие M
mod 10=8.

2)    
используя, структуру повтора с
постусловием организуем подсчет контрольной суммы и обнуление некоторых переменных:

max:=0;
min:=x;M:=0;d:=0;

при следующем значении х (х:=х+1).

…

REPEAT

      
max:=0; min:=x;M:=0;d:=0;

    …

       
if M mod 10=8 then  begin

       
writeln  (x, ‘   ‘, M); s:=s+1; end; {увеличиваем контрольную сумму s}

    
n:=0;{обнуляем число делителей для следующего
числа х}

     x:=x+1;{берем
следующее число}

  UNTIL s>=5;  {выводим
5 пар (x, M)}

…  

Листинг
программы (при х=6)

var x,i,n,max,min,M, d:integer;

 begin

 x:=6;{первоначальное
значение х большее 5}

  n:=0; max:=0; min:=x;

    for i:=2 to x-1 do begin{перебираем
делители от 2 до (x-1)для числа х}

     if (x mod i)=0 then begin

    
n:=n+1;{считаем число делителей для
числа х}

     d:=i;{переменная хранит текущий делитель}

     {осуществляем поиск макс и мин делителя}

     if d<=min then min:=d;

      
if d>=max then max:=d;

       writeln (i,‘  ‘,n); {выводим
текущее значение делителя и текущее значение n}

      end;end;

     
M:=min+max;

       
if M mod 10=8 then  writeln (x, ‘   ‘, M) else writeln (‘M=0’);

       
end.

Результат работы программы

В
результате у нас первый делитель  — это 2, а второй делитель – это 3.

М=0,
так как (2+3) mod
10 =5.

Если
в программе х:=12, то результат работы программы следующий:

Листинг
программы (при х>5)

var x,i,k,n,max,min,M,d,s:integer;

    begin

 x:=6;{первоначальное
значение х большее 5}

 s:=0; {контрольная сумма, которая накапливает
количество чисел}

    REPEAT

      
max:=0; min:=x;M:=0;d:=0;

    for i:=2 to x-1 do begin{перебираем
делители от 2 до (x-1)для числа х}

     if (x mod i)=0 then begin

  
  n:=n+1;{считаем число делителей для
числа х}

     d:=i;{переменная хранит текущий делитель}

     {осуществляем поиск макс и мин делителя}

     if d<=min then min:=d;

      
if d>=max then max:=d;

      
{writeln (i,’  ‘,n);{выводим текущие значения делителя и n}

      end;end;

           
if min<>max then M:=min+max;

       
if M mod 10=8 then  begin

       
writeln 
(x, ‘  
‘,
M); s:=s+1; end; {увеличиваем контрольную сумму s}

    
n:=0;{обнуляем число делителей для следующего
числа х}

     x:=x+1;{берем
следующее число}

  UNTIL s>=5;  {выводим
5 пар (x, M)}    

    END.

Результат
работы программы

Переменную
n (подсчет
делителей в окончательной программе уберем).

Листинг
программы (х>
700000)

var
x,i,k,max,min,M,d,s:integer;

    begin

 x:=700001;{первоначальное
значение х большее 700000}

 s:=0; {контрольная сумма, которая накапливает
количество чисел}

    REPEAT

      
max:=0; min:=x;M:=0;d:=0;

    for i:=2 to x-1 do begin{перебираем
делители от 2 до (x-1)для числа х}

     if (x mod i)=0 then begin

      d:=i;{переменная
хранит текущий делитель}

     {осуществляем поиск макс и мин делителя}

     if d<=min then min:=d;

      
if d>=max then max:=d;

      
{writeln (i,’  ‘,n);{выводим текущие значения делителя и n}

      end;end;

           
if min<>max then M:=min+max;

       
if M mod 10=8 then  begin

       
writeln 
(x, ‘  
‘,
M); s:=s+1; end; {увеличиваем контрольную сумму s}

     x:=x+1;{берем
следующее число}

    UNTIL s>=5;  {выводим
5 пар (x, M)}    

    END.

Результат
работы программы

Ответ
на экзамене:

Успехов
в учебе!