A circular sieve of eratosthenes to visualize prime numbers (sievesofchaos.com)

Someone should tell this guy about google docs..

I had a kind of program which would find primes higher than the Sieve of Eratosthenes (typically this only goes up to 4 billion because of 1 bit per integer), called a 'Leapfrog' sieve, but someone said it wasn't very interesting, and I can't tell if it's been done before.

After reading this awesome article I decided to write my own version of exactly what I saw in his pictures:

timing_array = Hash.new

for q in 0..6

  max_n = 10**q

  prime_array = Array.new

  for z in 0..max_n

    prime_array[z] = 0

  end

  for i in 2..max_n

    a = max_n / i

    for j in 1..a

      prime_array[j*i] += 1 unless j*i > max_n

    end

  end

  puts "prime numbers to #{max_n}"

  prime_array.each_with_index {|num,v| puts "#{v}" unless num > 1}

  timing_array[max_n] = Time.now

end

puts "and the resultz"

puts timing_array

1000000 Sun Dec 13 20:33:05 -0500 2009

100000 Sun Dec 13 20:32:34 -0500 2009

10000 Sun Dec 13 20:32:31 -0500 2009

1000 Sun Dec 13 20:32:31 -0500 2009

100 Sun Dec 13 20:32:31 -0500 2009