Найти все делители для заданного числа

@Artyom2124 · Регистрация: 02.07.2020

Студворк — интернет-сервис помощи студентам

Найти все делители для заданного числа:

1967084231266765692860010223558507897047 1701460580534920254457589056359125409007 9162973668806152370560989633700137089767 7037758202000926055361230716134424540809 4674390999497229796026032588483841393489 3551073244410428771253965567859

это программа работает только с маленькими числами

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var i,n,m:integer;
begin
read(n);
m:=n;
i:=1;
while i<=m do
begin
if n mod i=0 then
begin
write(i,' ');
m:=(n div i);
end;
i:=i+1;
end;
write(n);
end.

@mr-Crocodile · 10.07.2020, 16:14

Artyom2124, зачем тебе все делители для этого числа? что ты с ними будешь делать?

но, если реально нужны - то длинная арифметика тебе в помощь!

@Artyom2124 · 10.07.2020, 17:01 **[ТС]**

Такая у меня задача – найти как можно больше положительных делителей заданного числа. 1967084231266765692860010223558507897047 1701460580534920254457589056359125409007 9162973668806152370560989633700137089767 7037758202000926055361230716134424540809 4674390999497229796026032588483841393489 3551073244410428771253965567859

@mr-Crocodile · 10.07.2020, 17:06

Сообщение от Artyom2124

Такая у меня задача – найти как можно больше положительных делителей заданного числа.

а сколько уже нашли?

могу 268 делителей скинуть.

@Mike_Boone · 20.07.2020, 13:59

Лучше конечно искать за О(sqrt(n)), но и так работает

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
begin
  var kek : biginteger;
  var str := readlnstring;
  kek := str.ToBigInteger;
  var i := 1;
  while (true) do
  begin 
    if (kek mod i = 0) then
      write(i, ' ');
    i += 1;
  end;
end.

@Cyborg Drone · 21.07.2020, 22:17

Mike_Boone, в Pascal ABC Ваш код на Pascal ABC.NET работать не будет.

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

@Mike_Boone · 21.07.2020, 22:20

Cyborg Drone, извиняйте, ошибся разделом с .NET

@Cyborg Drone · 21.07.2020, 23:02

Ничего страшного, вообще-то.

Если считаете, что Ваш ответ поможет ТС, то можете писать в Pascal ABC и на Pascal ABC.NET, поскольку у всех, как правило, установлен Pascal ABC.NET, потому что древний Pascal ABC сейчас даже найти не так уж и легко. С другой стороны, есть одна несуразность: в большинстве учебных заведений учат "классическому" паскалю (как правило, Turbo Pascal), а в качестве среды программирования рекомендуют Pascal ABC.NET, потому что он бесплатный и запускается в современных Windows без танцев с бубном. Порой даже и не подозревая, что Pascal ABC.NET и старичок Pascal ABC, от которого Pascal ABC.NET произошёл - это далеко не одно и то же.

Короче, может случиться нелепое недопонимание. Поэтому делайте приписку типа "Программа для Pascal ABC.NET".

@Puporev · 22.07.2020, 07:34

Сообщение от Cyborg Drone

древний Pascal ABC сейчас даже найти не так уж и легко.

Однако у нас есть, раздел Паскаль, тема Скачать Паскаль.
https://www.cyberforum.ru/atta... 1448354644

@Cyborg Drone · 24.07.2020, 02:25

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

Сообщение от Mike_Boone

и так работает

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

Сообщение от Artyom2124

Найти все делители

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

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

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

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

Pascal
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 секунды.

Прогон программы

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 минуты
Если желаете, можете

Сообщение от Artyom2124

найти как можно больше положительных делителей заданного числа

хоть вручную. Сначала принимаете все степени равными 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⁶
=196708423126676569286001022355850789704 7170146058053492025445758905635912540900 7916297366880615237056098963370013708976 7703775820200092605536123071613442454080 9467439099949722979602603258848384139348 93551073244410428771253965567859

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

Pascal
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, и будет напечатан последний делитель заданного числа, а именно, само заданное число.

