class Primegen::Generator
Attributes
n[R]
Public Class Methods
new(n)
click to toggle source
# File lib/primegen/generator.rb, line 6 def initialize(n) @n = n end
Public Instance Methods
run()
click to toggle source
Adding 1 to sieve structure to use it in the creation of multiplication table later. Adding 2 - the only even prime number to sieve structure. Sieving only odd numbers to improve complexity. Stepping only till sqrt of n since if its not a prime it would be already marked by a multiple of a number less than the sqrt of n.
# File lib/primegen/generator.rb, line 15 def run sieve_map = {1 => 1, 2 => 2} sieve = (3..n).step(2).inject(sieve_map) {|k,v| k[v] = v; k} (3..Math.sqrt(n)).each do |i| unless sieve[i].nil? sieve[i].step(n, sieve[i]) do |j| sieve.delete(j) unless j == sieve[i] end end end sieve.keys end