Module: Primes::Utils

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

Constant Summary collapse

VERSION = 
"2.5.1"

Instance Method Summary collapse

Instance Method Details

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

p is unused dummy variable for method consistency



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

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) 


62
63
64
 
# File 'lib/primes/utils.rb', line 62

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

#primemr?(k = 20) ⇒ Boolean

increase k for more reliability

Returns:

  • (Boolean) 


208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
 
# File 'lib/primes/utils.rb', line 208

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  # n is prime (with high probability)
end

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



129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/primes/utils.rb', line 129

def primenth(p=0)
  # Return value of nth prime
  # Adaptively selects best SP PG, unless valid input PG given at runtime
  seeds = [2, 3, 5, 7, 11, 13]
  (primes=seeds[0..seeds.index(p)]; mod=primes.reduce(:*)) if 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 value if n a ref prime key

  num = approximate_nth(n)      # close approx to nth >= real nth
  primes, mod = select_pg(num, start_num) unless primes
  prms, m, modk, residues, rescnt, pcs2start, * = sozcore2(num, start_num, mod)
  return unless prms            # 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 



157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
# File 'lib/primes/utils.rb', line 157

def primes(start_num=0)
  # List 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, x, maxprms, r = sozcore2(num, start_num, mod)
  return unless prms            # exit gracefully if sozcore2 mem error

  # init 'primes' w/any excluded primes in range then extract primes from prms
  primes.select! {|p| p >= start_num && p <= num}
  while m < maxprms             # list 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

display list of available methods



257
258
259
260
261
 
# File 'lib/primes/utils.rb', line 257

def primes_utils                # display list of available methods
  methods = %w/prime? primemr? primes primesf primesmr primescnt
               primescntf primescntmr primenth|nthprime factors|prime_division primes_utils/
  (methods - (@@os_has_factor ? [] : %w/primesf primescntf/)).join(" ")
end

#primescnt(start_num = 0) ⇒ Object 



181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 
# File 'lib/primes/utils.rb', line 181

def primescnt(start_num=0)
  # Count 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

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

  primes,mod = select_pg(num, start_num)  # adaptively select PG
  prms, m, * = sozcore2(num, start_num, mod)
  return unless prms            # exit gracefully if sozcore2 mem error

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

#primescntf(start_num = 0) ⇒ Object 



45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/primes/utils.rb', line 45

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 primes count
  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 



244
245
246
247
248
249
250
251
252
253
254
255
 
# File 'lib/primes/utils.rb', line 244

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 



31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/primes/utils.rb', line 31

def primesf(start_num=0)
  # List 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 list
  pcs_in_range, r, mod, modk, rescnt, residues, primes = sozdata

  pcs_in_range.times do         # list 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 



230
231
232
233
234
235
236
237
238
239
240
241
242
 
# File 'lib/primes/utils.rb', line 230

def primesmr(start_num=0)
  # List 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         # list 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