8

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

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

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

2
  • Это НЕ очень много кода. Даже не просто много кода... 20 дек 2017 в 13:50
  • while => for, if += while, q,ak => vector<pair<...>>, (10) => push_back, а ответ может потом напишу.
    – Qwertiy
    20 дек 2017 в 13:57

3 ответа 3

5

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

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

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

19
  • я думал насчет map. Но дальше как к нему обращаться?. Например мне нужен первый делитель.Я к нему уже не смогу обратиться, как m[0]. 20 дек 2017 в 13:54
  • Зачем делать медленный map, когда нужен просто вектор пар?
    – Qwertiy
    20 дек 2017 в 13:55
  • Что значит "первый"? Наименьший? m.begin()->first. Посмотрите по ссылке в ответе - там полностью работоспособный пример с выводом делителей.
    – Harry
    20 дек 2017 в 13:56
  • спасибо, понял) 20 дек 2017 в 13:57
  • @Qwertiy Ну, можно и так. Не думаю, однако, что для реальных делителей (там что-то типа логарифма должно получаться) это критично. Но, конечно же, можно и так.
    – Harry
    20 дек 2017 в 13:57
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

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

1
1

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
0

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.