4.2
(5)
Примерное время на чтение статьи: 9 минут

Модуль school, встроенный в последние версии PascalABC.Net, содержит реализацию алгоритмов, часто встречающихся в школьных задачах. Их использование сильно сокращает программный код и упрощает решение задачи. Каждая реализация в основном имеет два формата – для вызова в виде функции и для записи в точечной нотации. Рассмотрим типовые для номера 25 задачи ЕГЭ и их решение двумя способами: без использования функций модуля school и с его помощью.

Нахождение делителей числа

При нахождении нетривиальных делителей натурального числа ? (которые отличны от 1 и самого числа ?) часто предлагается перебирать числа из диапазона от 2 до [?/2] (скобки [] обозначают операцию взятия целой части числа), поскольку на интервале от [?/2]+1 до ?−1 у числа ? нет делителей. При таком подходе для нахождения делителей, например ?=10000 придется перебрать 4999 чисел (от 2 до 5000).

Перебор делителей числа ? можно оптимизировать, учитывая, что наименьший из пары делителей, таких что ?∗?=?, не превышает квадратного корня из ?; нужно только аккуратно обработать случай, когда число ? представляет собой квадрат целого числа. В этом случае для нахождения делителей, например ?=10000 придется перебрать уже 99 делителей (от 2 до 100=sqrt(10000)).

Получается, что для определения количества делителей числа ? достаточно перебирать только числа от 2 до √N; если очередной делитель ? – это точный квадратный корень, добавляем в список делителей только один делитель, если нет – то добавляем пару делителей (?, [?/?]). Потом (или сразу) необходимо добавить к списку делителей единицу и само число ?.

PascalABC модуль school: список делителей числа

В PascalABC.Net для получения списка ????, содержащего все натуральные делители числа ?, включая 1 и ?, могут быть использованы:

  • функция ????????(?), которая в зависимости от типа ?, возвращает значение типа ????<???????> или ????<???64>;
  • расширение ?.???????? – делает то же самое.

Задача

Вывести все делители натурального числа ?.

Способ 1 (без school)

## 
  var n := ReadInteger;
  var lstDel := Lst(1);          // в список делителей добавили 1
  if n > 1 then lstDel.add(N); // числа от 1 имеют два делителя: 1 и N
  var lim := round(sqrt(N));
  for var d := 2 to lim do 
      if n.Divs(d)
      then if d = sqrt(N)
           then lstDel.add(d)
           else begin
                   lstDel.Add(d);
                   lstDel.Add(N div d)
                 end;
  lstDel.Sort;
  println('Делители:', lstDel);  
  println('Количество делителей:', lstDel.Count);

Способ 2 (используя модуль school)

## 
uses school;
  var n := ReadInteger;
  println('Делители:', n.Divisors); 

Разложение числа в произведение простых множителей

Факторизацией натурального числа называется его разложение в произведение простых множителей. Причем такое разложение единственно.

PascalABC модуль school: разложение числа ? на простые множители

В PascalABC.Net для получения списка ????, содержащего все простые делители числа ?, могут быть использованы:

  • функция ?????????(?) – выполняет разложение числа ? типа ??????? или ???64 на простые множители, результат помещается в список ????;
  • расширение ?.????????? делает то же самое.

Задача

Разложить натуральное число ? в произведение простых множителей.

Рассмотрим реализацию решения задачи без использования функции ?????????(?) модуля ??ℎ???, а затем с её использованием.

Способ 1 (без school)

##
  var n := ReadInteger;
  var ans := n.ToString + ' = ';
  var prime := true;
  var lstPrimeDel := new List <integer>;
  for var d := 2 to n do
    begin
      while n mod d = 0 do begin
        lstPrimeDel.Add(d);
        prime := false;
        n := n div d
      end;
      if n = 1 
      then break
      else if (d*d>n) and prime
           then break      
    end;
  if prime then lstPrimeDel.Add(n);
  ans += lstPrimeDel.JoinToString(' * ');
  ans.Println;

Способ 2 (используя модуль school)

##
uses school;
  var n := ReadInteger;
  var rez := Factorize(n);
  var ans := n.ToString + ' = ' + rez.JoinToString(' * ');
  ans.Println;

Другие полезные функции модуля school

PascalABC модуль school: простые числа

  • функция ??????(?) – возвращает список ????, содержащий простые числа на отрезке [2; ?];
  • функция ???????????(?) – возвращает список ????, содержащий первые ? простых чисел;
  • расширение ?.??????? – возвращает ????, если ? – простoе и ????? в противном случае. Переменная ? должна быть типа ??????? или ???64.

PascalABC модуль school: нахождение НОД и НОК пары чисел a и b

  • функция НОД(?,?) – возвращает НОД типа ??????? или ???64;
  • расширение ?.НОД – возвращает НОД для кортежа ?=(?,?) с данными типа ??????? или ???64;
  • функция НОК(?,?) – возвращает НОК типа ???64;
  • функция НОДНОК(?,?) – возвращает кортеж вида (НОД,НОК) для пары чисел ? и ? типа ???64.
##
uses School;
    var (n, m) := ReadInteger2;
    НОД(n, m).Println;
    НОК(n, m).Println;

PascalABC модуль school: список цифр числа

Получение списка ????, содержащего все цифры числа ? в порядке их следования слева направо:

  • функция ??????(?) – возвращает список типа ????<???64>;
  • расширение ?.?????? делает то же, возвращая список типа ????<???????> или ????<???64>.
