Разложение на простые множители..

[Kernel Panic]

Кто-нить пытался как-то оптимизировать сабж? Максимум, что у меня получилось, - это где-то за 70 секунд (на 120-м пне) определить, что самое большое 32-битное простое - действительно простое (4294836197, по-моему). Т.е. при разложении получилось 1 и само число.

Есть идеи? Просто интересно..

Сообщение отредактировано: Kernel_Panic - 16.04.02, 19:39

[Фауст]

А ты не думал - почему именно сабж является источником почти-необратимых функций, которые сейчас используются для наиболее популярных алгоритмов шифрования? Именно из-за больших затрат ресурсов для решения сабжа.

[Jin X]

Вот пример на TMT.... Работает быстро....

{$S-,B-,R-,Q-}<br>Var<br>   N, i, j: DWord;<br>   Prime: Boolean;<br><br>Begin<br>   N := $FFFFFFFF;<br>   For i := 2 to Trunc(Sqrt(N)) do<br>   Begin<br>      Prime := True;<br>      For j := 2 to Trunc(Sqrt(i)) do<br>         If (i mod j) = 0 then<br>         Begin<br>            Prime := False;<br>            Break<br>         End;<br>      If Prime and ((N mod i) = 0) then WriteLn(i)<br>   End<br>End.

А если заменить DWord на Longint и поставить N := $7FFFFFFF, то можно будет и в BP компилить..... Кстати, простое - это $7FFFFFFF (2147483647), а не $FFFFFFFF.

А если тебе нужно найти все числа, кратные N, то ещё проще....

{$S-,B-,R-,Q-}<br>Var<br>   N, i: DWord;<br><br>Begin<br>   N := $FFFFFFFF;<br>   For i := 2 to Trunc(Sqrt(N)) do<br>      If (N mod i) = 0 then WriteLn(i)<br>End.

[Jin X]

Я тут прогнал немного, извиняюсь ;D
Вот верный вариант программы, раскладывающий число на простые множители....

{$S-,B-,R-,Q-}<br>Var<br>   N, i, j: DWord;<br>   Prime: Boolean;<br><br>Begin<br>   N := $FFFFFFFF;<br>   Repeat<br>      For i := 2 to Trunc(Sqrt(N)) do<br>      Begin<br>         Prime := True;<br>         For j := 2 to Trunc(Sqrt(i)) do<br>            If (i mod j) = 0 then<br>            Begin<br>               Prime := False;<br>               Break<br>            End;<br>         If Prime and ((N mod i) = 0) then<br>         Begin<br>            WriteLn(i);<br>            N := N div i;<br>            Break<br>         End<br>      End<br>   Until not Prime;<br>   WriteLn(N)<br>End.

[zer]

По-моему, выше перебор описан. Попробуй найти документацию по ассиметричной криптографии там описан алгоритм разложения на простые множители. К примеру схема ElGamal. А вторую забыл ???

[Фауст]

Цитата zer, 23.04.02, 11:38:45

По-моему, выше перебор описан. Попробуй найти документацию по ассиметричной криптографии там описан алгоритм разложения на простые множители. К примеру схема ElGamal. А вторую забыл ???

Неверный ответ  - шифр Эль-Гамаля основан на дискретном логарифмировании, на факторизации основан RSA.
Уточнено из источника: http://algolist.manual.ru/defence/well_known/index.php

[esperanto]

:-[
да на данный момент есть разные решения но все они в общем случае принадлежат классу НП то есть экспоненцмальные

один из алгоритмов позваляющих раскладывать  - алг-Ферма ищет множители близкие к корню из числа.


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

[Imperator]

Лучший алгоритм - общее решето числового поля. Как раз сейчас ищу)

Добавлено 28.02.06, 18:55
Нашёл:
http://en.wikipedia.org/wiki/General_Number_Field_Sieve

[Славян]

Подскажите какую-нибудь "стандартную" Си-библиотеку для проверки на простоту (+разложение на простые) для чисел от 2 до 10³², пожалуйста!

[Majestio]

Славян, "стандартной" по твоему запросу нет. Думаю тебе следует скрестить вот этот код разложения (на Си без плюсов перевести несложно, равно как и добавить проверок):

#include <iostream>
#include <vector>
 
void PrimeFactorization(int Value, std::vector<int> &Res) {
  int Div = 2;
  Res.push_back(1);
  while (Value > 1) {
    while (Value % Div == 0) {
        Res.push_back(Div);
        Value /= Div;
    }    
    if (Div == 2) Div++;
    else Div += 2;
  }
}
 
int main() {
  int Value = 10111787;
  std::vector<int> Res;
  PrimeFactorization(Value, Res);
  std::cout << "Value (" << Value << "): ";
  for(const auto &i: Res) std::cout << i << " ";
  return 0;
}

Value (10111787): 1 7 7 17 61 199

... и какую-нить либу для работы с большими целыми, типа этой. Для чистого Си без плюсов не искал.

[macomics]

