Class: Prime::TrialDivision

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

Overview

Internal use. An implementation of prime table by trial division method.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ TrialDivision

:nodoc:



479
480
481
482
483
484
485
486
487
488
489
490
 
# File 'lib/prime.rb', line 479

def initialize # :nodoc:
  # These are included as class variables to cache them for later uses.  If memory
  #   usage is a problem, they can be put in Prime#initialize as instance variables.

  # There must be no primes between @primes[-1] and @next_to_check.
  @primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
  # @next_to_check % 6 must be 1.
  @next_to_check = 103            # @primes[-1] - @primes[-1] % 6 + 7
  @ulticheck_index = 3            # @primes.index(@primes.reverse.find {|n|
  #   n < Math.sqrt(@@next_to_check) })
  @ulticheck_next_squared = 121   # @primes[@ulticheck_index + 1] ** 2
end

Instance Method Details

#[](index) ⇒ Object

Returns the indexth prime number.

index is a 0-based index.



495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
 
# File 'lib/prime.rb', line 495

def [](index)
  while index >= @primes.length
    # Only check for prime factors up to the square root of the potential primes,
    #   but without the performance hit of an actual square root calculation.
    if @next_to_check + 4 > @ulticheck_next_squared
      @ulticheck_index += 1
      @ulticheck_next_squared = @primes.at(@ulticheck_index + 1) ** 2
    end
    # Only check numbers congruent to one and five, modulo six. All others

    #   are divisible by two or three.  This also allows us to skip checking against
    #   two and three.
    @primes.push @next_to_check if @primes[2..@ulticheck_index].find {|prime| @next_to_check % prime == 0 }.nil?
    @next_to_check += 4
    @primes.push @next_to_check if @primes[2..@ulticheck_index].find {|prime| @next_to_check % prime == 0 }.nil?
    @next_to_check += 2
  end
  @primes[index]
end