Skip to content

Instantly share code, notes, and snippets.

@obelisk68
Last active Apr 30, 2018
Embed
What would you like to do?
省メモリで「エラトステネスの篩」同等の結果を得るコード
def prime_table(n)
return [] if n < 2
return [2] if n == 2
table = [2, 3]
i, step = 5, 2
while i <= n
guard = Math.sqrt(i).to_i
table.each do |prime|
break if (i % prime).zero?
if prime > guard
table << i
break
end
end
i += step
step = 6 - step
end
table
end
prime_table(1000_0000)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment