Форум программистов, компьютерный форум, киберфорум
Наши страницы
PascalABC.NET
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
Ksen Helsing
0 / 0 / 0
Регистрация: 06.05.2014
Сообщений: 12
1

Факторизация (раскладывание числа на множители, нахождение их суммы)

29.05.2014, 23:40. Просмотров 1489. Ответов 21
Метки нет (Все метки)

Помогите, пожалуйста, написать прогу на Pascal ABC. NET на тему: Факторизация (должна раскладывать число на множители, находить их сумму и т.д)
Буду очень признательна
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2014, 23:40
Ответы с готовыми решениями:

Нахождение суммы всех цифр числа от 10 до 10000
Напишите программу для нахождения суммы всех цифр числа от 10 до 10000 . Через...

Нахождение суммы и произведения цифр введенного числа
С клавиатуры вводится натуральное число N. Необходимо написать программу...

Нахождение суммы цифр заданного натурального числа
найти сумму цифр заданного натурального числа.

Вычисление суммы цифр целого числа (нахождение суммы цифр целого числа)
Составить и отладить программу, используя указанные в скобках процедуры или...

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

21
rassamaha42
0 / 0 / 4
Регистрация: 22.03.2011
Сообщений: 39
01.06.2014, 13:21 2
Привет можно поточнее про факторизацию?
0
Ksen Helsing
0 / 0 / 0
Регистрация: 06.05.2014
Сообщений: 12
01.06.2014, 22:56  [ТС] 3
Эта программка должна разбивать числа на простые множители и искать делители, а так же находить их сумму
0
erl27
894 / 742 / 832
Регистрация: 06.09.2013
Сообщений: 1,561
02.06.2014, 12:35 4
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
var
  N, S: int64;
  
begin
  write('N = ');
  readln(N);
  writeln;
  if N = 0 then writeln('0 не имеет делителей')
  else begin
    writeln('Множители числа ', N, ':');
    if N < 0 then N := -N; //отрицательное число заменяем на положительное
    S := 1;
    write(' ', 1);
    var d := 2; //наименьший делитель
    while N > 1 do
      if N mod d = 0 then begin //если N делится на d
        N := N div d; //то делим N на d
        S += d;
        write(' ', d) //и выводим делитель
      end
      else inc(d); //в противном случае увеличиваем делитель на 1
    writeln;
    writeln('Сумма делителей: ', S)
  end
end.
0
CrazzyBeer
3 / 3 / 6
Регистрация: 24.03.2014
Сообщений: 65
12.06.2014, 22:28 5
А можно какой-то более быстрый алгоритм ?
Нужно факторизировать два числа <=1*10^9 меньше, чем за 1 секунду
0
erl27
894 / 742 / 832
Регистрация: 06.09.2013
Сообщений: 1,561
12.06.2014, 22:51 6
Цитата Сообщение от CrazzyBeer Посмотреть сообщение
меньше, чем за 1 секунду
Не получится. Только чтобы сложить 1 миллиард натуральных чисел необходимо несколько секунд. Запустите следующий код в PascalABC.Net и убедитесь:
Pascal
1
2
3
4
5
6
begin
  var i := 0;
  while i < 1000000000 do inc(i);
  writeln(i);
  writeln('Время: ', milliseconds / 1000, ' секунд')