void PrimeFactorization(int Value, std::vector<int> &Res) {
  int Div = 2, Div2 = 4;
  Res.push_back(1);
  while (Value > 1) {
    while (Value > Div2 && Value % Div == 0) {
        Res.push_back(Div);
        Value /= Div;
    }
    if (Value <= Div2) {
        Res.push_back(Value);
        Value = 1;
    }
    if (Div++ > 2) Div++;
    Div2 = Div * Div;
  }
}

Так будет чуть быстрее

[Славян]

Спасибо, поэкспериментирую, но что-то строки Div++ и Div+=2 несколько напрягают по скорости алгоритма... Хм-м...

[macomics]

(Div++) это (Div = Div + 1)
(Div+=2) это (Div = Div + 2)
Сложение не сильно увеличит сложность. Тем более, что проверка на (Div > 2) это тоже еще одна операция суммирования
Если проверять на делимость с четными числами - это бесполезно после проверки div = 2. А так перебор сокращен вдвое.

Сообщение отредактировано: macomics - 18.06.22, 09:23

[Славян]

Да я тут слегонца глубже задумался и понял, что физически идёт проверка на делимость со всеми нечётными. Ну так это же Г-метод, "детсадовский"!
Надо, конечно, не всемирно-кластерный, с проверкой до 10³⁰⁰, но всё же хоть какой-то "университетский".

[macomics]

Может он и детсадовский (хотя деление и дроби это школа, 1-2 класс), но число 2147483647 с моими дополнениями проверяется меньше секунды и вывод

Value (2147483647): 1 2147483647

Максимально проверяемый делитель 46341

Сообщение отредактировано: macomics - 18.06.22, 10:12

[Славян]

Согласен, просто есть очевидное беспокойство за числа близкие к 10³¹.

[macomics]

10³¹ это примерно 100-битное число?

[Majestio]

Цитата macomics @ 18.06.22, 08:47

Так будет чуть быстрее

Думаю, не совсем правильный алгоритм. Мой при цифре 8 дает результат: 1 2 2 2, твой: 1 2 4. Но число 4 не простое.

[macomics]

Точно. Равно не туда поставил

#include <iostream>
#include <vector>
 
void PrimeFactorization(unsigned int Value, std::vector<int> &Res) {
   unsigned int Div = 2, Div2 = 4;
   Res.push_back(1);
   while (Value > 1) {
//      std::cout << Div << " "; // Лишнее осталось
      while (Value >= Div2 && Value % Div == 0) {
         Res.push_back(Div);
         Value /= Div;
      }
      if (Value < Div2) {
         Res.push_back(Value);
         Value = 1;
      }
      if (Div++ == 2) Div++;
      Div2 = Div * Div;
   }
//   std::cout << std::endl;
}
 
int main() {
  unsigned int Value = 65536;
  std::vector<int> Res;
  PrimeFactorization(Value, Res);
  std::cout << "Value (" << Value << "): ";
  for(const auto &i: Res) std::cout << i << " ";
  std::cout << std::endl;
  return 0;
}

Вот так правильно. Так вывод будет такой

2
Value (8): 1 2 2 2
 
2
Value (65536): 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Добавлено 18.06.22, 11:44
Почему исправить нельзя? Я в прошлом исправлении накосячил. В предыдущем варианте он 3-ки пропускает и идет не только по нечетным.

    #include <iostream>
    #include <vector>
    
    void PrimeFactorization(unsigned int Value, std::vector<int> &Res) {
       unsigned int Div = 2, Div2 = 4;
       Res.push_back(1);
       while (Value > 1) {
          while (Value >= Div2 && Value % Div == 0) {
             Res.push_back(Div);
             Value /= Div;
          }
          if (Value < Div2) {
             Res.push_back(Value);
             Value = 1;
          }
          if (Div++ > 2) Div++;
          Div2 = Div * Div;
       }
    }
    
    int main() {
      unsigned int Value = 65536;
      std::vector<int> Res;
      PrimeFactorization(Value, Res);
      std::cout << "Value (" << Value << "): ";
      for(const auto &i: Res) std::cout << i << " ";
      std::cout << std::endl;
      return 0;
    }

Сообщение отредактировано: macomics - 18.06.22, 11:44

[Mikle]

Цитата macomics @ 18.06.22, 10:12

число 2147483647 с моими дополнениями проверяется меньше секунды

Моя программа на бейсике ищет все простые числа до 2ккк за менее, чем 4 секунды.

[Славян]

Цитата macomics @ 18.06.22, 10:26

10³¹ это примерно 100-битное число?

Да, 103 бита.

[macomics]

Цитата Mikle @ 18.06.22, 15:33

Моя программа на бейсике ищет все простые числа до 2ккк за менее, чем 4 секунды.

Прежде чем хвастаться - выложите алгоритм. Это раздел про алгоритмы, а не про понты.

[Mikle]

Цитата macomics @ 18.06.22, 19:08

выложите алгоритм

Может, всё-таки, не алгоритм, а исходник? Если кому-то интересно - выложу завтра, он на рабочем компьютере. Так что не надо тут про понты рассуждать.
А алгоритмически там - обычное решето Эратосфена.

[Akina]

