Язык Паскаль. Быстрый поиск количества делителей (основная теорема арифметики)

Найдем количество делителей заданного натурального числа, используя основную теорему арифметики.

Если разложение числа на простые множители представить в виде:

a = p1^s1p2^s2p3^s3…pn^sn, тогда количество делителей рассчитывается по формуле: 

(s1+1)*(s2+1)*(s3+1)*..*(sn+1)

Для поиска количества делителей необходимо знать, сколько раз встретился каждый простой множитель числа.

Для хранения этих количеств будем использовать массив.

Программа решения задачи на языке Паскаль (эффективная)

var n, j, k: int64; d: integer; a: array of integer;

begin

  writeln('Введите число');

  readln(n);

  d := Milliseconds;

  setlength(a, 100);//кол-во возможных различных множителей

  j := 2; k := 0;

  writeln('Множители: ');

  while n > 1 do

  begin

    while n mod j = 0 do

    begin

      write(j, ' ');

      a[k] += 1;

      n := n div j;

    end;

    j := j + 1; 

    if n mod j = 0 then k += 1;

  end;

  writeln;

  //writeln('Количество множителей:');

  //a.Where(j->j<>0).Print;

  //writeln;

  writeln('Количество делителей:');

  n := 1;

  for j := 0 to k do

  begin

    if a[j] <> 0 then n := n * (a[j] + 1);

  end;

  writeln(n);

  writeln('Время: ',(Milliseconds - d) / 1000,' с');

end.

Программа решения задачи на языке Паскаль (неэффективная)

var  j, s, n, d: int64;

begin

  writeln('Введите число');

  readln(n);

  d := Milliseconds;

  s := 2;

  for j := 2 to n div 2 do

    if n mod j = 0 then s := s + 1;

  writeln('Количество делителей:');

  writeln(s);

  writeln('Время: ',(Milliseconds - d)/1000,' с');

end.

Результаты запусков

Эффективная программа

Неэффективная программа

Язык Паскаль. Как решить комбинаторную задачу про слова?

Валя составляет шестибуквенные слова из букв слова ГРОЗА. Сколько слов составит Валя, если на первом месте нельзя использовать букву З, на последнее место нельзя ставить гласные буквы, а буква Г должна встретиться в слове не более 1 раза?

Как будем решать задачу

Закодируем буквы цифрами от 1 до 5.

О – 1

А – 2

Г – 3

Р – 4

З – 5

Запустим цикл по числам n из промежутка от 111111 до 555555. Преобразуем число n в строку s процедурой str(n,s).

Выполним проверку условий:

1)      В строке есть символы ‘0’, ‘6’, ‘7’, ‘8’, ‘9’

2)      Последний символ строки – это ‘1’ или ‘2’

3)      Количество символов ‘3’ меньше или равно 1

4)      Первый символ строки – это ‘5’

Если 1-ое условие ложно и 2-ое условие ложно и 3-е условие истинно и 4-ое условие ложно, то будем увеличивать счетчик подходящих слов t на 1.

Программа решения задачи на языке Паскаль

var n,t:integer; f1,f2,f3,f4:boolean;

    s:string;

begin

  for n:=111111 to 555555 do

  begin

    str(n,s);

    f1:=('0' in s) or ('6' in s) or ('7' in s) or ('8' in s) or ('9' in s);

    f2:=s[6] in ['1','2'];

    f3:=s.CountOf('3')<=1;

    f4:=s[1]='5';

    if (not f1) and (not f2) and f3 and (not f4) then t+=1;

  end;

  writeln('Количество слов, которые составит Валя: ',t);

end.

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

Данная программа нашла ответ за 1.166 с.

Как ускорить выполнение программы

Поскольку на последнем месте не может встретиться гласная буква, то есть цифры 1 и 2, то можно начать с числа 111113, на первом месте не может стоять буква З, то есть цифра 5, значит можно идти в цикле до числа 455555 и отказаться от проверки 4-ого условия.

В этом случае программа нашла ответ за 0.884 с.

Язык Паскаль. Разложение натурального числа на простые множители

Как разложить число на множители? Вспомним математику основной школы.

Выполним разложение чисел 360, 192, 36, 44 на простые множители.

В этой публикации приведем код программы для получения простых множителей некоторого натурального числа N.

Как будем решать задачу

Возьмем за первый предполагаемый множитель первое простое число j=2. Организуем внешний цикл пока число больше 1. В этом цикле организуем внутренний цикл пока число делится на j без остатка. Во внутреннем цикле будем уменьшать число в j раз и выводить множитель j на экран. Как только число перестанет делится на множитель j (перестанет работать внутренний цикл), во внешнем цикле увеличим j на 1.

Программа решения задачи на языке Паскаль

var n,j:int64;

begin

  writeln('Введите число');

  readln(n);

  j:=2;

  while n>1 do

  begin

    while n mod j = 0 do

    begin

      writeln('Множитель ',j);

      n:=n div j;

    end;

    j:=j+1;

  end;

end.

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

Запуск 1

Запуск 2

Решето Эратосфена на языке Паскаль (поиск простых чисел быстро)

В этой публикации решим следующую задачу:

Вывести все простые числа из некоторого диапазона с использованием алгоритма "Решето Эратосфена".

Простое число - это натуральное число, имеющее ровно 2 делителя: 1 и само число. Например, 2, 3, 5, 7, 11.

Для быстрого поиска простых чисел будем использовать алгоритм "Решето Эратосфена", заключающийся в просеивании последовательности чисел так, что составные числа последовательности вычеркиваются.

