I had a bad experience with the Sieve of Eratosthenes during a college test, I became traumatized by it and tried to avoid it. During this holiday break I decided to face my fears (lol) and successfully implemented it ruby (not very idiomatic but ruby still)

My favorite parts of this algorithm were:

  • The fact that I don’t have to iterate the whole sieve! I can do it just for _sqrt(n) _since the factors of any number are always composed by two numbers and one of them is always lower than the sqrt of any given number n.
  • The usage of ruby’s inline _if _statements

    def populate_array(n)
      arr = Array.new(n, true)
      arr[0] = false
      arr[1] = false
      arr
    end
    
    def print_array(a)
      count = 0
      while count < a.length
        puts "#{count} is prime" if a[count]
        count += 1
      end
    end
    
    def mark_factors(a, count)
      mult = 2
      while count * mult <= a.length
        a[count * mult] = false
        mult += 1
      end
      a
    end
    
    def sieve(a)
      count = 2
      while count <= Math.sqrt(a.length)
        a = mark_factors(a, count) if a[count]
        count += 1
      end
    end
    
    def main
      puts 'Give me the limit for your primes'
      n = Integer(gets.chomp)
      a = populate_array(n + 1)
      sieve(a)
      print_array(a)
    end
    
    main
    

Gist link