Все факторы данного числа
Например, я имею 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]]
Как Вы сделали бы это в рубине или каком-либо языке?
5 ответов
В 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 вы должны требовать 'mathn' вместо требовать 'prime' . В Ruby 1.8.6 требует 'backports / 1.8.7 / enumerable / inject' или модифицирует inject выше ...
Вы также можете использовать алгоритм 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");
}
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]
В Haskell, любое из этих двух:
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)
В F #:
let factors n = [for i in 1..n do if n%i=0 then yield i]
Реализации других языков можно найти здесь, в Rosetta Code .