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

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;
        }
    }
}

Я бы не сказал, что его много, его просто мало :), но он не очень удобен и эффективен. Держать два массива для делителей и степеней - неудобно, тем более что это тесно взаимосвязанные вещи. Проще использовать 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;
}

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

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

Итак, сравниваем два метода. Полный код тут. Вкратце - чтоб не просто делители считать, но еще и использовать как-то наши 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

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

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