@Mike_Boone · 27.07.2020, 18:15

Cyborg Drone, ну там делителей не мало ( ~ 2*sqrt(N)). Бесконечный цикл в самый раз.

@Cyborg Drone · 28.07.2020, 08:53

Mike_Boone, ну да, при таком времени работы в самый раз. Насчёт делителей. $https://www.cyberforum.ru/cgi-bin/latex.cgi?\small 2\sqrt{N}$ бывает крайне редко: только у таких N, которые суть факториал. Как правило, значительно меньше, например, в данном случае делителей ровно 2963520000, что значительно меньше, чем
2805055601065166546129328260595075049295 8975208022765284852313338733313141696607 246630163899571147712385678084079858.

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

@mr-Crocodile 3053 / 1672 / 657 Регистрация: 19.03.2019 Сообщений: 5,380
	10.07.2020, 16:14
	Artyom2124, зачем тебе все делители для этого числа? что ты с ними будешь делать? но, если реально нужны - то длинная арифметика тебе в помощь! 0

@Artyom2124 0 / 0 / 0 Регистрация: 02.07.2020 Сообщений: 3
	10.07.2020, 17:01 [ТС]
	Такая у меня задача – найти как можно больше положительных делителей заданного числа. 1967084231266765692860010223558507897047 1701460580534920254457589056359125409007 9162973668806152370560989633700137089767 7037758202000926055361230716134424540809 4674390999497229796026032588483841393489 3551073244410428771253965567859 0

@Cyborg Drone Модератор 10352 / 5638 / 3395 Регистрация: 17.08.2012 Сообщений: 17,205
	21.07.2020, 22:17
	Mike_Boone, в Pascal ABC Ваш код на Pascal ABC.NET работать не будет. И ещё. Если публикуете программу на диалекте языка, который отличается от диалекта языка в названии раздела, то указывайте, на каком именно диалекте языка написана Ваша программа. 0

@Mike_Boone online 52 / 35 / 16 Регистрация: 11.02.2018 Сообщений: 221
	21.07.2020, 22:20
	Cyborg Drone, извиняйте, ошибся разделом с .NET 0

@Cyborg Drone Модератор 10352 / 5638 / 3395 Регистрация: 17.08.2012 Сообщений: 17,205
	21.07.2020, 23:02
	Ничего страшного, вообще-то. Если считаете, что Ваш ответ поможет ТС, то можете писать в Pascal ABC и на Pascal ABC.NET, поскольку у всех, как правило, установлен Pascal ABC.NET, потому что древний Pascal ABC сейчас даже найти не так уж и легко. С другой стороны, есть одна несуразность: в большинстве учебных заведений учат "классическому" паскалю (как правило, Turbo Pascal), а в качестве среды программирования рекомендуют Pascal ABC.NET, потому что он бесплатный и запускается в современных Windows без танцев с бубном. Порой даже и не подозревая, что Pascal ABC.NET и старичок Pascal ABC, от которого Pascal ABC.NET произошёл - это далеко не одно и то же. Короче, может случиться нелепое недопонимание. Поэтому делайте приписку типа "Программа для Pascal ABC.NET". 0

@Mike_Boone online 52 / 35 / 16 Регистрация: 11.02.2018 Сообщений: 221
	27.07.2020, 18:15
	Cyborg Drone, ну там делителей не мало ( ~ 2*sqrt(N)). Бесконечный цикл в самый раз. 0

@Cyborg Drone Модератор 10352 / 5638 / 3395 Регистрация: 17.08.2012 Сообщений: 17,205
	28.07.2020, 08:53
	Mike_Boone, ну да, при таком времени работы в самый раз. Насчёт делителей. $https://www.cyberforum.ru/cgi-bin/latex.cgi?\small 2\sqrt{N}$ бывает крайне редко: только у таких N, которые суть факториал. Как правило, значительно меньше, например, в данном случае делителей ровно 2963520000, что значительно меньше, чем 2805055601065166546129328260595075049295 8975208022765284852313338733313141696607 246630163899571147712385678084079858. 0