Todos los factores de un número dado

Por ejemplo, tengo 4800 y me gustaría ver todos los factores de este número.

# num = the number you want factors of def factors_of(num) (1..num).collect { |n| [n, num/n] if ((num/n) * n) == num}.compact end 

divisors_of (4800) => [[1, 4800], [2, 2400], [3, 1600], [4, 1200], [5, 960], [6, 800], [8, 600], [ 10, 480], [12, 400], [15, 320], [16, 300], [20, 240], [24, 200], [25, 192], [30, 160], [32, 150], [40, 120], [48, 100], [50, 96], [60, 80], [64, 75], [75, 64], [80, 60], [96, 50] , [100, 48], [120, 40], [150, 32], [160, 30], [192, 25], [200, 24], [240, 20], [300, 16], [ 320, 15], [400, 12], [480, 10], [600, 8], [800, 6], [960, 5], [1200, 4], [1600, 3], [2400, 2], [4800, 1]]

¿Cómo harías esto en ruby ​​o en cualquier otro idioma?

En Ruby, la biblioteca prime te da la factorización:

 require 'prime' 4800.prime_division #=> [[2, 6], [3, 1], [5, 2]] 

Para obtener esa lista suya, tome el producto cartesiano de los posibles poderes:

 require 'prime' def factors_of(number) primes, powers = number.prime_division.transpose exponents = powers.map{|i| (0..i).to_a} divisors = exponents.shift.product(*exponents).map do |powers| primes.zip(powers).map{|prime, power| prime ** power}.inject(:*) end divisors.sort.map{|div| [div, number / div]} end p factors_of(4800) # => [[1, 4800], [2, 2400], ..., [4800, 1]] 

Nota : en Ruby 1.8.7, debe require 'mathn' lugar de require 'prime' . En Ruby 1.8.6, require 'backports/1.8.7/enumerable/inject' o modifique la inject anterior …

  def divisors_of(num) (1..num).select { |n|num % n == 0} end 

Creo que esta solución es más agradable, especialmente porque no realiza tantos bucles, no requiere la biblioteca Prime y lo más importante se ejecuta hasta Math.sqrt(n) . Aquí está el código:

 class Integer def factors 1.upto(Math.sqrt(self)).select {|i| (self % i).zero?}.inject([]) do |f, i| f << i f << self / i unless i == self / i f end.sort end # Usage 4800.factors 

Si quieres emparejarlos , como en tu ejemplo, puedes usar el siguiente fragmento de código (que se empareja primero con el último y en caso de que exista un número impar de factores, y luego el del medio es la raíz cuadrada):

 class Integer def paird_up_factors a = self.factors l = a.length if l % 2 == 0 a[0, l / 2].zip(a[- l / 2, l / 2].reverse) else a[0, l / 2].zip(a[- l / 2 + 1, l / 2].reverse) + [a[l / 2], a[l / 2]] end end end # Usage 4800.paird_up_factors 

Python no viene con baterías para hacer la factorización, pero comenzando con

 >>> p=[[2, 6], [3, 1], [5, 2]] >>> from itertools import product >>> print sorted(reduce(lambda x,y:x*y,j) for j in product(*[[x**i for i in range(0,y+1)] for x,y in p])) [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 25, 30, 32, 40, 48, 50, 60, 64, 75, 80, 96, 100, 120, 150, 160, 192, 200, 240, 300, 320, 400, 480, 600, 800, 960, 1200, 1600, 2400, 4800] 

También podría hacer un algoritmo O (sqrt (n)) que no necesita factorización prima. Si ve en su lista, por cada par [a, b] en su lista, de modo que a <= b , también aparece el par [b, a]. Esto le permite iterar solo hasta sqrt(n) , porque a <= sqrt(n) .

Para demostrar que por cada par [a, b] tal que a <= b contiene que a <= sqrt(n) puede usar una prueba por contradicción. Supongamos que a > sqrt(n) . Si a > sqrt(n) , entonces b > sqrt(n) también, porque b >= a . Por lo tanto:

a * b > sqrt(n) * sqrt(n) = n

