Как найти количество делителей числа паскаль

Хотел написать программу по заданию, но, как оказалось, в который раз я попытался решить практически неразрешимую задачу. Всё никак не мог достичь приемлемой скорости вычислений… Ещё бы. Общее количество делителей заданного числа оказалось равным 2963520000.

Работает, конечно. Только считать будет до скончания веков. Или, если переполнение BigInteger аварийно завершает программу, то до момента переполнения переменной i. Если добавить условие окончания нахождения делителей, то выводить все делители на экран программа будет где-то пару лет.

Artyom2124, Вы уверены? Если программа будет выдавать по 1000 делителей в секунду, она будет работать более месяца, и, если делители записывать в текстовый файл, конечный объём файла будет примерно 160 гигабайт (более 170000000000 символов). Сильно сомневаюсь, что такое задание могли дать в каком-либо учебном заведении.

Artyom2124, может быть, нужно найти все простые делители?

Это я сделал. К счастью, максимальный простой делитель Вашего числа сравнительно маленький, и помещается в тип integer. Общее количество делителей числа не помещается в тип integer, для подсчёта указанной величины я использовал тип real.

Программа факторизации Вашего числа, находит все простые делители, их максимальные степени и общее количество делителей числа:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

const
  hor = '+----+---------+-----------+';
 
var
  s, t: string; {делимое, частное}
  i, j, c, k: integer; {делитель, счётчик, остаток от деления, номер делителя}
  q: real; {общее количество всех делителей}
  d, p: array[0..15] of integer; {массивы делителей и максимальных степеней делителей}
 
begin
  d[0] := 1; {"лишний" нулевой элемент массива для упрощения алгоритма}
  {первое делимое (исходное число):}
  s := '196708423126676569286001022355850789704717014605805349202544575890563591254090079162973668806152370560989633700137089767703775820200092605536123071613442454080946743909994972297960260325884838413934893551073244410428771253965567859';
  i := 2; {начинаем поиск простых делителей с наименьшего простого числа}
  k := 0; {пока что простые делители не найдены, поэтому их количество пока 0}
  while s <> '1' do {делим число на простые делители до тех пор, пока число не станет равным 1}
    begin
      t := ''; {текуще частное пока не найдено}
      c := 0; {остаток от деления пока равен 0}
      for j := 1 to length(s) do {цикл деления числа}
        begin
          c := c * 10 - ord('0') + ord(s[j]); {приписываем к остатку текущую цифру}
          t := t + inttostr(c div i); {находим текущую цифру частного}
          c := c mod i {находим следующий остаток}
        end;
      if c = 0 then {если последний остаток равен 0, то}
        begin {число делится на текущий делитель, разбираемся с делителем}
          if d[k] <> i then {если новый делитель, то}
            begin
              inc(k); {увеличиваем номер делителя}
              d[k] := i {и записываем текущий делитель в массив}
            end;
          inc(p[k]); {подсчитываем количество текущих делителей}
          while t[1] = '0' do delete(t, 1, 1); {убираем из частного незначащие нули}
          s := t {и переписываем его в делимое}
        end
      else inc(i); {иначе, если последний остаток не равен 0, увеличиваем делитель на 1}
    end;
  {печатаем простые делители}
  writeln('Prime divisors:');
  writeln(hor);
  writeln('|  # | divisor | max power |');
  writeln(hor);
  for j := 1 to k do writeln('|', j:3, ' |',  d[j]:7, '|':3, p[j]:6, '|':6);
  writeln(hor);
  {находим и печатаем общее количество делителей}
  q := 1;
  for j := 1 to k do q := q * (p[j] + 1);
  writeln;
  write('Total quantity of all divisors = ', q)
end.

На моём древнем ноутбуке в Pascal ABC программа считает примерно 24 секунды, эта же программа, подрихтованная и запущенная в Free Pascal, считает примерно 4 секунды.

Prime divisors:
+----+---------+-----------+
|  # | divisor | max power |
+----+---------+-----------+
|  1 |   1297  |     6     |
|  2 |   5651  |     2     |
|  3 |   6959  |     5     |
|  4 |  10799  |     2     |
|  5 |  12547  |     1     |
|  6 |  15161  |     4     |
|  7 |  16223  |     1     |
|  8 |  16417  |     4     |
|  9 |  17681  |     4     |
| 10 |  18541  |     4     |
| 11 |  20411  |     6     |
| 12 |  23563  |     6     |
| 13 |  26591  |     7     |
| 14 |  27943  |     1     |
| 15 |  28513  |     3     |
+----+---------+-----------+

Total quantity of all divisors = 2963520000

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

Пояснения по количеству делителей: любой делитель числа может быть представлен в виде произведения степеней всех простых делителей числа, степень при конкретном простом делителе может быть от 0 до упомянутой выше максимальной степени. Таким образом, общее количество делителей равно количеству всех возможных комбинаций степеней при всех простых делителях, иными словами, произведению увеличенных на 1 максимальных степеней для каждого простого делителя.

Напоследок, если строго по заданию… Казалось бы, имеет смысл дописать мою программу… Осталось совсем немного: перебрать все степени при простых делителях, и умножить исходную единицу нужное количество раз на каждый простой делитель, и так 2963520000 раз… Короче, сущий пустяк, думаю, за год можно будет найти все делители заданного числа.

