Есть ли более эффективный способ вычисления мощных чисел?

Question

Я пытаюсь создать эффективную функцию для генерации вектора всех powerful numbers до некоторого bound (в конечном итоге я хотел бы, чтобы это ограничение было таким же высоким, как 10^17 или 10^18, что, по моему мнению, находится в пределах максимального значения 64-битное беззнаковое длинное длинное значение - 2^64 - 1).

Самый эффективный метод, который я придумал, размещен ниже. Мой вопрос только в том, есть ли у кого-то лучшее/более эффективное предложение.

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

std::vector<int> powerful(int bound){ 
    int x,y,cnt,num; 
    std::vector<int>* pows = new std::vector<ull>; 
    for(int i = 4; i<bound;i++){ 
     x = i; 
     y=3; 
     cnt = 0; 
     num = x; 
     while(x%2==0){ 
      x/=2; 
      cnt++; 
     } 
     while ((y <= x) && (cnt != 1)) { 
      cnt = 0; 
      while (x % y == 0) { 
       x /= y; 
       cnt++; 
      } 
      y += 2; 
     } 
     if(cnt>1) 
      pows->push_back(num); 
    } 
    return *pows; 
} 

Answer 1

Вместо того, чтобы пытаться перепроектировать номер, чтобы определить, является ли это сильное число, генерировать мощные числа, используя известную формулу: m = a^2 * b^3 (от вашей ссылки)

можно увеличить значения из a и b для достижения полного охвата всех результатов меньше N.

Answer 2

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

Answer 3

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

#include <cstdlib> 
#include <iostream> 
#include <set> 
#include <vector> 

static const int bound = 1000; 
static const std::vector<int> primes = 
    // I'm assuming you can create this by Sieve of Eratosthenes or similar 
    { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, }; // up to sqrt(bound) 

typedef std::vector<int>::const_iterator prime_iter; 

void add_powerful(std::set<int>& p, int v, 
        prime_iter it, prime_iter end, int bound) 
{ 
    if (it == end) { // terminate the recursion 
     p.insert(v); 
     return; 
    } 

    add_powerful(p, v, it+1, end, bound); 
    for (v *= *it * *it; v <= bound; v *= *it) 
     add_powerful(p, v, it+1, end, bound); 
} 

int main() 
{ 
    auto p = std::set<int>{}; 
    add_powerful(p, 1, primes.begin(), primes.end(), bound); 
    for (auto i: p) std::cout << i << std::endl; 
    return EXIT_SUCCESS; 
} 

add_powerful сквозь рекурсивно простых чисел, в каждом случае, умножая v всех полномочия 0,2,3,4 ,. .. (опуская 1) этого простого числа.

Мой быстрый тест согласуется с expected results до 1000.