Ну глупо же - биться за скорость, и при этом генерировать простые числа... что, не умеем взять готовый список и положить в ресурсы или хотя бы в текстовый файл радом с программой? уж вроде скачать такой список совсем не проблема.

[Majestio]

Цитата Akina @ 19.06.22, 18:26

Ну глупо же - биться за скорость, и при этом генерировать простые числа... что, не умеем взять готовый список и положить в ресурсы

Akina, сжалься! Ты наверное не заметил начального условия... разложение для больших чисел, вплоть до 10^32.

Цитата Славян @ 18.06.22, 06:30

(+разложение на простые) для чисел от 2 до 10³², пожалуйста!

[macomics]

Цитата Mikle @ 19.06.22, 18:17

Может, всё-таки, не алгоритм, а исходник?

Исходный текст записывает алгоритм на определенном языке. Если мы не привязываемся к конкретному ЯП, то это алгоритм. Хоть блок-схему нарисуйте и выложите.

Цитата Akina @ 19.06.22, 18:26

Ну глупо же - биться за скорость, и при этом генерировать простые числа... что, не умеем взять готовый список и положить в ресурсы или хотя бы в текстовый файл радом с программой? уж вроде скачать такой список совсем не проблема.

Представляю себе исполняемый файл, у которого в ресурсах +10 Гб текста с простыми числами.

[Majestio]

Цитата macomics @ 19.06.22, 18:49

Представляю себе исполняемый файл, у которого в ресурсах +10 Гб текста с простыми числами.

Не, ну может где-то и есть специфические задачи такие, тогда да - можно эту таблицу всунуть в БД. Но мне такие задачи не встречались.

Добавлено 19.06.22, 18:58

Цитата macomics @ 19.06.22, 18:49

Хоть блок-схему нарисуйте и выложите.

Ну щя таких инструментов валом, например этот.

[macomics]

Цитата Majestio @ 19.06.22, 18:55

Не, ну может где-то и есть специфические задачи такие, тогда да - можно эту таблицу всунуть в БД. Но мне такие задачи не встречались.

Тут вся суть в том, что это текст. Зачем, если включаете в ресурсы числа, хранить их в виде текста? Чтобы наверное потом потратить кучу времени на преобразование текста в число и цикл прохода по строке. Вместо того, чтобы просто индексировать бинарный массив.

Так уж лучше запихнуть в виде bmp 32-bpp. Забавная картинка выйдет.

Сообщение отредактировано: macomics - 19.06.22, 19:13

[Majestio]

Цитата macomics @ 19.06.22, 19:12

Так уж лучше запихнуть в виде bmp 32-bpp. Забавная картинка выйдет.

Ну реализаций "внешнего хранения" можно придумать множество вариантов. Не суть. Я про то, что и вариант Акины, даже с такими предварительными условиями, может дать выхлоп.

[Mikle]

Вот моя реализация поиска простых чисел до 2ккк, находящая все числа на i5-2400 за 3.75 с.: https://gamedev.ru/files/?id=142299

[Majestio]

Mikle, а можешь дать ссылку на инфу, которой ты пользовался при написании?

[Mikle]

Я не пользовался ни чем, кроме общего понятия того, что такое решето Эратосфена. Далее - соображалка.
В общем даже само решето я, можно сказать, изобрёл, а позже уже узнал как это называется.

Сообщение отредактировано: Mikle - 20.06.22, 10:48

[Akina]

Есть готовые таблицы простых как минимум до 10^12 (емнип на oeis.org). На самом деле есть и больше - просто лень искать сейчас.

[macomics]

Цитата Mikle @ 20.06.22, 06:52

Вот моя реализация поиска простых чисел до 2ккк, находящая все числа на i5-2400 за 3.75 с.: https://gamedev.ru/files/?id=142299

Вот теперь хотя бы есть что обсуждать.

Цитата Majestio @ 20.06.22, 09:31

Mikle, а можешь дать ссылку на инфу, которой ты пользовался при написании?

Думаю стоит заглянуть сюда

[Majestio]

Цитата macomics @ 20.06.22, 12:25

Думаю стоит заглянуть сюда

Там пусто

Добавлено 20.06.22, 13:19
Хотя, Mikle, уже решетом поделился.

[macomics]

Действительно пропала ссылка. Когда выкладывал была доступна. Думаю автор закрыл доступ.
Хотя книга находилась поисковиком в открытом доступе на яндекс диске.

Сообщение отредактировано: macomics - 20.06.22, 17:22

[Majestio]

Цитата macomics @ 20.06.22, 17:18

Хотя книга находилась поисковиком в открытом доступе на яндекс диске.

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

[macomics]

МЕТОДЫ ФАКТОРИЗАЦИИ НАТУРАЛЬНЫХ ЧИСЕЛ, Ш.Т. ИШМУХАМЕТОВ, Казанский университет 2011

Простите за капс, но так написано в названии книги автором.
Там 1 глава как раз посвящена генерации простых чисел. Есть алгоритмы решета Эратосфена и решета Аткина. Жаль PDF себе не сохранил пока был доступ.

add: Вот тут эта же книга.

Сообщение отредактировано: macomics - 21.06.22, 12:23

[Majestio]

macomics, пасип!!!