Создание всех факторов числа с учетом его простой факторизации

Question

Если у вас уже есть факторизация числа, то какой самый простой способ получить набор всех факторов этого числа? Я знаю, что я мог бы просто перебирать от 2 до sqrt (n) и находить все делимые числа, но это кажется неэффективным, поскольку у нас уже есть основная факторизация.

Я предполагаю, что это в основном модифицированная версия комбинации/функции выбора, но все, что я могу найти, это методы для подсчета количества комбинаций и способы подсчета количества факторов, а не для генерации комбинаций/факторы.

Answer 1

Представьте, что простые делители - это шары в ведре. Если, например, простые делители вашего номера - 2, 2, 2, 3 и 7, то вы можете взять 0, 1, 2 или 3 экземпляра «шара 2». Аналогично, вы можете взять «мяч 3» 0 или 1 раз, а «мяч 7» - 0 или 1 раз.

Теперь, если вы берете «мяч 2» дважды и «мяч 7» один раз, вы получаете делитель 2 * 2 * 7 = 28. Аналогичным образом, если вы не делаете шаров, вы получаете дивизор 1, и если вы берете все шары вы получаете делитель 2 * 2 * 2 * 3 * 7, который равен самому числу.

И, наконец, чтобы получить все возможные комбинации шаров, которые вы можете взять из ведра, вы можете легко использовать рекурсию.

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

Теперь вы можете запустить его на приведенном выше примере:

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

Answer 2

dimo414, порождая факторы, как правило, считается очень трудной задачей. На самом деле защита большинства ваших важных активов (т. Е. Денег, информации и т. Д.) Лежит на простой, но чрезвычайно сложной задаче факторинга числа. См. Эту статью по схеме шифрования RSA http://en.wikipedia.org/wiki/RSA_(cryptosystem). Я отвлекся.

Чтобы ответить на ваш вопрос, комбинаторный подход - это ваш лучший метод, как указал Никита (кстати, на ваше объяснение).

Я знаю, что я мог бы просто цикл от 2 до SQRT (п) и найти все кратные номер

Многих людей прыгают к такому выводу из-за очень аналогичную концепцию, связанную с формированием простых чисел. К сожалению, это неверно, поскольку вы пропустите несколько факторов, превышающих sqrt (n), которые не являются простыми числами (я позволю вам доказать это самому себе).

Теперь, чтобы определить количество факторов для любого заданного числа n, рассмотрим простую факторизацию n. Если п = р , то мы знаем, что п будет (а + 1) факторы (1, р, р , ..., р ). Это ключ к определению общего числа факторов.Если п было несколько простых множителей, скажем

п = р & Мидот; p ^b& middot; & middot; & middot; р _к^г

затем с помощью правила продукта подсчета (http://en.wikipedia.org/wiki/Rule_of_product), мы знаем, что будет

м = (а + 1) & Мидот; (b + 1) & middot; & middot; & middot; (r + 1)

Факторы. Теперь все, что нам нужно сделать, - найти любую возможную комбинацию чисел, предоставленных нам простой факторизацией. Ниже приведен некоторый код в R, который, надеюсь, демонстрирует то, что я объяснил.

Первая часть моего кода выполняет простую проверку правильности, потому что, если число является простым, единственными факторами являются 1 и сам. Далее, если число не является простым и больше 1, я сначала найти разложение на простые множители числа, скажем, у нас есть,

п = р & Мидот; p ^b& middot; & middot; & middot; р _к^г

Я тогда найти только уникальные простые числа помечены UniPrimes, так, для этого примера, UniPrimes будет содержать (р , р , р _к). Затем я нахожу все полномочия каждого штриха и добавляю его в массив, выделенный MyFactors. После того, как этот массив создан, я нахожу все возможные комбинации продуктов в MyFactors. Наконец, я добавляю 1 к массиву (как тривиальный фактор) и сортирую его. Вуаля! Это очень быстро и работает для очень больших чисел со многими факторами.

Я попытался сделать код максимально переводимым на другие языки (т. Е. Я предположил, что вы уже создали функцию, которая генерирует простую факторизацию (или используя встроенную функцию) и функцию проверки простого числа.) и я не использовал специальные встроенные функции, уникальные для R. Дайте мне знать, если что-то неясно. Ура!

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