Factorisation Sieve

sieve.cr

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

sieve_64.cr

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