Генерация всех факторов числа с учетом его первичной факторизации - PullRequest
Новая
       47

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

21 голосов
/ 05 сентября 2010

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

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

Ответы [ 2 ]

29 голосов
/ 05 сентября 2010

Представьте, что простые делители - это шарики в ведре.Если, например, простые делители вашего числа равны 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);
5 голосов
/ 29 января 2015

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 2)., ..., p a ).Это ключ к определению общего количества факторов.Если n имеет несколько простых множителей, скажем,

n = p 1 a · p 2 b ··· p k r

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

м = ( a + 1 ) · ( b + 1 ) ··· ( r + 1 )

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

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

n = p 1 a · p 2 b ··· pk r

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