Skip to content

Instantly share code, notes, and snippets.

@JoshCheek
Created November 26, 2018 01:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JoshCheek/b5326b54939b920d584e59ee6d054d2e to your computer and use it in GitHub Desktop.
Save JoshCheek/b5326b54939b920d584e59ee6d054d2e to your computer and use it in GitHub Desktop.
Compiler does not like this (but ic you change the size of the static array, it's cool with it)
# $ crystal build 357.cr --release
struct SeiveSlot
property number, divisors
def initialize(@number : Int32)
@divisors = [] of Int32
end
def prime?
@divisors.size == 2 && @divisors[0] == 1 && @divisors[1] == @number
end
def <<(divisor : Int32) : SeiveSlot
@divisors.push divisor
self
end
def prime_generator?(seive)
@divisors.all? do |divisor|
generated = divisor + @number/divisor
seive[generated-1].prime?
end
end
end
seive = StaticArray(SeiveSlot, 100_000_000).new { |i| SeiveSlot.new i+1 }
puts "allocated"
seive.each do |slot|
divisor = slot.number
p "seive: #{divisor}" if divisor % 100_000 == 0
multiplier = 1
loop do
multiple = divisor*multiplier
break if seive.size < multiple
seive[multiple-1] << divisor
multiplier += 1
end
end
seive.each do |slot|
next if seive.size <= slot.number
p slot.number if slot.prime_generator? seive
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment