Class: Prime::TrialDivision

Inherits:
Object show all
Includes:
Singleton
Defined in:
lib/backports/1.9.1/stdlib/prime.rb

Overview

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

Instance Method Summary collapse

Constructor Details

#initialize ⇒ TrialDivision

:nodoc:



377
378
379
380
381
382
383
384
385
386
387
388
 
# File 'lib/backports/1.9.1/stdlib/prime.rb', line 377

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.



400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
 
# File 'lib/backports/1.9.1/stdlib/prime.rb', line 400

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

#cache ⇒ Object Also known as: primes, primes_so_far

Returns the cached prime numbers.



391
392
393
 
# File 'lib/backports/1.9.1/stdlib/prime.rb', line 391

def cache
  @primes
end