Реализация поиска простых делителей

50
14 июня 2018, 10:50

Всем привет, написал код по поиску простых чисел и запоминания этих чисел и их степеней:

int t = 0;
    int i = 2;
    int k = 1;
    int z = 0;
    vector<int> q(10);
    vector<int> ak(10);
    int l=phi(p);
    t = l;
    while (i <= t)
    {
        if (t%i == 0)
        {
            t = t / i;
            q[z] = i;
            ak[z] = k;
            k++;
            if (t%i != 0)
            {
                z++;
                k = 1;
            }
        }
        else
        {
            i = i + 1;
        }
    }
}

Получилось очень много кода. Подскажите, пожалуйста, как можно оптимизировать

Answer 1

Я бы не сказал, что его много, его просто мало :), но он не очень удобен и эффективен. Держать два массива для делителей и степеней - неудобно, тем более что это тесно взаимосвязанные вещи. Проще использовать map.

Далее, перебирать все делители тоже смысла не имеет - ну зачем после проверки деления на 2 проверять, например, деление на 6? Идеально для скорости - хранить массив простых чисел и работать с ним; но если это кажется напрасной тратой места :) - то хотя бы проходите просто по нечетным числам, вынеся работу с двойками отдельно.

Словом, я бы предложил такое:

map<unsigned int, unsigned int> factorize(unsigned int n)
{
    map<unsigned int, unsigned int> m;
    while(n > 1 && n%2 == 0)
    {
        m[2]++;
        n /= 2;
    }
    if (n > 1) for(unsigned int i = 3; i*i <= n;)
    {
        if (n%i == 0) { m[i]++; n /= i; continue; }
        i += 2;
    }
    if (n > 1) m[n]++;
    return m;
}

Еще раз - я бы этот код дополнил таблицей простых чисел...

И еще - малое количество кода - не всегда означает эффективное решение. Нередко лучше написать в два раза больше кода, но получить в несколько раз более быстрое решение.

Answer 2

Итак, сравниваем два метода. Полный код тут. Вкратце - чтоб не просто делители считать, но еще и использовать как-то наши vector и map, я еще и считаю общую сумму делителей и их степеней. Так, первое, что в голову пришло. Ну, и пришлось переписать немного код Qwertiy, чтоб лишнего поменьше делал...

Проверяю примерно так:

{
    muTimer mu;
    unsigned int total = 0;
    for(unsigned int n = 2; n < N; ++n)
    {
        auto m = Qwertiy(n);
        for(auto [p,k] : m) total += p + k;
    }
    mu.stop();
    cout << "Qwertiy: " << total << " for " << mu.duration<muTimer::ms>() << " ms\n";
}

Заряжаем на 5 миллионов чисел:

Harry  : 2479739720 for 4377 ms
Qwertiy: 2479739720 for 4056 ms

Компилировал VC++2017, 64-разрядное приложение, запускал на своей Intel(R) Core(TM) i5-2500 CPU @ 3.30 GHz 8G RAM --- Windows 7 x64.

Разница есть, но назвать ее критичной я не могу :) Вот если дописать резервирование памяти для вектора - тогда да, разница с 10% вырастает до 20%.

Кстати, замена map на unordered_map только ухудшает дело.

Update

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

Harry    : 647967786 for 9054 ms
PHarry   : 647967786 for 105 ms
Qwertiy  : 647967786 for 8975 ms
VecPrimes: 647967786 for 95 ms

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

Answer 3

https://ideone.com/HVD59h

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
vector < pair <unsigned, unsigned> > dividers(unsigned n)
{
  vector < pair <unsigned, unsigned> > res;
  if (n <= 1)
    res.push_back(make_pair(n, 1));
  for (unsigned q=2; q*q<=n; ++q)
  {
    if (n % q == 0)
    {
      unsigned d;
      for (d=0; !(n%q); ++d) n/=q;
      res.push_back(make_pair(q, d));
    }
  }
  if (n > 1)
    res.push_back(make_pair(n, 1));
  return res;
}
string fragment(const pair <unsigned, unsigned> &p)
{
  char res[256];
  sprintf(res, p.second==1 ? "%d" : "%d^%d", p.first, p.second);
  return res;
}
void print(const vector < pair <unsigned, unsigned> > &v)
{
  transform(v.begin(), --v.end(), ostream_iterator<string>(cout, " * "), fragment);
  cout << fragment(*v.rbegin()) << endl;
}
int main()
{
  print(dividers(126));
  print(dividers(1));
  print(dividers(17));
  print(dividers(128));
  print(dividers(0));
  print(dividers(121));
  return 0;
}
2 * 3^2 * 7
1
17
2^7
0
11^2
READ ALSO
Выбор папки. C++. MFC

Выбор папки. C++. MFC

Как вызвать Dialog для выбора папки, не для файла, а именно для папки?

70
Как сделать сайдбар по всей высоте родителя?

Как сделать сайдбар по всей высоте родителя?

Как сделать блок "Соседние статьи" справа по всей высоте родительского блока? Раньше у родительского блока была задана height, но ее пришлось...

78
CSS3: repeating-linear-gradient

CSS3: repeating-linear-gradient

Я сделала следующий гардиент для фона:

70
Как при увеличении одного блока сделать так чтобы он не толкал другой блок

Как при увеличении одного блока сделать так чтобы он не толкал другой блок

Возможно ли сделать так, чтобы при увеличении одного блока он не толкал другой блок без использования position: absolute? Как видите я тут поставил...

62