Class: Primegrid::Prime

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

Class Method Summary collapse

Class Method Details

.find(n) ⇒ Object

Finds the first n primes

Example:

>> Prime.find(10)
=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Arguments:

n: an integer > 0



12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/primegrid/prime.rb', line 12

def self.find(n)
  if n <= 0
    return []
  elsif n <= 10
    return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].slice(0, n)
  end

  # (Over)estimate the nth prime: Pn/n < ln n + ln ln n for n >= 6
  # See: http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
  p = n * (Math.log(n) + Math.log(Math.log(n)))
  return self.sieve(p).slice(0, n)
end

.sieve(n) ⇒ Object

Finds all the primes less than or equal to n

An implementation of the Sieve of Eratosthenes See: en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Example:

>> Prime.sieve(30)
=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Arguments:

n: an integer > 1



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/primegrid/prime.rb', line 36

def self.sieve(n)
  if n < 2 then return [] end
  n = n + 1
  a = Array.new(n){|i| if i >= 2 then true else false end }
  for i in 2..Math.sqrt(n)
    if a[i]
      i_sq = i * i
      j = i_sq
      count = 0
      until j >= n
        a[j] = false
        j = i_sq + (count * i)
        count = count + 1
      end
    end
  end
  return a.each_with_index.map{ |x,i| if x then i end }.compact
end