Все факторы данного числа

Question

Например, у меня 4800, и я хотел бы увидеть все факторы этого числа.

 # 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]]

Как бы вы сделали это на рубине или на любом другом языке?

Answer 1

В Ruby библиотека prime дает вам факторизацию:

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

Чтобы получить этот список, вы берете декартово произведение возможных степеней:

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

Примечание : в Ruby 1.8.7 вы должны require 'mathn' вместо require 'prime'. В Ruby 1.8.6, require 'backports/1.8.7/enumerable/inject' или измените inject выше ...

Answer 2

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

Answer 3

Я думаю, это решение лучше, особенно потому, что оно не выполняет так много циклов, не требует библиотеки Prime и, самое главное, оно работает до Math.sqrt(n).Вот код:

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

Если вы хотите объединить их в пару , как и в вашем примере, вы можете использовать следующий фрагмент кода (который соединяется сначала с последним и вЕсли существует нечетное количество факторов, то средний является квадратным корнем):

class Integer
  def paired_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.paired_up_factors

Answer 4

Вы также можете сделать алгоритм O (sqrt (n)), который не требует простой факторизации.Если вы видите в своем списке, для каждой пары [a, b] в вашем списке, что a <= b, также появляется пара [b, a].Это позволяет вам выполнять итерации только до sqrt(n), потому что a <= sqrt(n).

Чтобы доказать, что для каждой пары [a, b] такой, что a <= b содержит, что a <= sqrt(n) вы можете использоватьпротиворечием.Давайте предположим, что a > sqrt(n).Если a > sqrt(n), то b > sqrt(n) тоже, потому что b >= a.Следовательно:

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

, что противоречит тому факту, что a * b == n.Таким образом, следующий алгоритм будет генерировать все пары (следующий код на 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");
}

Единственная проблема состоит в том, что этот код не генерирует пары по порядку.Одно из решений состоит в том, чтобы сохранить их в векторе, отсортировать их и затем распечатать, или сделать два прохода, один вперед и один назад:

void GeneratePairsTwoPasses(int n) {
  const int sq = static_cast<int>(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");
}

Answer 5

Используя грубую силу, вы можете пропустить половину чисел, поскольку для n числа, большие n / 2, очевидно, не могут быть делителями, поэтому для ускорения вычислений вы можете перейти от n к n / 2 а затем просто добавьте n сам. Я также добавил .uniq для n = 1 дела:

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

Answer 6

Вопрос на самом деле не задает результаты делений, и вы можете вызвать product, преобразовав массив массивов в параметры массива.

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

Answer 7

Python не поставляется с батареями для факторизации, но начинается с

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

Answer 8

Это код 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

Например,

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

Для n = 24, шаги следующие:

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] 

Наконец,

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

возвращает указанный выше массив.

Answer 9

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

Answer 10

В F #:

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

Другие языковые реализации можно найти здесь в Rosetta Code .