Done puzzle 43
[project-euler.git] / divisors.rb
1 load 'primes.rb'
2
3
4 class Integer
5 # Returns a Hash of prime factors of self.
6 # Each key is a prime factor of self, and factors[i] is the power of that prime factor
7 # For example 45.prime_factors # => {3 => 2, 5 => 1}
8 # or, 45 = 3 ** 2 * 5 ** 1
9 def prime_factors
10 primes = Primes.instance
11 n = self
12 factors = Hash.new(0)
13 i = 0
14 while n > 1
15 if n % primes[i] == 0
16 factors[primes[i]] += 1
17 n = n.div primes[i]
18 else
19 i += 1
20 end
21 end
22 factors
23 end
24
25 def number_of_divisors
26 factors = prime_factors
27 factors.keys.reduce(1) {|a, factor| a *= factors[factor] + 1}
28 end
29
30 def sum_of_divisors
31 factors = prime_factors
32 factors.keys.map {|f|
33 (0..factors[f]).map {|a| f ** a}.reduce(:+)
34 }.reduce(:*)
35 end
36
37 def sum_of_proper_divisors
38 sum_of_divisors - self
39 end
40
41 def perfect?
42 sum_of_proper_divisors == self
43 end
44
45 def abundant?
46 sum_of_proper_divisors > self
47 end
48
49 def deficient?
50 sum_of_proper_divisors < self
51 end
52
53 end