Tạo tất cả các thừa số của một số cho hệ số chính của nó

Question

Nếu bạn đã có hệ số chính xác của một số, cách dễ nhất để có được tập hợp tất cả các yếu tố của số đó là gì? Tôi biết tôi chỉ có thể lặp từ 2 đến sqrt (n) và tìm tất cả các số chia hết, nhưng điều đó có vẻ không hiệu quả vì chúng ta đã có hệ số chính. Tôi tưởng tượng nó về cơ bản là một phiên bản sửa đổi của một kết hợp/lựa chọn chức năng, nhưng tất cả tôi có thể tìm thấy là phương pháp để đếm số lượng kết hợp, và cách đếm số lượng các yếu tố, không phải để thực sự tạo ra các kết hợp/Logged/các yếu tố.

Answer 1

Hãy tưởng tượng ước nguyên tố là quả bóng trong một cái xô. Ví dụ: nếu ước số nguyên tố của số của bạn là 2, 2, 2, 3 và 7, thì bạn có thể lấy 0, 1, 2 hoặc 3 trường hợp 'bóng 2'. Tương tự, bạn có thể thực hiện 'quả bóng 3' 0 hoặc 1 lần và 'bóng 7' 0 hoặc 1 lần.

Bây giờ, nếu bạn lấy 'quả bóng 2' hai lần và 'bóng 7' một lần, bạn sẽ nhận được số chia 2 * 2 * 7 = 28. Tương tự, nếu bạn không có bóng, bạn nhận số chia 1 và nếu bạn lấy tất cả các quả bóng bạn nhận được ước số 2 * 2 * 2 * 3 * 7 bằng với số của chính nó.

Và cuối cùng, để có được tất cả các kết hợp có thể có của quả bóng bạn có thể lấy từ xô, bạn có thể dễ dàng sử dụng đệ quy.

void findFactors(int[] primeDivisors, int[] multiplicity, int currentDivisor, long currentResult) { 
    if (currentDivisor == primeDivisors.length) { 
     // no more balls 
     System.out.println(currentResult); 
     return; 
    } 
    // how many times will we take current divisor? 
    // we have to try all options 
    for (int i = 0; i <= multiplicity[currentDivisor]; ++i) { 
     findFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult); 
     currentResult *= primeDivisors[currentDivisor]; 
    } 
} 

Bây giờ bạn có thể chạy nó trên trên ví dụ:

findFactors(new int[] {2, 3, 7}, new int[] {3, 1, 1}, 0, 1); 

Answer 2

dimo414, tạo ra các yếu tố thường được coi là một nhiệm vụ rất khó khăn. Trên thực tế, việc bảo vệ hầu hết các tài sản quan trọng của bạn (ví dụ: tiền, thông tin., V.v.), phần còn lại trên nhiệm vụ đơn giản nhưng cực kỳ khó khăn của việc bao thanh toán một số. Xem bài viết này về lược đồ mã hóa RSA http://en.wikipedia.org/wiki/RSA_(cryptosystem). Tôi digress.

Để trả lời câu hỏi của bạn, cách tiếp cận tổ hợp là phương pháp tốt nhất của bạn như được chỉ ra bởi Nikita (btw, kudo về lời giải thích của bạn).

Tôi biết tôi có thể chỉ vòng từ 2 đến sqrt (n) và tìm thấy tất cả số chia hết cho

Nhiều người nhảy đến kết luận này vì khái niệm rất tương tự liên quan đến số nguyên tố tạo ra. Thật không may, điều này là không chính xác, vì bạn sẽ bỏ lỡ một số yếu tố lớn hơn sqrt (n) mà không phải là số nguyên tố (tôi sẽ cho phép bạn chứng minh điều này cho chính mình).

Bây giờ, để xác định số lượng các yếu tố cho bất kỳ số n nào, chúng tôi xem xét đến hệ số chính của n. Nếu n = p ^một, sau đó chúng ta biết rằng n sẽ có (a + 1) yếu tố (1, p, p , ..., p ^một). Đây là chìa khóa để xác định tổng số yếu tố.Nếu n có nhiều thừa số nguyên tố, nói

