Skip to content

Instantly share code, notes, and snippets.

@Daniel-Worrall
Last active March 22, 2022 22:53
Show Gist options
  • Save Daniel-Worrall/def8d2322e989f74bbd4e82a201a57f4 to your computer and use it in GitHub Desktop.
Save Daniel-Worrall/def8d2322e989f74bbd4e82a201a57f4 to your computer and use it in GitHub Desktop.
Factorisation Sieve
module Sieve
protected class_getter sieve = Hash(Int32, Int32).new { |h, k| k }
@@calculated = 1
class Factors
include Iterator(Int32)
def initialize(@n : Int32)
end
def next
if @n == 1
stop
else
factor = Sieve.sieve[@n]
@n //= factor
factor
end
end
end
def self.each_factor(n)
process_sieve(@@calculated, n) if @@calculated < n
Factors.new(n)
end
private def self.process_sieve(from : Int32, to : Int32)
((from / 2).ceil.to_i * 2).step(to: to, by: 2).each { |i| @@sieve[i] = 2 }
3.step(to: Math.sqrt(to).ceil.to_i).each do |i|
if @@sieve[i] == i
(Math.max(i, (from / i).ceil.to_i) * i).step(to: to, by: i).each do |j|
@@sieve[j] = i if @@sieve[j] == j
end
end
end
@@calculated = to
end
end
module Sieve
protected class_getter sieve = Hash(Int64, Int64).new { |h, k| k }
@@calculated = 1_i64
def self.factors(n)
process_sieve(@@calculated, n) if @@calculated < n
a = Array(Int64).new
while n != 1
a << (factor = Sieve.sieve[n])
n = (n / factor).floor.to_i64
end
a
end
private def self.process_sieve(from : Int64, to : Int64)
((from / 2).ceil.to_i64 * 2).step(to: to, by: 2).each { |i| @@sieve[i] = 2_i64 }
3_i64.step(to: Math.sqrt(to).ceil.to_i64).each do |i|
if @@sieve[i] == i
(Math.max(i, (from / i).ceil.to_i64) * i).step(to: to, by: i).each do |j|
@@sieve[j] = i if @@sieve[j] == j
end
end
end
@@calculated = to
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment