Module: Primes::Utils

Included in:
Integer
Defined in:
lib/primes/utils.rb,
lib/primes/utils/version.rb

Constant Summary collapse

VERSION = 
"3.0.4"
@@os_has_factor =

Upon loading, determine if platform has cli command ‘factor’

false

Instance Method Summary collapse

Instance Method Details

#factors ⇒ Object

Return prime factors of n in form [[-1,1],,…[pn,en]] Use Linux|Unix coreutils cli command ‘factor’ for speed and large numbers



26
27
28
29
30
 
# File 'lib/primes/utils.rb', line 26

def factors
  factors = self < 0 ? [-1] : []
  factors += `factor #{abs}`.split(' ')[1..-1].map(&:to_i)
  factors.group_by { |prm| prm }.map { |prm, exp| [prm, exp.size] }
end

#factors1 ⇒ Object Also known as: prime_division

Return prime factors of n in form [[-1,1],,..[pn,en]] Adaptively selects optimum PG of reduced factored number, if possible



40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/primes/utils.rb', line 40

def factors1
  modpg, rescnt = 210, (48 + 4)         # P7's modulus and residues count
  residues = [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,103,107,109,113,121,127,131,137,139,143,149,151,157,163,
            167,169,173,179,181,187,191,193,197,199,209,211]

  factors = self < 0 ? [-1] : []        # returns [] for 0|1; [-1, 1] for negatives
  num = self.abs                        # factor only non-negative integers

  unless num.prime? || (num | 1) == 1   # skip factoring if num is prime, 0, or 1
    modk, r, r0 = 0, 0, 4               # r0 is index for P7's first residue 11
    until num.prime? || num == 1        # find factors until num is prime or 1
      while prime = modk + residues[r]
        (factors << prime; num /= prime; break) if (num % prime).zero?
        (r = r0; modk += modpg) if (r = r.succ) == rescnt
  end end end
  factors << num if num > 1
  factors.group_by{ |prm| prm}.map{ |prm, exp| [prm, exp.size] }
end

#next_prime ⇒ Object

Returns the next prime number for self >= 0, or nil if n < 0



185
186
187
188
189
190
191
192
193
 
# File 'lib/primes/utils.rb', line 185

def next_prime
  return nil if (n = self) < 0
  return (n >> 1) + 2 if n <= 2                # return 2 if n is 0|1
  n = n + 1 | 1                                # 1st odd number > n
  until (res = n % 6) & 0b11 == 1; n += 2 end  # n first P3 pc >= n, w/residue 1 or 5
  inc = (res == 1) ? 4 : 2                     # set its P3 PGS value, inc by 2 and 4
  until n.primemr?; n += inc; inc ^= 0b110 end # find first prime P3 pc
  n
end

#prev_prime ⇒ Object

Returns the previous prime number < self, or nil if self <= 2



196
197
198
199
200
201
202
203
204
 
# File 'lib/primes/utils.rb', line 196

def prev_prime
  return nil if (n = self) < 3
  return (n >> 1) + 1 if n <= 5
  n = n - 2 | 1                                # 1st odd number < n
  until (res = n % 6) & 0b11 == 1; n -= 2 end  # n first P3 pc <= n, w/residue 1 or 5
  dec = (res == 1) ? 2 : 4                     # set its P3 PGS value, dec by 2 and 4
  until n.primemr?; n -= dec; dec ^= 0b110 end # find first prime P3 pc
  n
end

#prime?(k = 5) ⇒ Boolean

PGT and Miller-Rabin combined primality tests for random n

Returns:

  • (Boolean) 


176
177
178
179
180
181
182
 
# File 'lib/primes/utils.rb', line 176

def prime? (k = 5)      # Can change k higher for mr_prime?
  #Use PGT residue checks for small values < PRIMES.last**2
  return PRIMES.include? self if self <= PRIMES.last
  return false if MODPN.gcd(self) != 1
  return true  if self < PRIMES_LAST_SQRD
  primemr?(k)
end

#primemr?(k = 5) ⇒ Boolean

Returns true if self is a prime number, else returns false.

Returns:

  • (Boolean) 


214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
 
# File 'lib/primes/utils.rb', line 214

def primemr? (k = 5)               # k is default number of random bases
  return false if self < 2         # return false for 0|1 and negatives
  neg_one_mod = n = d = self - 1   # these are even as self is always odd
  d >>= 2 while (d & 0b11) == 0; d >>= (d & 1)^1  # make d odd number
  # wits = [range, [wit_prms]] or nil
  wits = WITNESS_RANGES.find { |range, wits| range > self }
  witnesses = wits ? wits[1] : k.times.map{ rand(self - 4) + 2 }
  witnesses.each do |b|
    next if (b % self).zero?       # **skip base if a multiple of input**
    y = b.pow(d, self)             # y = (b**d) mod self
    s = d
    until y == 1 || y == neg_one_mod || s == n
      y = y.pow(2, self)           # y = (y**2) mod self
      s <<= 1
    end
    return false unless y == neg_one_mod || s.odd?
  end
  true
end

#primenth(p = 0) ⇒ Object Also known as: nthprime

Return value of nth prime for self > 0, or nil if self < 1 Adaptively selects best SP PG, unless valid input PG given at runtime



65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
# File 'lib/primes/utils.rb', line 65