Добавлено через 2 часа 3 минуты
Если желаете, можете

хоть вручную. Сначала принимаете все степени равными 0, и получаете первый делитель:
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651⁰1297⁰
=1

Затем начинаем увеличивать степени, например, в порядке справа налево, и перебираем все возможные комбинации следующим образом: если степень в самом правом сомножителе достигла максимальной по таблице, то обнуляем эту степень, и увеличиваем следующую (вторую справа), и продолжаем в том же духе до тех пор, пока не переполнится и вторая справа степень, тогда увеличиваем третью справа, а вторую справа обнуляем, и так до тех пор, пока набор степеней не будет такой же, как в таблице:

28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651⁰1297¹
=1297
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651⁰1297²
=1682209
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651⁰1297³
=2181825073
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651⁰1297⁴
=2829827119681
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651⁰1297⁵
=3670285774226257
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651⁰1297⁶
=4760360649171455329
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651¹1297⁰
=5651
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651¹1297¹
=7329347
…
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651¹1297⁶
=26900798028467894064179
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651²1297⁰
=31933801
…
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959⁰5651²1297⁶
=152016409658872069356675529
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959¹5651⁰1297⁰
=6959
…
28513⁰27943⁰26591⁰23563⁰20411⁰18541⁰17681⁰16417⁰16223⁰15161⁰12547⁰10799⁰6959¹5651²1297⁶
=1057882194816090730653105006311
…
28513³27943¹26591⁷23563⁶20411⁶18541⁴17681⁴16417⁴16223¹15161⁴12547¹10799²6959⁵5651²1297⁶
=1967084231266765692860010223558507897047170146058 05349202544575890563591254090079162973668806152370 56098963370013708976770377582020009260553612307161 34424540809467439099949722979602603258848384139348 93551073244410428771253965567859

Добавлено через 4 часа 36 минут
Хотя… Если применить что-нибудь получше строк, то… Программа на Free Pascal Compiler для печати заданного количества делителей, начиная с делителя с заданным номером:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

const
  nd = 15;
 
type
  arr = array[1..nd] of integer;
 
const
  d: arr = (1297, 5651, 6959, 10799, 12547, 15161, 16223, 16417, 17681, 18541, 20411, 23563, 26591, 27943, 28513);
  p: arr = (6, 2, 5, 2, 1, 4, 1, 4, 4, 4, 6, 6, 7, 1, 3);
  n = 17;
  m = 100000000000000;
  mn = 2963520000;
 
var
  a: array[1..n] of uint64;
  i, j, c, k: integer;
  q, b, v: longword;
  r: arr;
 
begin
  write('Start number (1..', mn, '): ');
  readln(b);
  write('Count (1..', mn, '): ');
  readln(q);
  v := b - 1;
  for i := 1 to nd do
    begin
      r[i] := v mod (p[i] + 1);
      v := v div (p[i] + 1)
    end;
  dec(r[1]);
  repeat {начало цикла вычисления делителей}
    //write(b:10, ' |'); //раскомментировать для печати номеров делителей
    inc(b);
    {вычисляем и печатаем очередной набор степеней для простых делителей}
    dec(q);
    c := 1; {перенос}
    for i := 1 to nd do
      begin
        r[i] += c;
        if r[i] > p[i] then
          begin
            r[i] := 0;
            c := 1
          end
        else c := 0;
        //write(r[i]:2) //раскоментировать для печати набора степеней
      end;
    //writeln; раскомментировать для печати набора степеней
    {пока очередной делитель равен 1}
    a[1] := 1;
    for i := 2 to n do a[i] := 0;
    {перемножаем очередной делитель на каждый простой делитель d[i], r[i] раз}
    for i := 1 to nd do
      for j := 1 to r[i] do
        begin
          for k := 1 to n do a[k] := a[k] * d[i];
          for k := 1 to n - 1 do
            begin
              a[k + 1] := a[k + 1] + a[k] div m;
              a[k] := a[k] mod m
            end
        end;
    {печатаем найденный делитель}
    k := n;
    while a[k] = 0 do dec(k);
    write(a[k]);
    for k := k - 1 downto 1 do
      begin
        c := m div 10;
        while (c > 10) and (c > a[k]) do
          begin
            write('0');
            c := c div 10
          end;
        write(a[k])
      end;
    writeln
  until (q = 0) or (b > mn); {конец цикла вычисления делителей}
  readln
end.

Делитель числа размещается в массиве, который используется в качестве 17-разрядного длинного числа в 100000000000000-ричной системе счисления. Так как основание системы счисления является степенью числа 10, то перевести такое число в десятичное не вызывает никаких проблем. Большее основание системы счисления применить не получилось из-за целочисленного переполнения.
В программе нет проверки вводимых значений.
можно объединить обе программы.
Можно переделать для вывода делителей в файл.
Можно переделать под Pascal ABC, но неохота из-за танцев с бубном ввиду отсутствия в Pascal ABC достаточно ёмкого целочисленного типа.
Проверить программу очень просто: нужно ввести Start number: 2963520000 и Count: 1, и будет напечатан последний делитель заданного числа, а именно, само заданное число.

Забыли пароль?

Русский ‎(ru)‎