Генерация всех делителей числа с учетом его простой факторизации

Question

Генерация всех делителей числа с учетом его простой факторизации

Я хочу найти все делители чисел в диапазоне [1,10⁷]. Я знаю, что это может быть решено в O (sqrt (n)). Но перед этим пришлось запустить сито Эратосфена, которое можно легко изменить, чтобы получить простую факторизацию числа (отслеживая один из главных факторов каждого числа). Поэтому мне интересно, будет ли эффективнее генерировать все факторы, используя их первичную факторизацию?
Пусть п = р₁^К₁ * п₂^К₂*….*п_м^К_м

Я думаю, что это обозначение можно получить в O (m + Σk_я) после сита
Я придумал следующий код для генерации факторов после небольшого размышления:

int factors[]={2,5};        // array containing all the factors
int exponents[]={2,2};      // array containing all the exponents of factors
// exponents[i] = exponent of factors[i]
vector <int> ans;           // vector to hold all possible factors

/*
*   stores all possible factors in vector 'ans'
*   using factors and exponents from index l to r(both inclusive)
*/
void gen(int factors[],int exponents[],vector<int>& ans,int l,int r)
{
if(l==r)
{
int temp = 1;
for(int i=0;i<=exponents[l];i++)
{
ans.push_back(temp);
temp *= factors[l];
}
return;
}
gen(factors,exponents,ans,l+1,r);
int temp=factors[l];
int size = ans.size();
for(int i=1;i<=exponents[l];i++)
{
for(int j=0;j<size;j++)
{
ans.push_back(ans[j]*temp);
}
temp *= factors[l];
}
}

Я думаю, что его сложность по времени составляет по крайней мере Ω (без факторов) = Ω (∏ (1 + k_я)).

Итак, мой вопрос:
1) Быстрее ли генерировать факторы таким образом, чем обычно (метод O (sqrt (n)))?
2) Можно ли оптимизировать приведенный выше код?

2

algorithm c++factorization primes

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Первая наиболее очевидная оптимизация — это предварительно выделить вектор ответов. Вы точно знаете, сколько будет факторов (поскольку вы уже дали формулу как ∏ (1 + k_я)).

Если вы сами управляете стеком вместо рекурсии, вы получите наиболее оптимальное решение (для каждого фактора потребуется только 1 поиск и 1 умножение).

Что-то вроде этого?

int factors_count = 1;
for (int i = 0; i < r; ++i)
{
factors_count *= 1+exponents[i];
}
ans.resize(factors_count);
ans[0] = 1;
int count = 1;
for (int stack_level = 0; stack_level < r; ++stack_level)
{
const int count_so_far = count;
const int prime = factors[stack_level];
const int exponent = exponents[stack_level];
int multiplier = 1;
for (int j = 0; j < exponent; ++j)
{
multiplier *= prime;
for (int i = 0; i < count_so_far; ++i)
{
ans[count++] = ans[i] * multiplier;
}
}
}

Я даже не пытался его скомпилировать, так что будьте внимательны.

5