Odnajdywanie liczby całkowitej w liczbach całkowitych

Question

Jaki jest najlepszy (najbardziej wydajny) algorytm znajdowania wszystkich liczb całkowitych mocy liczbowej?

Oznacza to, otrzymuje numern, chce się znaleźćb (zasad) i e (wykładnik) tak, że

n = B ^e

Chcę uzyskać wszystkie możliwe pary wartości: b i e

Ps: nb i e mają być całkowite dodatnie.

Answer 1

myślę podejście brute force powinno działać: spróbować wszystkich e s od 2 (1 rozwiązanie jest trywialne) i do góry, biorąc r = n^1/e, a double. Jeśli r ma mniej niż 2, zatrzymaj się. W przeciwnym razie, obliczyć ceil(r)^e i floor(r)^e i porównać je z n (potrzebujesz ceil i floor, aby zrekompensować błędy w reprezentacjach zmiennoprzecinkowych). Zakładając, że twoje liczby całkowite mieszczą się w 64 bitach, nie musisz wypróbowywać więcej niż 64 wartości e.

Oto przykład w C++:

#include <iostream> 
#include <string> 
#include <sstream> 
#include <math.h> 
typedef long long i64; 
using namespace std; 
int main(int argc, const char* argv[]) { 
    if (argc == 0) return 0; 
    stringstream ss(argv[1]); 
    i64 n; 
    ss >> n; 
    cout << n << ", " << 1 << endl; 
    for (int e = 2 ; ; e++) { 
     double r = pow(n, 1.0/e); 
     if (r < 1.9) break; 
     i64 c = ceil(r); 
     i64 f = floor(r); 
     i64 p1 = 1, p2 = 1; 
     for (int i = 0 ; i != e ; i++, p1 *= c, p2 *= f); 
     if (p1 == n) { 
      cout << c << ", " << e << endl; 
     } else if (p2 == n) { 
      cout << f << ", " << e << endl; 
     } 
    } 
    return 0; 
} 

Wywołany z 65536, produkuje ten wyjściowe:

65536, 1 
256, 2 
16, 4 
4, 8 
2, 16 

Answer 2

To zależy od wymiarów zadania, czy moje podejście zaspokoi Twoje potrzeby.

Przede wszystkim istnieje jedno oczywiste rozwiązanie: e = 1, prawda? Odtąd, jeśli chcesz znaleźć wszystkie rozwiązania: wszystkie algorytmy, które mogę wymyślić, wymagają znalezienia jakiegoś pierwotnego czynnika n. Jeśli to tylko jedno niezależne zadanie, nie można zrobić nic lepszego niż brutalna siła na liczbach pierwszych (jeśli się nie mylę). Po znalezieniu pierwszego czynnika głównego p i odpowiadającego mu wykładnika (tj. Największej liczby k takiej, że p^k/n), musisz sprawdzić tylko e dzielniki k. Dla każdego takiego wykładnika l (ponownie l iteruje wszystkie dzielniki k) można użyć wyszukiwania binarnego, aby zobaczyć, czy pierwszy korzeń n jest liczbą całkowitą (co odpowiada znalezieniu nowego rozwiązania).

Answer 3

Najpierw znajdź na czynniki pierwsze n: n = p1e1 p2e2 p3e3 ...

następnie znaleźć największy wspólny dzielnik g z e1, e2, e3 ... za pomocą Euclidean algorithm.

Teraz dla każdego czynnika e z g, można użyć:

b = p1e1/e p2e2/e p3e3/e ...

I masz n = be.

Answer 4

Wymieszać podejścia interjay i dasblinkenlight. Najpierw znajdź wszystkie małe czynniki pierwsze (jeśli występują) i ich wykładniki w rozkładzie podstawowym na n. Odpowiednia wartość z „małych” zależy od n, dla średnich n, p <= 100 może być wystarczające dla dużejn, p <= 10000 lub p <= 10^6 mogą być bardziej odpowiednie. Jeśli znajdziesz jakieś małe czynniki pierwsze, wiesz, że e musi podzielić największy wspólny dzielnik wszystkich znalezionych wykładników. Dość często, że gcd będzie 1. W każdym razie, zakres możliwych wykładników zostanie zmniejszony, jeśli n ma małe czynniki pierwsze, wiesz, że e <= log(n)/log(small_limit), co jest dobrym zmniejszeniem z log(n)/log(2), jeśli znalazłeś kilka małych prime Współczynniki, gcd ich wykładników to g, a pozostały kofaktor z n to m, wystarczy sprawdzić dzielniki g nie przekraczające log(m)/log(small_limit).