Module: PrimeProducts::PrimeNumbers::SieveOfEratosthenes

Defined in:
lib/prime_products/prime_numbers/sieve_of_eratosthenes.rb

Class Method Summary collapse

Class Method Details

.first(number_of_primes) ⇒ Immutable::SortedSet<Integer>

Finds the first ‘n` prime numbers using the performant Sieve of Eratosthenes method.

See ‘benchmarks/prime_numbers.rb` - it performs well, but as not as well as the solution in Ruby’s stdlib 😭 But at least it’s written in Ruby (not C) and is fairly easy to understand.

Parameters:

  • number_of_primes (Integer) —

    the number of prime numbers, starting from 0, you want to find

Returns:

  • (Immutable::SortedSet<Integer>) —

    the first ‘n` prime numbers



18
19
20
21
 
# File 'lib/prime_products/prime_numbers/sieve_of_eratosthenes.rb', line 18

def self.first(number_of_primes)
  estimated_max = number_of_primes * Math.log(number_of_primes * number_of_primes)
  Immutable::SortedSet[*upto(estimated_max).first(number_of_primes)]
end

.upto(maximum) ⇒ Array<Integer>

Finds all prime numbers up to ‘maximum` using the performant Sieve of Eratosthenes method.

Parameters:

  • maximum (Integer) —

    the number you want to find primes up to

Returns:

  • (Array<Integer>) —

    all of the prime numbers up to ‘maximum`



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

def self.upto(maximum)
  # All numbers *might* be primes until we start ruling them out
  primes = (0..maximum).to_a

  # Zero and one aren't considered prime numbers
  primes[0] = primes[1] = nil

  primes.each do |n|
    # Skip if this number has already been removed when stepping through
    # multiples
    next unless n

    break if n * n > maximum

    # Remove multiples of the number we're looking at - they're not primes
    (n * n).step(maximum, n) { |i| primes[i] = nil }
  end

  primes.compact
end