Class: Primegen::Generator

Inherits:
Object
  • Object
show all
Defined in:
lib/primegen/generator.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n) ⇒ Generator

Returns a new instance of Generator.



6
7
8
 
# File 'lib/primegen/generator.rb', line 6

def initialize(n)
	@n = n
end

Instance Attribute Details

#n ⇒ Object (readonly)

Returns the value of attribute n.



4
5
6
 
# File 'lib/primegen/generator.rb', line 4

def n
  @n
end

Instance Method Details

#run ⇒ Object

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.



15
16
17
18
19
20
21
22
23
24
25
26
 
# 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