Идея алгоритма

В упорядоченной последовательности натуральных чисел возьмем число k, равное 2 – первому простому числу, и вычеркнем из последовательности все числа, кратные k: 2k, 3k, 4k, …, ik (ik≤N). Далее, в качестве k возьмем следующее за 2 число – это 3, и вычеркнем все кратные 3 числа (6, 9, 12, …).

Слово "вычеркнем" следует понимать так: сделаем число нулем.

Как будем решать задачу

Последовательность натуральных чисел сохраним в массиве. Номера ячеек отождествим с числами. Ячейки с номерами 0 и 1 должны быть равны 0 (0 и 1 не являются простыми числами).

Внешний цикл запустим по k от 2 до N.

Если ячейка a[k] хранит число, не равное 0, то возьмем j=k и во внутреннем цикле пока j<=N-k, с шагом j=j+k, будем обнулять ячейку a[j].

Приведем код программы на языке Паскаль 

var a:array of integer;

    k,j,n:integer;

begin

  {простые числа до 500}

  n:=500;

  setlength(a,n+1);

  for k:=0 to n do a[k]:=k;

  a[1]:=0;

  for k:=2 to n do

  begin

    if a[k]<>0 then  

      begin 

       j:=k;

       while (j<=n-k) do

        begin

         j:=j+k;

         a[j]:=0;

        end;

      end;

  end;

  a.Where(k->k<>0).print; {вывод элементов массива, не равных 0}

end.

Время выполнения программы

Сравним время выполнения программ для поиска простых чисел в диапазоне от 0 до 50 000 с использованием алгоритма "Решето Эратосфена" и алгоритма, в котором для каждого числа считается количество его делителей.

Решето Эратосфена

Подсчет количества делителей

var a:array of integer;     k,j,n:integer; begin   var d := Milliseconds;   {простые числа до 50000}   n:=50000;   setlength(a,n+1);   for k:=0 to n do a[k]:=k;   a[1]:=0;   for k:=2 to n do   begin     if a[k]<>0 then         begin         j:=k;        while (j<=n-k) do         begin          j:=j+k;          a[j]:=0;         end;       end;    end;  // a.Where(k->k<>0).print;   println;   println((Milliseconds-d)/1000); end. Время: 0.041 с

var a:array of integer;     k,j,n,p:integer; begin   var d := Milliseconds;   {простые числа до 50000}   n:=50000;   setlength(a,n+1);   for k:=0 to n do a[k]:=0;   a[1]:=0;   for k:=2 to n do   begin     p:=0;     for j:=1 to k div 2 do       if k mod j=0 then p+=1;     if p=1 then a[k]:=k;   end;   //a.Where(k->k<>0).print;   println;   println((Milliseconds-d)/1000); end. Время: 10.894 с

Очевидно, что программа "Решето Эратосфена" ищет простые числа быстрее.

Для промежутка чисел [0; 100 000] время выполнения программы составило 0.096 с; программа, подсчитывающая количество делителей, выполнилась за 46.2 с.

Уменьшить время выполнения программы, подсчитывающей количество делителей, можно за счет поиска сразу двух делителей, идя в цикле до корня квадратного от числа k. 

Таблица простых чисел до 200

Функции count и countof в языке Паскаль (примеры использования в задачах)

Для подсчета количества каких-либо символов, имеющихся в строке, можно использовать функции:

• countof
• count

В чем разница этих функций, и как их применить к решению задач, разберём в этой публикации.

Функция countof

Пусть дана строка

s:='231привет2432';

Вычислим количество цифр '2':

d:=s.countof('2');

Функция s.countof('2') подсчитывает количество цифр 2 в строке s, и в качестве своего аргумента использует символ 2, заключенный в апострофы.

Пример задачи 1

С клавиатуры вводится строка. Найти количество символов 'Z'.

Программа решения на языке Паскаль

var s:string;k:integer;

begin

  readln(s);

  k:=s.Countof('Z');

  println(k);

end.

Пример задачи 2

С клавиатуры вводится строка. Верно ли, что строка содержит символ '9'?

Программа решения на языке Паскаль

var s:string;k:integer;

begin

  readln(s);

  k:=s.Countof('9');

  if k>0 then writeln('Строка содержит цифру 9')

         else writeln('В строке нет цифр 9');

end.

Функция count

Пусть дана строка

s:='flower555';

Вычислим количество цифр '5':

d:=s.count(c->c='5');

Функция s.count(c->c='5') в качестве своего аргумента принимает логическое выражение (условие). Переменная c в данном случае должна быть описана типом char в блоке var.

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

Пример задачи 1

С клавиатуры вводится строка. Найти количество символов 'Z' и 'A'.

Программа решения на языке Паскаль

var s:string;c:char;k:integer;

begin

  readln(s);

  k:=s.Count(c->(c='Z')or(c<='A'));

  println(k);

end.

Результат выполнения программы

Пример задачи 2

С клавиатуры вводится строка. Найти количество символов цифр.

Программа решения на языке Паскаль

var s:string;c:char;k:integer;

begin

  readln(s);

  k:=s.Count(c->(c>='0')and(c<='9'));

  println(k);

end.

Результат выполнения программы

Пример задачи 3

Во введенной строке подсчитать все символы, кроме P.

Программа решения на языке Паскаль

var s:string;k:integer;c:char;

begin

  readln(s);

  k:=s.Count(c->not(c='P'));

  println(k);

end.

Результат выполнения программы