jzakiya

def gcd(a, b)
  return b if a.zero?
  return a if b.zero?

  k = 0
  while (a | b).even?
     a >>= 1; b >>= 1; k += 1
  end

  a >>= 1 while a.even?

jzakiya

#[
 This Nim source file is a single threaded implementation to perform an
 extremely fast Segmented Sieve of Zakiya (SSoZ) to find Twin Primes <= N.
 It is based on the P5 Strictly Prime (SP) Prime Generator.

 Prime Genrators have the form:  mod*k + ri; ri -> {1,r1..mod-1}
 The residues ri are integers coprime to mod, i.e. gcd(ri,mod) = 1
 For P5, mod = 2*3*5 = 30 and the number of residues are
 rescnt = (2-1)(3-1)(5-1) = 8, which are {1,7,11,13,17,19,23,29}.
 For just Twin Primes, use generator: Pn = 30*k + {11,13,17,19,29,31}

jzakiya

#[
 This Nim source file is a single threaded implementation to perform an
 extremely fast Segmented Sieve of Zakiya (SSoZ) to find Twin Primes <= N.
 It is based on the P5 Strictly Prime (SP) Prime Generator.

 Prime Genrators have the form:  mod*k + ri; ri -> {1,r1..mod-1}
 The residues ri are integers coprime to mod, i.e. gcd(ri,mod) = 1
 For P5, mod = 2*3*5 = 30 and the number of residues are
 rescnt = (2-1)(3-1)(5-1) = 8, which are {1,7,11,13,17,19,23,29}.
 For just Twin Primes, use generator: Pn = 30*k + {11,13,17,19,29,31}

jzakiya

#[
 This Nim source file will compile to an executable program to
 find the nth prime. It's foundation is the Sieve of Zakiya, and it
 performs the Segmented Sieve of Zakiya (SSoZ) to find primes <= N.
 This version is based on the P5 Strictly Prime (SP) Prime Generator.

 Prime Genrators have the form:  mod*k + ri; ri -> {1,r1..mod-1}
 The residues ri are integers coprime to mod, i.e. gcd(ri,mod) = 1
 For P5, mod = 2*3*5 = 30 and the number of residues are
 rescnt = (2-1)(3-1)(5-1) = 8, which are {1,7,11,13,17,19,23,29}.

jzakiya

#[
 This Nim source file is a single threaded implementation to perform an
 extremely fast Segmented Sieve of Zakiya (SSoZ) to find Twin Primes <= N.
 It is based on the P5 Strictly Prime (SP) Prime Generator.

 Prime Genrators have the form:  mod*k + ri; ri -> {1,r1..mod-1}
 The residues ri are integers coprime to mod, i.e. gcd(ri,mod) = 1
 For P5, mod = 2*3*5 = 30 and the number of residues are
 rescnt = (2-1)(3-1)(5-1) = 8, which are {1,7,11,13,17,19,23,29}.
 For just Twin Primes, use generator: Pn = 30*k + {11,13,17,19,29,31}

jzakiya

#[
 This Nim source file will compile to an executable program to
 perform the Segmented Sieve of Zakiya (SSoZ) to find primes <= N.
 It is based on the P5 Strictly Prime (SP) Prime Generator.

 Prime Genrators have the form:  mod*k + ri; ri -> {1,r1..mod-1}
 The residues ri are integers coprime to mod, i.e. gcd(ri,mod) = 1
 For P5, mod = 2*3*5 = 30 and the number of residues are
 rescnt = (2-1)(3-1)(5-1) = 8, which are {1,7,11,13,17,19,23,29}.

jzakiya

module Roots
  require 'complex'
  include Math

  def root(n,k=0) # return kth (1..n) value of root n or default for k=0
    raise "Root  n not an integer >  0" unless n.kind_of?(Integer) && n > 0
    raise "Index k not an integer >= 0" unless k.kind_of?(Integer) && k >= 0
    return self if n == 1 || self == 0
    mag = abs**(1.0/n) ; theta = phase/n ; delta = 2*PI/n  # arg <-> phase
    #mag = abs**n**-1 ; theta = arg/n ; delta = 2*PI/n

jzakiya

require "complex"  # can't require inside module; must use double quotes ""
include Math

module Roots
  def root(n,k=0) # return kth (1..n) value of root n or default for k=0
    raise "Root  n not an integer >  0" unless n.is_a?(Int) && n > 0
    raise "Index k not an integer >= 0" unless k.is_a?(Int) && k >= 0
    return self if n == 1 || self == 0
    v = is_a?(Complex) ? self : self.to_c
    mag = v.abs**(1.0/n); theta = v.phase/n; delta = 2*PI/n

jzakiya

require 'openssl'
require 'parallel'

class Integer
  # Returns true if +self+ passes Miller-Rabin Test on +b+
  def miller_rabin_test(b)             # b is a witness to test with
    return self >= 2 if self <= 3 
    return false unless 6.gcd(self % 6) == 1
    n = d = self - 1
    d >>= 1 while d.even?

jzakiya

#!/usr/local/bin/ruby -w

require 'rational' if RUBY_VERSION =~ /^(1.8)/   # for 'gcd' method

class Integer

   def primz?
      residues = [1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61]
      res1 = [1,13,17,29,37,41,49,53]
      res2 = [7,19,31,43]