fork download
copy 
  1. def sieve(upper)
  2.   i = 0
  3.   list = (2..upper).to_a
  4.  
  5.   (2..Math.sqrt(upper)).each do |mult|
  6.   	if list[i]         # list[i]==mult
  7.       init = mult + i  # list[init]==mult*2
  8.       (init..upper-1).step(mult) do |index|
  9.         list[index] = nil  # 0-based index: list[0]==2
  10.       end
  11.     end
  12.     i += 1
  13.   end
  14.   list.compact
  15. end
  16.  
  17. puts sieve(2000000).length
Success #stdin #stdout 1.45s 20080KB
comments (?)
stdin
copy 
100k: 9592:  0.16s 7.9MB            ## with if list[i] ## 
200k: 17984: 0.35s 8.6MB               0.15s
400k: 33860: 0.75s 9.9MB   n^1.20      0.29s     n^1.04
1mln: 78498: 2.0s 13.1MB   n^1.16      0.71s     n^1.06
2mln: 148933        20MB               1.45s     n^1.11

http://stackoverflow.com/questions/18994059/
 improving-efficiency-of-my-sieve-of-eratosthenes-in-ruby
stdout
copy 
148933
https://ideone.com/GXkFhK
http://stackoverflow.com/questions/18994059/improving-efficiency-of-my-sieve-of-eratosthenes-in-ruby
language:
Ruby (ruby 2.5.5)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!