Module: Primes::Utils

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

Constant Summary collapse

VERSION = 
"2.4.0"

Instance Method Summary collapse

Instance Method Details

#factors(p = 13) ⇒ Object Also known as: prime_division

p is unused dummy variable for method consistency



31
32
33
34
 
# File 'lib/primes/utils.rb', line 31

def factors(p=0) # p is unused dummy variable for method consistency
  factors = `factor #{self.abs}`.split(' ')[1..-1].map(&:to_i)
  h = Hash.new(0); factors.each {|f| h[f] +=1}; h.to_a.sort
end

#prime? ⇒ Boolean

use pure ruby versions for platforms without cli command ‘factor’

Returns:

  • (Boolean) 


67
68
69
 
# File 'lib/primes/utils.rb', line 67

def prime?
  `factor #{self.abs}`.split(' ').size == 2
end

#primemr?(k = 20) ⇒ Boolean

increase k for more reliability

Returns:

  • (Boolean) 


218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
 
# File 'lib/primes/utils.rb', line 218

def primemr?(k=20)  # increase k for more reliability
  n = self.abs
  return true  if [2,3].include? n
  return false unless [1,5].include?(n%6) and n > 1

  d = n - 1
  s = 0
  (d >>= 1; s += 1) while d.even?
  k.times do
    a = 2 + rand(n-4)
    x = a.to_bn.mod_exp(d,n)      # x = (a**d) mod n
    next if x == 1 or x == n-1
    (s-1).times do
      x = x.mod_exp(2,n)          # x = (x**2) mod n
      return false if x == 1
      break if x == n-1
    end
    return false if x != n-1
  end
  true  # with high probability
end

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



137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# File 'lib/primes/utils.rb', line 137

def primenth(p=7)
  # Return value of nth prime; P7 is default SP Prime Generator
  seeds = [2, 3, 5, 7, 11, 13]
  p = 7 unless seeds.include? p

  n = self.abs                  # the desired nth prime
  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 if nth ref value

  num = approximate_nth(n)      # close approx to nth >= real nth
  primes = seeds[0..seeds.index(p)]
  mod = primes.reduce(:*)       # create modulus of SP PG
  prms, m, modk, residues, rescnt, pcs2start, * = sozcore2(num, start_num, mod)
  return if prms == nil         # exit gracefully if sozcore2 mem error

  # starting at start_num's location, find nth prime within given range
  prmcnt = n > nth ? nth-1 : primes.size
  pcnt = prmcnt + prms[m..-1].count(1)  # number of primes upto nth approx
  return puts "#{pcnt} not enough primes, approx nth too small." if pcnt < n
  while prmcnt < n; prmcnt +=1 if prms[m] == 1; m +=1 end
  k, r = (m + pcs2start).divmod rescnt
  mod*k + residues[r]
end

#primes(start_num = 0) ⇒ Object 



165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/primes/utils.rb', line 165

def primes(start_num=0)
  # Find primes between a number range: end_num - start_num
  # Adaptively selects Strictly Prime (SP) Prime Generator
  num = self.abs;  start_num = start_num.abs
  num, start_num = start_num, num  if start_num > num

  primes, mod = select_pg(num, start_num) # adaptively select PG

  prms, m, modk, residues, rescnt, *, maxprms, r = sozcore2(num, start_num, mod)
  return if prms == nil         # exit gracefully if sozcore2 mem error

  # init 'primes' w/any excluded primes in range then extract primes from prms
  primes = primes.select {|p| p >= start_num && p <= num}
  while m < maxprms             # find primes from sieved pcs in prms for range
    begin
      primes << modk + residues[r] if prms[m] == 1
      rescue Exception
        return puts "ERROR3: not enough memory to store all primes in output array."
    end
    r +=1; if r > rescnt; r=1; modk +=mod end
    m +=1
  end
  primes
end

#primes_utils ⇒ Object 



267
268
269
 
# File 'lib/primes/utils.rb', line 267

def primes_utils
  "prime? primemr? primes primesmr primescnt primescntmr primenth|nthprime factors|prime_division"
end

#primescnt(start_num = 0) ⇒ Object 



190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
 
# File 'lib/primes/utils.rb', line 190

def primescnt(start_num=0)
  # Count primes between a number range: end_num - start_num
  # Uses P5 or P7 Strictly Prime (SP) Prime Generators
  num = self.abs;  start_num = start_num.abs
  num, start_num = start_num, num  if start_num > num

  if start_num < 3              # for all primes upto num
    start_num, nth, nthflag = set_start_value(num,false)
    return nth unless nthflag   # output nth's number if n a ref nth prime
  end

  primes = nthflag ? [2,3,5,7] : [2,3,5]  # use P7 upto an N; P5 for a range
  mod = primes.reduce(:*)
  prms, m, * = sozcore2(num, start_num, mod)
  return if prms == nil         # exit gracefully if sozcore2 mem error

  # init prmcnt for any excluded primes in range then count primes in prms
  prmcnt = primes.select {|p| p >= start_num && p <= num}.size
  prmcnt = nth-1 if nthflag && nth > 0    # nflag is nil or true
  prmcnt + prms[m..-1].count(1)
end

#primescntf(start_num = 0) ⇒ Object 



50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/primes/utils.rb', line 50

def primescntf(start_num=0)
  # Count primes within a number range: end_num - start_num
  # Uses 'prime?' to check primality of prime candidates in range
  sozdata = sozcore1(self, start_num, false) # false for primescnt
  pcs_in_range, r, mod, modk, rescnt, residues, primescnt = sozdata

  pcs_in_range.times do         # count primes from this num pcs in range
    primescnt +=1 if (modk + residues[r]).prime?
    r +=1; if r > rescnt; r=1; modk +=mod end
  end
  primescnt
end

#primescntmr(start_num = 0) ⇒ Object 



254
255
256
257
258
259
260
261
262
263
264
265
 
# File 'lib/primes/utils.rb', line 254

def primescntmr(start_num=0)
  # Count primes within a number range: end_num - start_num
  # Uses 'primemr' to check primality of prime candidates in range
  sozdata = sozcore1(self, start_num, false) # false for primescnt
  pcs_in_range, r, mod, modk, rescnt, residues, primescnt = sozdata

  pcs_in_range.times do         # count primes from this num pcs in range
  primescnt +=1 if (modk + residues[r]).primemr?
  r +=1; if r > rescnt; r=1; modk +=mod end
  end
  primescnt
end

#primesf(start_num = 0) ⇒ Object 



36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/primes/utils.rb', line 36

def primesf(start_num=0)
  # Find primes within a number range: end_num - start_num
  # Uses 'prime?' to check primality of prime candidates in range
  sozdata = sozcore1(self, start_num, true) # true for primes
  pcs_in_range, r, mod, modk, rescnt, residues, primes = sozdata

  pcs_in_range.times do         # find primes from this num pcs in range
    prime = modk + residues[r]
    primes << prime if prime.prime?
    r +=1; if r > rescnt; r=1; modk +=mod end
  end
  primes
end

#primesmr(start_num = 0) ⇒ Object 



240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'lib/primes/utils.rb', line 240

def primesmr(start_num=0)
  # Find primes within a number range: end_num - start_num
  # Uses 'primemr' to check primality of prime candidates in range
  sozdata = sozcore1(self, start_num, true)  # true for primes
  pcs_in_range, r, mod, modk, rescnt, residues, primes = sozdata

  pcs_in_range.times do         # find primes from this num pcs in range
    prime = modk + residues[r]
  primes << prime if prime.primemr?
  r +=1; if r > rescnt; r=1; modk +=mod end
  end
  primes
end