Class: FundingPrimer::Prime::TrialDivisionGenerator

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

Overview

Tests for primality explicitly by brute force

Modulo 2 and 3 optimisations are exploited, as well as testing possible prime factors only up to the square root of the prime candidate

Instance Method Summary collapse

Constructor Details

#initialize ⇒ TrialDivisionGenerator

start off @primes with 2 and 3, after which

6k ± 1, k > 0

are the only candidates that are not divisible by 2 or 3



36
37
38
39
40
41
42
43
 
# File 'lib/funding_primer/prime.rb', line 36

def initialize
  @primes = [2,3]
  @candidate = 5
  @jump = 4 # jump to next candidate
  # start from 5, since factors of 2 and 3 are not checked
  @biggest_candidate_factor_index = 3
  @next_biggest_candidate_factor_squared = 121 # 11 squared
end

Instance Method Details

#first(n) ⇒ Object

Lazily generates each successive prime that hasn’t been cached yet



46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/funding_primer/prime.rb', line 46

def first(n)
  while n > @primes.length
    # if necessary, add 1 extra prime to the factors that are tested
    expand_candidate_factors

    # append a truly prime number
    append_candidate_to_primes

    jump_to_next_candidate
  end

  @primes.take(n)
end