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

#cpp #алгоритм #математика #инспекция_кода #факторизация

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

int t = 0;
    int i = 2;
    int k = 1;
    int z = 0;
    vector q(10);
    vector 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;
        }
    }
}


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

Ответы

Ответ 1

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

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

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

map factorize(unsigned int n)
{
    map 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;
}


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

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


Ответ 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() << " 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


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


Ответ 3

https://ideone.com/HVD59h

#include 
#include 
#include 
#include 
#include 

using namespace std;

vector < pair  > dividers(unsigned n)
{
  vector < pair  > 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  &p)
{
  char res[256];
  sprintf(res, p.second==1 ? "%d" : "%d^%d", p.first, p.second);
  return res;
}

void print(const vector < pair  > &v)
{
  transform(v.begin(), --v.end(), ostream_iterator(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