Class: PrimeUtils

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

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PrimeUtils

Returns a new instance of PrimeUtils.



8
9
10
11
12
 
# File 'lib/prime_utils.rb', line 8

def initialize
  @memoized = {} # stores true if composite
  @ulimit = 150
  @primes = []
end

Class Method Details

.n_primes(n) ⇒ Object 



14
15
16
17
 
# File 'lib/prime_utils.rb', line 14

def self.n_primes n
  item = self.new
  return item.n_primes n
end

.prime?(n) ⇒ Boolean

Returns:

  • (Boolean) 


49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/prime_utils.rb', line 49

def self.prime? n
  coprime = 2
  # integer `2` is a good enough co-prime to any integer.

  n = Integer( n )

  if n < 2
    return false
  elsif 2 == n
    return true
  elsif 0 == n % 2
    return false
  else
    result = 2**(n-1) % n
    if 1 != result
      return false
    else
      return true
    end
  end
end

Instance Method Details

#compute(current = 2) ⇒ Object 



30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/prime_utils.rb', line 30

def compute current = 2
  # puts! current
  # puts! @memoized
  return if current > @ulimit
  
  if @memoized[current]
    # current is composite, switch to next
    return compute( current + 1 )
  else
    @primes << current
    ttt = current + current # ttt is steps of length current, up to @ulimit
    while ttt < @ulimit do
      @memoized[ ttt ] = true
      ttt = ttt + current
    end
    return compute( current + 1 )
  end
end

#n_primes(n) ⇒ Object 



19
20
21
22
23
24
25
26
27
28
 
# File 'lib/prime_utils.rb', line 19

def n_primes n
  if @primes.length < n
    initialize()
    @ulimit = @ulimit * 2
    compute
    return n_primes n
  else
    return @primes.take( n )
  end
end

#ulimit=(n) ⇒ Object 



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

def ulimit= n
  @ulimit = n
end