##
    uses school;
    var n := ReadInteger;
    n.Digits.Sum.print;

Решение типовых задач ЕГЭ

Демо к ЕГЭ 2021

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

Ответ:

3 58153
7 24923
59 2957
13 13421
149 1171
5 34897
211 827
2 87251

Способ 1 (без school)

##
  var (a, b) := (174457, 174505);
  var maxd: integer;
  for var n := a to b do
  begin
    var kd := 0;
    for var d := 2 to n div 2 do
      if n mod d = 0 
      then begin
             kd += 1;
             maxd := d;
           end;
      if kd = 2 then println(n div maxd, maxd)
  end;

Способ 2 (используя модуль school и лямбда-выражения)

##
uses school;
  (174457..174505)         // возврати все числа из диапазона
  .Select(n → Divizors(n)) // получи (Select) из n все его делители
  .Where(L → L.Count = 4)  // оставь те, у кого 4 делителя
  .Foreach(L → Println(L[1], L[2])) // для тех, что остались, выведи первые 2 

Статград вариант ИН2010103

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.

Ответ: 1225043; 1295029; 1442897

Способ 1 (без school)

##
  var (a, b) := (123489567, 223456789);
  var ans := new List<integer>;  //список наибольших нетривиальных делителей
  for var n := a to b do
    if trunc(sqrt(n))=sqrt(n) then
      begin
        var lstDel := new List <integer>; //список нетривиальных делителей N
        var lim := round(sqrt(N));
        for var d := 2 to lim do 
          begin
            if n.Divs(d)
            then if d = sqrt(N)
                 then lstDel.add(d)
                 else begin
                        lstDel.Add(d);
                        lstDel.Add(N div d)
                      end;
            if lstDel.Count > 3 then break;
          end;
        if lstDel.Count = 3 
        then begin
               lstDel.Sort;
               ans.Add(lstDel.Last);
             end;
      end;
  ans.Sort;
  ans.Println;

Способ 2 (используя модуль school)

##
uses school;
    var a := 123489567;
    var b := 223456789;
    var ans := new List<integer>; 
    for var n := a to b do
      if trunc(sqrt(n)) = sqrt(n) then
      begin
        var s := Divisors(n).RemoveLast;
        if s.Count - 1 = 3  then ans.Add(s.last)
      end;
    ans.Sort;
    ans.Println;

Способ 3 (используя модуль school и лямбда-выражения)

##
uses school;
    (123489567..223456789)
    .Where(x → trunc(sqrt(x))=sqrt(x))
    .Select(x → divisors(x))
    .Where(L → L.count = 5)
    .foreach(L → print(L[3])); 

Статград вариант ИН2010201

Рассмотрим произвольное натуральное число, представим его всеми возможными способами в виде произведения двух натуральных чисел и найдём для каждого такого произведения разность сомножителей. Например, для числа 16 получим: 16=16∗1=8∗2=4∗416=16∗1=8∗2=4∗4, множество разностей содержит числа 15, 6 и 0. Найдите все натуральные числа, принадлежащие отрезку [1000000;2000000], у которых составленное описанным способом множество разностей будет содержать не меньше трёх элементов, не превышающих 100. В ответе перечислите найденные числа в порядке возрастания.

Ответ: 1113840; 1179360; 1208844; 1499400

Способ (без school)

##
  var a := 1000000;
  var b := 2000000;
  for var n := a to b do 
  begin
    var count := n - 1 <= 100? 1 : 0;
    var lim := trunc(sqrt(n));
    for var d := 2 to lim do 
    begin
      if n mod d = 0
      then if abs(n div d - d) <=100
           then count += 1
    end;
    if count >= 3 then 
      println(n);
  end;

Способ 2 (используя модуль school)

##
uses school;
  var a := 1000000;
  var b := 2000000;
  for var n := a to b do 
  begin
    var s := Divisors(n);
    var lst := new List<integer>;
    for var i := s.Count - 1 downto (s.count div 2) do 
      lst.add(s[i] - s[s.Count - i - 1]);
    if lst.Count(x → x <= 100) >= 3 then 
      println(n);
  end;

Статград вариант ИН2010301 (Решу ЕГЭ № 33527)

Найдите все натуральные числа, принадлежащие отрезку [101000000;102000000], у которых ровно три различных чётных делителя. В ответе перечислите найденные числа в порядке возрастания.

Ответ: 101075762; 101417282; 101588258; 101645282

Способ (без school)

##
var (a, b) := (101000000, 102000000);
var n := a;
while n <= b do 
  begin
    var keven := 1;  //само число уже чётно и оно делитель себя 
    var lim := trunc(sqrt(n));
    for var d := 2 to lim  do 
      begin
        if n mod d = 0 
        then begin
               if d mod 2 = 0 then keven+=1;
               if (d <> lim) //если d=lim, то будет чётное число чётных делителей
               then if (n div d) mod 2 = 0 then keven += 1;
             end;
        if keven > 3 then break;
      end;
    if keven = 3 then println(n);
    n += 2;  //перебираем только чётные
  end;

Способ 2 (используя модуль school)

##
uses school;
    (101000000..102000000)
    .Where(n → Divisors(n).Count(x → x.IsEven)=3)
    .Println;

P.S. Если Вы заметили ошибку, буду благодарна за комментарии.

Насколько публикация полезна?

Нажмите на звезду, чтобы оценить!

Средняя оценка 4.2 / 5. Количество оценок: 5

Оценок пока нет. Поставьте оценку первым.

Наверх