Table of Contents
I wrote the code to check perfect number and semipefrect number in Ruby. Semiperfect number is also called pseudoperfect number.
Definition
- Perfect Number
- A positive integer that is equal to the sum of its proper positive divisors.
- Semiperfect Number
- A natural number n that is equal to the sum of all or some of its proper divisors.
Perfect number is also semiperfect number.
Code
Environment
- Ruby 2.4.0
I created the class called Number. is_perfect? returns whether the number is perfect, is_semiperfect? returns whether the number is semi-perfect.
初期化処理のところで約数を配列に入れてしまっています。 初期化でそれをやるべきかというのは考えるべきことではありますが、今回は目的が特化しているのでこれで。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Number attr_reader :n def initialize(n) @n = n @factors = [1] u = (@n ** 0.5).to_i 2.step(u, 1) do |i| if @n % i == 0 @factors.push(i) s = @n / i if i != s @factors.push(s) end end end @factors.sort! end def is_perfect? return @factors.sum == @n end def is_semiperfect? return check_semiperfect([], 0, @factors.length - 1) end private def check_semiperfect(element_array, sub_total, upper_index) if sub_total == @n return true end if upper_index < 0 return false end if sub_total > @n || sub_total + @factors[0, upper_index + 1].sum < @n return false end if check_semiperfect(element_array + [@factors[upper_index]], sub_total + @factors[upper_index], upper_index - 1) return true end if upper_index > 0 if check_semiperfect(element_array + [@factors[upper_index - 1]], sub_total + @factors[upper_index - 1], upper_index - 2) return true end end return false end end |
The first argument of check_semiperfect? is array whose member constructs subset sum. In this case, it only show whether perfect/semi-perfect or not, so it’s not used, but in outputting the sequence of elements which compose subset, it can be used.
We can use the above code as follows.
|
1 2 3 4 |
for i in 1..100 n = Number.new(i) puts n.n.to_s + " : " + n.is_perfect?.to_s + " / " + n.is_semiperfect?.to_s end |
Its output is the following.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
1 : true / true 2 : false / false 3 : false / false 4 : false / false 5 : false / false 6 : true / true 7 : false / false 8 : false / false 9 : false / false 10 : false / false 11 : false / false 12 : false / true 13 : false / false 14 : false / false 15 : false / false 16 : false / false 17 : false / false 18 : false / true 19 : false / false 20 : false / true 21 : false / false 22 : false / false 23 : false / false 24 : false / true 25 : false / false 26 : false / false 27 : false / false 28 : true / true 29 : false / false 30 : false / true 31 : false / false 32 : false / false 33 : false / false 34 : false / false 35 : false / false 36 : false / true 37 : false / false 38 : false / false 39 : false / false 40 : false / true 41 : false / false 42 : false / true 43 : false / false 44 : false / false 45 : false / false 46 : false / false 47 : false / false 48 : false / true 49 : false / false 50 : false / false 51 : false / false 52 : false / false 53 : false / false 54 : false / true 55 : false / false 56 : false / true 57 : false / false 58 : false / false 59 : false / false 60 : false / true 61 : false / false 62 : false / false 63 : false / false 64 : false / false 65 : false / false 66 : false / true 67 : false / false 68 : false / false 69 : false / false 70 : false / false 71 : false / false 72 : false / true 73 : false / false 74 : false / false 75 : false / false 76 : false / false 77 : false / false 78 : false / true 79 : false / false 80 : false / true 81 : false / false 82 : false / false 83 : false / false 84 : false / true 85 : false / false 86 : false / false 87 : false / false 88 : false / true 89 : false / false 90 : false / true 91 : false / false 92 : false / false 93 : false / false 94 : false / false 95 : false / false 96 : false / true 97 : false / false 98 : false / false 99 : false / false 100 : false / true |
Supplementary
Semi-perfect number detection is called subset sum problem. (Reference: Programming Contest Challenge Book)
