-
Notifications
You must be signed in to change notification settings - Fork 0
/
prime_factors.rb
71 lines (57 loc) · 1.38 KB
/
prime_factors.rb
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
# frozen_string_literal: false
# https://exercism.org/tracks/ruby/exercises/prime-factors
# Prime Factors exercise
module PrimeFactors
def self.of(number)
factors = []
case number
when 0 | 1
return factors
when 2
factors.push(2)
return factors
end
if number > 5
primes = sieve(MAX_PRIMES)
primes.select! { |prime| prime < (number / 2) + 1 }
else
primes = sieve(5)
end
factors = []
factor = primes.pop
while number > 1
while number.modulo(factor).zero? && number > 1
number /= factor
factors.push(factor)
end
factor = primes.pop
end
factors.sort
end
MAX_PRIMES = 1_000_000
def self.sieve(limit)
result = []
return result if limit < 2
result.push(2)
return result if limit == 2
@numbers = Array.new(limit + 1, true)
@numbers.each_index { |number| @numbers[number] = false if number.modulo(2).zero? }
@numbers[0] = @numbers[1] = false
@numbers[2] = true
(3..limit).step(2).each_entry do |number|
is_prime = @numbers[number]
next unless is_prime
jdex = 3
while (mul = number * jdex) <= limit
index = mul
@numbers[index] = false
jdex += 1
end
end
result = []
@numbers.each_with_index do |is_prime, index|
result.push(index) if is_prime
end
result
end
end