n = p ^một& chấm giữa; p ^b& middot; & middot; & middot; p _k^r

sau đó sử dụng Rule sản phẩm đếm (http://en.wikipedia.org/wiki/Rule_of_product), chúng ta biết rằng sẽ có

m = (a + 1) & chấm giữa; (b + 1) & middot; & middot; & middot; (r + 1)

yếu tố. Bây giờ, tất cả những gì chúng ta cần làm là tìm mọi sự kết hợp có thể có của các con số được đưa ra cho chúng ta bởi sự yếu tố chính. Dưới đây, là một số mã trong R, hy vọng thể hiện những gì tôi đã giải thích.

Phần đầu tiên của mã của tôi thực hiện kiểm tra tính nguyên thủy đơn giản bởi vì nếu số nguyên tố, thì các yếu tố duy nhất là 1 và chính nó. Tiếp theo, nếu số lượng không phải là số nguyên tố và lớn hơn 1, lần đầu tiên tôi tìm ra nguyên tố của số, nói rằng chúng ta có,

n = p ^một& chấm giữa; p ^b& middot; & middot; & middot; p _k^r

sau đó tôi tìm thấy chỉ số nguyên tố độc đáo có nhãn UniPrimes, như vậy cho ví dụ này, UniPrimes sẽ chứa (p , p , p _k). Sau đó tôi tìm thấy tất cả các quyền hạn của mỗi nguyên tố và thêm nó vào một mảng đã được thử nghiệm MyFactors. Sau khi mảng này được tạo, tôi tìm thấy mọi kết hợp sản phẩm có thể có của các phần tử trong MyFactors. Cuối cùng, tôi thêm 1 vào mảng (vì nó là một yếu tố tầm thường), và sắp xếp nó. Thì đấy! Nó cực kỳ nhanh và hoạt động với số lượng rất lớn với nhiều yếu tố.

Tôi cố gắng làm cho mã có thể dịch càng tốt sang các ngôn ngữ khác (ví dụ: tôi giả định rằng bạn đã tạo một hàm tạo hệ số chính (hoặc sử dụng hàm dựng sẵn) và hàm kiểm tra số nguyên tố.) và tôi không sử dụng các chức năng tích hợp chuyên dụng duy nhất cho R. Hãy cho tôi biết nếu có điều gì đó không rõ ràng. Chúc mừng!

factor2 <- function(MyN) { 

    CheckPrime <- isPrime(MyN) 

    if (CheckPrime == F && !(MyN == 1)) { 
      MyPrimes <- primeFactors(MyN) 
      MyFactors <- vector() 
      MyPowers <- vector() 
      UniPrimes <- unique(MyPrimes) 
        for (i in 1:length(UniPrimes)) { 

          TempSize <- length(which(MyPrimes == UniPrimes[i])) 

          for (j in 1:TempSize) { 
            temp <- UniPrimes[i]^j 
            MyPowers <- c(MyPowers, temp) 
          } 

        } 
      MyFactors <- c(MyFactors, MyPowers) 
      MyTemp <- MyPowers 
      MyTemp2 <- vector() 
      r <- 2 
      while (r <= length(UniPrimes)) { 

        i <- 1L 

        while (i <= length(MyTemp)) { 
          a <- which(MyPrimes > max(primeFactors(MyTemp[i]))) 
            for (j in a) { 
              temp <- MyTemp[i]*MyPowers[j] 
              MyFactors <- c(MyFactors, temp) 
              MyTemp2 <- c(MyTemp2, temp) 
            } 
          i <- i + 1 
        } 
        MyTemp <- MyTemp2 
        MyTemp2 <- vector() 
        r <- r + 1 
      } 
    } else { 
      if (MyN == 1) { 
        MyFactors <- vector() 
      } else { 
        MyFactors <- MyN 
      } 
    } 
    MyFactors <- c(1, MyFactors) 
    sort(MyFactors) 
}