Skip to content

Instantly share code, notes, and snippets.

@dekokun
Created December 25, 2011 05:43
Show Gist options
  • Save dekokun/1518774 to your computer and use it in GitHub Desktop.
Save dekokun/1518774 to your computer and use it in GitHub Desktop.
愚直なエラトステネスのふるい(動きがわかるよ)
ns = Array.new(99){|i| i+2}
result = Array.new
while ns.length != 0
prime = ns.shift
ns.delete_if{|x| x % prime == 0}
result.push prime
p ns
p result
puts
end
@dekokun
Copy link
Author

dekokun commented Dec 25, 2011

エラトステネスの篩です。

@dekokun
Copy link
Author

dekokun commented Dec 25, 2011

本当は、すべての数について走査する必要はない。高々100の平方根までで問題ない

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment