Generowanie wszystkich czynników liczby z uwagi na jej główną czynnikowość

Question

Jeśli masz już faktyczną faktoryzację liczby, jaki jest najprostszy sposób na uzyskanie zestawu wszystkich czynników tej liczby? Wiem, że mogłem po prostu zapętlić od 2 do sqrt (n) i znaleźć wszystkie podzielne liczby, ale to wydaje się nieefektywne, ponieważ mamy już główną czynnikowość.

Wyobrażam sobie, że jest to właściwie zmodyfikowana wersja funkcji kombinacji/wyboru, ale wszystko, co mogę znaleźć, to metody liczenia liczby kombinacji i sposoby liczenia liczby czynników, a nie faktyczne generowanie kombinacji/czynniki.

Answer 1

Wyobraź sobie, że główne dzielniki to kule w wiadrze. Jeśli na przykład główny dzielnik twojej liczby to 2, 2, 2, 3 i 7, wtedy możesz wziąć 0, 1, 2 lub 3 wystąpienia "kulki 2". Podobnie, możesz wziąć "piłkę 3" 0 lub 1 raz i "piłkę 7" 0 lub 1 raz.

Teraz, jeśli raz weźmiesz "piłkę 2" i "piłkę 7", otrzymasz dzielnik 2 * 2 * 7 = 28. Podobnie, jeśli nie weźmiesz kulek, otrzymasz dzielnik 1 i jeśli weźmiesz wszystkie kulki otrzymujesz dzielnik 2 * 2 * 2 * 3 * 7, który jest równy samej liczbie.

I na koniec, aby uzyskać wszystkie możliwe kombinacje kulek, które możesz wziąć z wiadra, możesz z łatwością użyć rekursji.

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]; 
    } 
} 

Teraz można uruchomić go na powyższy przykład:

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

Answer 2

dimo414, generując czynników jest powszechnie uważany za bardzo trudnym zadaniem. W rzeczywistości ochrona większości waszych ważnych zasobów (tj. Pieniędzy, informacji itp.) Spoczywa na prostym, ale niezwykle trudnym zadaniu polegającym na faktorowaniu liczby. Zobacz ten artykuł na schemacie szyfrowania RSA http://en.wikipedia.org/wiki/RSA_(cryptosystem). Dygresję.

Aby odpowiedzieć na twoje pytanie, podejście kombinatoryczne jest twoją najlepszą metodą wskazaną przez Nikitę (btw, kudos na twoje wyjaśnienie).

wiem, może po prostu pętla od 2 do sqrt (n) i znaleźć wszystkie liczby podzielne

Wiele osób Skocz do tego wniosku ze względu na bardzo podobnym pojęcia związane z generowaniem liczb pierwszych. Niestety, jest to niepoprawne, ponieważ stracisz kilka czynników większych niż sqrt (n), które nie są liczbami pierwszymi (pozwolę ci to udowodnić sobie).

Teraz, aby określić liczbę czynników dla dowolnej liczby n, patrzymy na główną czynnikowość n. Jeśli n = p , to wiemy, że n będzie miał (a + 1 ) czynniki (1, p, p , ..., p ). Jest to klucz do określenia całkowitej liczby czynników.Jeśli n prime miał wiele czynników, np

n = p i Middot; p ^b& middot; & middot; & middot; p _k^r

następnie stosując regułę produktu liczenia (http://en.wikipedia.org/wiki/Rule_of_product), wiemy, że nie będzie

m = (a + 1) & middot; (b + 1) & middot; & middot; & middot; (r + 1)

czynników. Teraz wszystko, co musimy zrobić, to znaleźć każdą możliwą kombinację liczb podanych nam przez główną faktoryzację. Poniżej znajduje się kod w R, który, mam nadzieję, demonstruje to, co wyjaśniłem.

Pierwsza część mojego kodu wykonuje prostą kontrolę pierwszości, ponieważ jeśli liczba jest liczbą pierwszą, jedynymi czynnikami są 1 i sam. Następnie, jeśli liczba jest prime i nie większa niż 1, po raz pierwszy znaleźć czynniki pierwsze liczby, że mamy,

n = p & middot; p ^b& middot; & middot; & middot; P _K^R

Następnie znaleźć tylko unikalne bodźce znakowanych UniPrimes, więc w tym przykładzie, UniPrimes zawierałby (P , s , s _K). Następnie znajduję wszystkie moce każdego z primerów i dodam je do tablicy Liniowej MyFactors. Po wykonaniu tej tablicy, znajduję każdą możliwą kombinację produktów elementów w MyFactors. Na koniec dodaję 1 do tablicy (ponieważ jest to czynnik trywialny) i sortuję ją. Voila! Jest niezwykle szybki i działa na bardzo duże liczby z wieloma czynnikami.

Próbowałem uczynić kod możliwym do przetłumaczenia jak to tylko możliwe dla innych języków (tj. Zakładam, że już zbudowałeś funkcję, która generuje rozkład czynnikowy (lub używając wbudowanej funkcji) i funkcję testu liczby pierwszej). i nie korzystałem z wyspecjalizowanych wbudowanych funkcji unikalnych dla R. Daj mi znać, jeśli coś nie jest jasne. Twoje zdrowie!

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) 
}