def primenth(p = 0)
  return nil if (n = self) < 1
  seeds = [2, 3, 5, 7, 11, 13]
  return n > 0 ? seeds[n - 1] : 0 if n <= seeds.size

  start_num, nth, nthflag = set_start_value(n, true)
  return start_num if nthflag      # output nthprime value if n a ref prime key
  end_num = approximate_nth(n)     # close approx to nth >= real nth

  (primes = seeds[0..seeds.index(p)]; modpg = primes.reduce(:*)) if seeds.include? p
  primes, modpg = select_pg(end_num, start_num) unless primes

  prms, m, _, residues, pcs2start, * = sozcore2(end_num, start_num, modpg)
  return unless prms               # exit gracefully if sozcore2 mem error

  # starting at start_num's location, find nth prime within given range
  pcnt = n > nth ? nth - 1 : primes.size
  max  = prms.size
  while pcnt < n && m < max; pcnt = pcnt.succ if prms[m].zero?; m = m.succ end
  return puts "#{pcnt} not enough primes, ~nth val too small." if pcnt < n
  k, r = (m + pcs2start - 1).divmod residues.size
  modpg * k + residues[r]
end

#primes(start_num = 0) ⇒ Object

List primes between a number range: end_num - start_num Adaptively selects Strictly Prime (SP) Prime Generator



93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/primes/utils.rb', line 93

def primes(start_num = 0)
  end_num, start_num = check_inputs(self, start_num)

  primes, modpg = select_pg(end_num, start_num) # adaptively select PG
  prms, m, modk, residues, _, r = sozcore2(end_num, start_num, modpg)
  return unless prms               # exit gracefully if sozcore2 mem error
  rescnt, modpg, maxprms = residues.size, residues[-1] - 1, prms.size

  # init 'primes' w/any excluded primes in range, extract primes from prms
  primes.select! { |p| p >= start_num && p <= end_num }

  # Find, numerate, and store primes from sieved pcs in prms for range 
  while m < maxprms
    begin
      primes << modk + residues[r] if prms[m].zero?; m = m.succ
    rescue Exception
      return puts 'ERROR3: not enough sys memory for primes output array.'
    end
    (r = 0; modk += modpg) if (r = r.succ) == rescnt
  end
  primes
end

#primes_utils ⇒ Object 



206
207
208
209
210
211
 
# File 'lib/primes/utils.rb', line 206

def primes_utils
  # display list of available methods
  methods = %w[prime? primemr? primes primesmr primescnt
               primescntmr primenth|nthprime factors|prime_division
               factors1 next_prime prev_prime primes_utils].join(" ")
end

#primescnt(start_num = 0) ⇒ Object

Count primes between a number range: end_num - start_num Adaptively selects Strictly Prime (SP) Prime Generator



118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/primes/utils.rb', line 118

def primescnt(start_num = 0)
  end_num, start_num = check_inputs(self, start_num)

  nthflag, nth = 0, 0
  if start_num < 3                 # for all primes upto num
    start_num, nth, nthflag = set_start_value(end_num, false) # closest nth value
    return nth unless nthflag      # output num's key|count if ref nth value
  end

  primes, modpg = select_pg(end_num, start_num) # adaptively select PG
  prms, m, _ = sozcore2(end_num, start_num, modpg)
  return unless prms               # exit gracefully if sozcore2 mem error

  # init prmcnt for any modulus primes in range; count primes in prms
  prmcnt = primes.count { |p| p >= start_num && p <= end_num }
  prmcnt = nth - 1 if nthflag && (nth > 0)  # start count for small range
  max = prms.size
  while m < max; prmcnt = prmcnt.succ if prms[m].zero?; m = m.succ end
  prmcnt
end

#primescntmr(start_num = 0) ⇒ Object

Count primes within a number range: end_num - start_num Uses ‘primemr’ to check primality of prime candidates in range



155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
# File 'lib/primes/utils.rb', line 155

def primescntmr(start_num = 0)
  end_num, start_num = check_inputs(self, start_num)

  nthflag, nth = 0, 0
  if start_num < 3                 # for all primes upto num
    start_num, nth, nthflag = set_start_value(end_num, false) # closest nth value
    return nth unless nthflag      # output num's key|count if ref nth value
  end

  r, modk, residues, mod_primes = sozcore1(end_num, start_num)
  rescnt, modpg, primescnt = residues.size, residues[-1] - 1, mod_primes.size
  primescnt = nth - 1 if nthflag && (nth > 0)  # set count for nth prime < num

  while end_num >= (pc = modk + residues[r])
    primescnt = primescnt.succ if pc.primemr?
    (r = 0; modk += modpg) if (r = r.succ) == rescnt
  end
  primescnt
end

#primesmr(start_num = 0) ⇒ Object

List primes within a number range: end_num - start_num Uses ‘primemr’ to check primality of prime candidates in range



141
142
143
144
145
146
147
148
149
150
151
 
# File 'lib/primes/utils.rb', line 141

def primesmr(start_num = 0)
  end_num, start_num = check_inputs(self, start_num)
  r, modk, residues, primes = sozcore1(end_num, start_num)
  rescnt, modpg = residues.size, residues[-1] - 1

  while end_num >= (pc = modk + residues[r])
    primes << pc if pc.primemr?
    (r = 0; modk += modpg) if (r = r.succ) == rescnt
  end
  primes
end