lo que contradice el hecho de que a * b == n . Entonces, el siguiente algoritmo generará todos los pares (el siguiente código está en C ++):

 void GeneratePairs(int n) { for (int a = 1; a <= n / a; ++a) if (n % a == 0) { const int b = n / a; printf("[%d, %d] ", a, b); if (a != b) // be careful with square numbers printf("[%d, %d] ", b, a); } printf("\n"); } 

El único problema es que este código no genera los pares en orden. Una solución es almacenarlos en un vector, clasificarlos y luego imprimirlos, o hacer dos pases, uno hacia delante y otro hacia atrás:

 void GeneratePairsTwoPasses(int n) { const int sq = static_cast(sqrt(n)); for (int a = 1; a <= sq; ++a) if (n % a == 0) printf("[%d, %d] ", a, n / a); for (int a = sq - 1; a >= 1; --a) if (n % a == 0) printf("[%d, %d] ", n / a, a); printf("\n"); } 

La pregunta realmente no pregunta sobre los resultados de las divisiones, y puede llamar al producto convirtiendo un conjunto de matrices en parámetros de matriz.

 n= 4800 pd= n.prime_division.map{ |pd| (0..pd[1]).map{ |i| pd[0]** i } } p (pd.length== 1 ? pd[0] : pd[0].product(*pd.drop(1)).map{ |a, b| a* b })[0..-2].uniq 

Utilizando la fuerza bruta, puede omitir la mitad de los números, ya que para n , los números mayores que n / 2 obviamente no pueden ser divisores, por lo que para acelerar el cálculo, puede ir de n a n / 2 y luego simplemente agregar n . También agregué .uniq para n = 1 caso:

 ((1..(n / 2.0).ceil).select { |i| n % i == 0 } + [n]).uniq 

En Haskell, cualquiera de estos dos:

 import Control.Monad factorsOf :: (Integral a) => a -> [(a,a)] factorsOf n = [(x,n `div` x) | x <- [1..n], n `mod` x == 0] factorsOf_ :: (Integral a) => a -> [(a,a)] factorsOf_ n = do x <- [1..n] guard (n `mod` x == 0) return (x, n `div` x) 

En F #:

 let factors n = [for i in 1..n do if n%i=0 then yield i] 

Otras implementaciones de idiomas se pueden encontrar aquí en el Código Rosetta .

Este es el código de Ruby.

 require 'prime' def divisors(n) arr = Prime.prime_division(n).map { |v,exp| (0..exp).map { |i| v**i } } arr.first.product(*arr[1..-1]).map { |a| a.reduce(:*) }.map { |m| [m,n/m] } end 

Por ejemplo,

 divisors 24 #=> [[1, 24], [3, 8], [2, 12], [6, 4], [4, 6], [12, 2], [8, 3], [24, 1]] divisors 9 #=> [[1, 9], [3, 3], [9, 1]] divisors 450 #=> [[1, 450], [5, 90], [25, 18], [3, 150], [15, 30], [75, 6], [9, 50], # [45, 10], [225, 2], [2, 225], [10, 45], [50, 9], [6, 75], [30, 15], # [150, 3], [18, 25], [90, 5], [450, 1]] 

Para n = 24, los pasos son los siguientes:

 a = Prime.prime_division(n) #=> [[2, 3], [3, 1]] arr = a.map { |v,exp| (0..exp).map { |i| v**i } } #=> [[1, 2, 4, 8], [1, 3]] b = arr.shift #=> [1, 2, 4, 8] arr #=> [[1, 3]] c = b.product(*arr) #=> [[1, 1], [1, 3], [2, 1], [2, 3], [4, 1], [4, 3], [8, 1], [8, 3]] d = c.map { |a| a.reduce(:*) } #=> [1, 3, 2, 6, 4, 12, 8, 24] 

Finalmente,

 d.map { |m| [m,n/m] } 

devuelve la matriz dada arriba.

 def divisors(n) divisors = [] # Initialize an empty array where we store our divisors for i in 1..n divisors.push([i,ni]) if n % i == 0 # Only pushes if i is a divisor of n end divisors # returns our array end