Tìm nguồn gốc số nguyên

Question

Thuật toán tốt nhất (hiệu quả nhất) để tìm tất cả các gốc số nguyên của một số là gì?

Đó là, được đưa ra một sốn, tôi muốn tìmb (cơ sở) và e (mũ) sao cho

n = b ^e

Tôi muốn lấy tất cả các cặp giá trị có thể có của b và e

Ps: nb và e phải là số nguyên dương.

Answer 1

Tôi nghĩ rằng cách tiếp cận sức mạnh vũ phu nên làm việc: thử tất cả e s từ 2 (1 là một giải pháp tầm thường) trở lên, lấy r = n^1/e, một double. Nếu r nhỏ hơn 2, hãy dừng lại. Nếu không, hãy tính ceil(r)^e và floor(r)^e và so sánh chúng với n (bạn cần ceil và floor để bù đắp lỗi trong biểu diễn điểm nổi). Giả sử các số nguyên của bạn phù hợp với 64 bit, bạn sẽ không cần thử nhiều hơn 64 giá trị của e.

Dưới đây là một ví dụ trong 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; 
} 

Khi gọi với 65536, nó tạo ra sản lượng này:

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

Answer 2

Điều đó phụ thuộc vào kích thước của tác vụ cho dù cách tiếp cận của tôi có phù hợp với nhu cầu của bạn hay không.

Trước hết, có một giải pháp rõ ràng: e = 1, phải không? Từ đó trở đi nếu bạn muốn tìm tất cả các giải pháp: tất cả các thuật toán tôi có thể nghĩ đến yêu cầu để tìm một số yếu tố chính của n. Nếu đây chỉ là một nhiệm vụ độc lập thì không có gì tốt hơn là lực lượng vũ phu trên các số nguyên tố có thể được thực hiện (nếu tôi không sai). Sau khi bạn tìm thấy số nguyên tố đầu tiên p và số mũ tương ứng của nó (tức là số k cao nhất sao cho p^k/n) bạn cần kiểm tra e chỉ số chia của k. Đối với mỗi số mũ l như vậy (một lần nữa l lặp lại tất cả các ước của k), bạn có thể sử dụng tìm kiếm nhị phân để xem gốc thứ l của n là số nguyên (tương đương với việc tìm giải pháp mới).

Answer 3

Đầu tiên tìm ra nguyên tố của n: n = p1e1 p2e2 p3e3 ...

Sau đó tìm ước số chung lớn nhất của ge1, e2, e3 ... bằng công Euclidean algorithm.

Bây giờ cho bất kỳ yếu tố e của g, bạn có thể sử dụng:

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

Và bạn có n = be.

Answer 4

Trộn các phương pháp tiếp cận của interjay và dasblinkenlight. Đầu tiên, hãy tìm tất cả các thừa số nguyên tố nhỏ (nếu có) và các số mũ của chúng trong hệ số chính là n. Giá trị thích hợp của 'nhỏ' tùy thuộc vào n, đối với kích thước trung bình n, p <= 100 có thể là đủ, đối với lớnn, p <= 10000 hoặc p <= 10^6 có thể phù hợp hơn. Nếu bạn tìm thấy bất kỳ yếu tố chính nhỏ nào, bạn biết rằng e phải chia ước số chung lớn nhất của tất cả số mũ bạn đã tìm thấy. Khá thường xuyên, rằng gcd sẽ là 1. Dù sao, phạm vi số mũ có thể sẽ bị giảm, nếu n không có các yếu tố chính nhỏ, bạn biết rằng e <= log(n)/log(small_limit), là mức giảm tốt từ log(n)/log(2), nếu bạn đã tìm thấy một vài thủ tố nhỏ các yếu tố, số gcd của số mũ là g và số máy còn lại của n là m, bạn chỉ cần kiểm tra số chia của g không vượt quá log(m)/log(small_limit).