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

[Славян]

Согласен, просто есть очевидное беспокойство за числа близкие к 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