Created
November 26, 2018 01:54
-
-
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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# $ 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