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

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

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

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.

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

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

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