end.
0
CrazzyBeer
3 / 3 / 6
Регистрация: 24.03.2014
Сообщений: 65
12.06.2014, 23:10 7
Как тогда решить проблему? Есть ли какой-то более быстрый алгоритм?
0
erl27
894 / 742 / 832
Регистрация: 06.09.2013
Сообщений: 1,561
12.06.2014, 23:24 8
Цитата Сообщение от CrazzyBeer Посмотреть сообщение
Есть ли какой-то более быстрый алгоритм?
Эту тему я подробно никогда не изучал, но знаю, что способов факторизации натуральных чисел много - и простых, и довольно сложных. Иных алгоритмов я пока для себя не писал. Но вы должны понять, что разложение числа на простые множители - одна из самых ресурсоемких задач в программировании, как и все, что связанно с простыми числами. В интернете гуляет масса литературы по способам факторизации (например, "Методы факторизации натуральных чисел: Учебное пособие")
0
CrazzyBeer
3 / 3 / 6
Регистрация: 24.03.2014
Сообщений: 65
12.06.2014, 23:26 9
Спасибо за ответы.
0
volvo
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
26146 / 17524 / 6949
Регистрация: 22.10.2011
Сообщений: 30,860
Записей в блоге: 6
12.06.2014, 23:57 10
erl27, сложить миллиард чисел и факторизовать число до миллиарда - разные вещи. Тут в худшем случае будет несколько десятков сложений. Стандартный метод факторизации:
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
procedure Factorization(x: uint64);
var
  i: uint64;
  
  procedure DivX;{ делим на простое число, пока делится без остатка }
  begin
    while (x > 1) and (x mod i = 0) do
    begin
      write(i:4);
      x := x div i;
    end;
  end;
 
begin
  i := 2;
  DivX;
  i := 3;
  while (i < x div 2) do
  begin
    DivX;
    inc(i, 2); { <=> i:=i+2; только нечётные числа }
  end;
  if x > 1 then writeln(x:4);
end;
 
begin
  Factorization(1797969847); // тут почти 2 миллиарда
  writeln('Время: ', milliseconds / 1000, ' секунд')
end.
отрабатывает за доли секунды. Единственное, на что можно напороться - это на простое число, которое не раскладывается на множители, соответственно будет долго находиться единственный делитель, оно же само.
1
CrazzyBeer
3 / 3 / 6
Регистрация: 24.03.2014
Сообщений: 65
13.06.2014, 00:02 11
На эту же проблему напоролся и я. Решается ли она вашим алгоритмом ?
0
Миниатюры
Факторизация (раскладывание числа на множители, нахождение их суммы)  
volvo
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
26146 / 17524 / 6949
Регистрация: 22.10.2011
Сообщений: 30,860
Записей в блоге: 6
13.06.2014, 00:45 12
Сначала проверять только простоту числа, а потом, если оно составное - факторизовать. Если брать числа до 109 (ну, даже чуть больше), то достаточно вот такой проверки:
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
procedure Factorization(x: uint64);
var
  i: uint64;
  
  procedure DivX;
  begin
    while (x > 1) and (x mod i = 0) do
    begin
      write(i:4);
      x := x div i;
    end;
  end;
  
  function isPrime(X: uint64): boolean;
  var
    i: uint64;
  begin
    isPrime := false;
    if not odd(x) and (x <> 2) then exit;
    i := 3;
    while i <= sqrt(x) do
    begin
      if x mod i = 0 then Exit;
      inc(i, 2);
    end;
    isPrime := true;
  end;
 
begin
  if isPrime(x) then
  begin
    writeln(x); exit;
  end;
  
  i := 2;
  DivX;
  i := 3;
  while (i < x div 2) do
  begin
    DivX;
    inc(i, 2);
  end;
  if x > 1 then writeln(x:4);
end;
 
begin
  Factorization(1073676287);
  writeln('Время: ', milliseconds / 1000, ' секунд')
end.
Посмотри, сколько оно теперь выполняется
1
erl27
894 / 742 / 832
Регистрация: 06.09.2013
Сообщений: 1,561
13.06.2014, 01:15 13
Цитата Сообщение от UI Посмотреть сообщение
на что можно напороться - это на простое число
Как раз это я имел виду. А эффективность алгоритма можно улучшить, если простые числа искать не среди всех нечетных чисел, а только среди чисел вида (6n-1) и (6n+1). Работает намного быстрее проверки нечетных чисел.
Вот код для Deelphi 2010, с помощью которого я искал таблицу простых чисел:
Delphi
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
program Primes;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
var
  f: text;
  c: char;
  i, k, d, W, max, count: integer;
  bln, delta, delta1: boolean;
 
