module PrimeMultiplicationTable::AtkinSieve

AtkinSieve contains implementation of atkin algorithm to find prime numbers.

Public Instance Methods

nth_prime(n) click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 4
def nth_prime(n)
  return Cache[n] if Cache[n]
  Cache.primes = compute_primes(n)
  Cache[n]
end

Private Instance Methods

apply_first_filter(sieve, sieve_size, x2, y2) click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 70
def apply_first_filter(sieve, sieve_size, x2, y2)
  n = x2 * 4 + y2
  sieve[n] = !sieve[n] if n <= sieve_size && (n % 12 == 1 || n % 12 == 5)
end
apply_second_filter(sieve, sieve_size, x2, y2) click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 75
def apply_second_filter(sieve, sieve_size, x2, y2)
  n = x2 * 4 + y2 - x2
  sieve[n] = !sieve[n] if n <= sieve_size && n % 12 == 7
end
apply_third_filter(sieve, sieve_size, x2, y2) click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 80
def apply_third_filter(sieve, sieve_size, x2, y2)
  n = x2 * 4 + y2 - x2 - 2 * y2
  sieve[n] = !sieve[n] if n <= sieve_size && n % 12 == 11
end
atkin_sieve(sieve_size) click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 27
def atkin_sieve(sieve_size)
  sieve = init_sieve
  filter_sieve(sieve, sieve_size)
  finalize_sieve(sieve, sieve_size)
  sieve
end
compute_primes(count) click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 12
def compute_primes(count)
  return Cache.primes if Cache.size > count
  sieve_size = compute_sieve_size(count)
  atkin_sieve(sieve_size).each_with_index.map { |v, p| p if v }.compact
end
compute_sieve_size(count) click to toggle source

TODO: 52 should be replaced with algorithm to find range which cover expected count of prime numbers

As we know the range 1..10**23 contains 1_925_320_391_606_803_968_923 prime numbers

(so, the range contains 1.92 % on prime numbers)

to find 100 prime numbers we need to create sieve 100 * (100 / 1.92) or 100 * 52

# File lib/prime_multiplication_table/atkin_sieve.rb, line 23
def compute_sieve_size(count)
  count * 52
end
filter_sieve(sieve, sieve_size) click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 39
def filter_sieve(sieve, sieve_size)
  sieve_size_sqrt = Math.sqrt(sieve_size).floor

  (1..sieve_size_sqrt).each do |x|
    (1..sieve_size_sqrt).each do |y|
      filter_sieve_iteration(sieve, sieve_size, x, y)
    end
  end
end
filter_sieve_iteration(sieve, sieve_size, x, y) click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 61
def filter_sieve_iteration(sieve, sieve_size, x, y)
  x2 = x**2
  y2 = y**2

  apply_first_filter(sieve, sieve_size, x2, y2)
  apply_second_filter(sieve, sieve_size, x2, y2)
  apply_third_filter(sieve, sieve_size, x2, y2) if x > y
end
finalize_sieve(sieve, sieve_size) click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 49
def finalize_sieve(sieve, sieve_size)
  sieve_size_sqrt = Math.sqrt(sieve_size).floor

  (5..sieve_size_sqrt).each do |n|
    next if Cache[n] || !sieve[n]
    step = n**2
    (step..sieve_size).step(step) do |not_prime|
      sieve[not_prime] = false
    end
  end
end
init_sieve() click to toggle source
# File lib/prime_multiplication_table/atkin_sieve.rb, line 34
def init_sieve
  # 0,  1,   2,    3
  [nil, nil, true, true]
end