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

Ответ 1

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

Теперь, если вы дважды возьмете "мяч 2" и "мяч 7" один раз, вы получите дивизор 2 * 2 * 7 = 28. Аналогичным образом, если вы не принимаете мячей, вы получаете дивизор 1, и если вы возьмете все мячи, вы get divisor 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);

Ответ 2

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

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

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

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

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

n = p ₁ ^a & middot; p ₂ ^b & middot; & middot; & middot; p _k ^r

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

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

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

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

n = p ₁ ^a & middot; p ₂ ^b & middot; & middot; & middot; p _k ^r

Затем я нахожу только уникальные простые числа UniPrimes, поэтому для этого примера UniPrimes будет содержать (p ₁, p ₂, p _k). Затем я нахожу все полномочия каждого шага и добавляю его в массив, содержащий 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)
}