Sieve of Eratosthene

prime-speed-comparison.cr

require "time"
require "big_int"

def primesArray(n : UInt64)
  primedex = [false, false] of Bool
  primedex += [true] * (n - 1)

  (2_u64..n).each do |i|
    (2_u64..n).each do |j|
      begin
        primedex[i * j] = false
      rescue
        break
      end
    end
  end

  primes = Array(UInt64).new
  summation : UInt64 = 0_u64
  (0_u64..(primedex.size).to_u64 - 1_u64).each do |i|
    if primedex[i]
      primes << i
      summation += i
    end
  end

  return summation
end

def primesHash(n : UInt64)
  primedex = Hash(String, Bool).new

  (2_u64..n).each do |i|
    ({"#{i}" => true}).each do |number, state|
      primedex[number] = state
    end
  end

  (2_u64..n).each do |i|
    (2_u64..n).each do |j|
      primedex["#{i * j}"] = false
    end
  end

  primes = Array(UInt64).new
  summation : UInt64 = 0_u64
  primedex.each do |prime, state|
    if primedex[prime]
      primes << prime.to_u64
      summation += prime.to_u64
    end
  end

  return summation
end

def primesBigInt
  n : BigInt = BigInt.new ARGV[0]
  primedex = [false, false] of Bool
  primedex += [true] * (n - 1)

  (BigInt.new(2)..n).each do |i|
    (BigInt.new(2)..n).each do |j|
      begin
        primedex[i * j] = false
      rescue
        break
      end
    end
  end

  primes = Array(BigInt).new
  summation : BigInt = BigInt.new(0)
  (BigInt.new(0)..BigInt.new(primedex.size) - BigInt.new(1)).each do |i|
    if primedex[i]
      primes << i
      summation += i
    end
  end

  return summation
  #puts primes
  #puts summation
end

n : UInt64 = ARGV[0].to_u64

begin
  go = Time.new
  primesHash(n)
  finish = Time.new

  puts "Hash UInt64 time: #{finish - go}"
end

begin
  go = Time.new
  primesArray(n)
  finish = Time.new

  puts "Array UInt64 time: #{finish - go}"
end

begin
  go = Time.new
  primesBigInt
  finish = Time.new

  puts "Array BigInt time: #{finish - go}"
end

primes-array

primes-array.cr

primes-bigint

primes-bigint.cr

primes-hash.cr

Use UInt64 for larger numbers when summing numbers that exceed the default Int32 limit (Int32::MAX which is 2,147,483,647)