begin
  Assign(f, 'D:\primes.dat'); { связываем файловую переменную f c физическим файлом D:\Massiv.dat }
  Rewrite(f); //открываем текстовый файл на запись, предварительно очищая всё его содержимое
  write(f, '');
  randomize;
 { Находим и записываем в файл таблицу простых чисел: }
  k := 2;
  d := 5;
  count := 2;
  delta := true;
  W := 0; //начальное значение длины строки
  writeln(f, ' 2');
  writeln(f, ' 3');
  repeat
    i := 5;
    delta1 := true;
    bln := true;
    //max := round(sqrt(d));
    while sqr(i) <= d {i <= max} do begin
      if d mod i <> 0 then
        if delta1 then begin
          inc(i, 2);
          delta1 := false
        end
        else begin
          inc(i, 4);
          delta1 := true
        end
      else begin
        bln := false;
        break
      end
    end;
    if bln then begin
      inc(count);
      inc(k);
      writeln(f, ' ', d); //ставим "пробел" и выводим простое число
      if count = 100000 then begin
        writeln(k, ' ---> ', d);
        count := 0
      end
    end;
    if delta then begin
      inc(d, 2);
      delta := false
    end
    else begin
      inc(d, 4);
      delta := true
    end;
  until false;
  Close(f); //закрытие файла
  writeln;
  write('Список ', k, ' простых чисел находится в файле "D:\primes.dat"')
end.
1
CrazzyBeer
3 / 3 / 6
Регистрация: 24.03.2014
Сообщений: 65
13.06.2014, 01:29 14
Спасибо огромное. Пару часов голову ломал, дошел бы и сам, но на это ушло бы еще больше . Вы мне очень помогли.

Добавлено через 12 минут
Как можно, кстати, без sqrt сделать? Если, допустим, пользуюсь не Uint64, а обычным Int64. Получается trunc(sqrt(n))?
0
erl27
894 / 742 / 832
Регистрация: 06.09.2013
Сообщений: 1,561
13.06.2014, 01:49 15
Вместо i <= sqrt(x) писать sqr(i) <= x. А зачем вам int64? - он содержит отрицательные числа.
0
CrazzyBeer
3 / 3 / 6
Регистрация: 24.03.2014
Сообщений: 65
13.06.2014, 01:51 16
Pascal
1
 while i*i<=n do
Добавлено через 1 минуту
Диапазон, думаю, больше. Да и работать приходится с компилятором паскаль от a c m p, так что использую это.
0
erl27
894 / 742 / 832
Регистрация: 06.09.2013
Сообщений: 1,561
13.06.2014, 01:54 17
Цитата Сообщение от CrazzyBeer Посмотреть сообщение
Диапазон, думаю, больше
int64 - содержит положительные и отрицательные числа, а Uint64 - только положительные.
0
CrazzyBeer
3 / 3 / 6
Регистрация: 24.03.2014
Сообщений: 65
13.06.2014, 01:57 18
Это я понял, только вот скушает ли это компилятор? Мой то скушал , а вот ихний..
0
erl27
894 / 742 / 832
Регистрация: 06.09.2013
Сообщений: 1,561
13.06.2014, 02:12 19
если нужны числа не более 1 миллиарда, то тогда смело можно использовать integer
0
CrazzyBeer
3 / 3 / 6
Регистрация: 24.03.2014
Сообщений: 65
13.06.2014, 02:14 20
А разве integer не -32.ххх до 32.ххх?
0
13.06.2014, 02:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.06.2014, 02:14

Описать процедуру Digit Count Sum(K,C,S). нахождение количества и суммы цифр числа
описать процедуру Digit Count Sum(K,C,S).нахождение количества цифр целого...

Нахождение суммы ряда, суммирование прекращается когда модуль слагаемого числа становится меньше е
Нахождение суммы ряда, суммирование прекращается когда модуль слагаемого числа...

Нахождение суммы ряда, суммирование прекращается когда модуль слагаемого числа становится меньше е
нахождения суммы ряда, суммирование прекращается, когда модуль слагаемого...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru