Module: Primes::Utils

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

Constant Summary collapse

VERSION = 
"2.0.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



29
30
31
32
 
# File 'lib/primes/utils.rb', line 29

def factors(p=0) # p is unused dummy variable for method consistency
  factors = `factor #{self.abs}`.split(' ')[1..-1].map {|i| i.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) 


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

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

#primemr?(k = 20) ⇒ Boolean

increase k for more reliability

Returns:

  • (Boolean) 


224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# File 'lib/primes/utils.rb', line 224

def primemr?(k=20)  # increase k for more reliability
  n = self.abs
  return true  if n == 2 or n == 3
  return false if n % 6 != 1 && n % 6 != 5 or 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 



136
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
162
163
164
165
166
 
# File 'lib/primes/utils.rb', line 136

def primenth(p=7)
  # Return value of nth prime
  # Uses sozP7 Sieve of Zakiya (SoZ) as default Prime Generator
  seeds = [2, 3, 5, 7, 11, 13]
  p = 7 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, nths)
  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)]

  ks, mod, residues, maxprms, 
  max_range, prms, prms_range = sozcore2(num, start_num, primes)

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

#primes(start_num = 0) ⇒ Object 



170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
 
# File 'lib/primes/utils.rb', line 170

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

  primes = [2,3,5,7,11,13]      # P13 excluded primes lists
  plast  = primes.last          # last prime in primes
  return primes.select {|p| p >= start_num && p <= num} if num <= plast

  ks, mod, residues, maxprms, 
  max_range, prms, prms_range = sozcore2(num, start_num, primes)
 
  rescnt = residues[1..-1].size
  # starting at start_num's location, extract primes within given range
  primes = start_num <= plast ? primes.drop_while {|p| p < start_num} : []
  if ks > 0; maxprms = max_range; prms = prms_range end
  m=0; r=1; modk = mod*ks;      # find number of pcs, m, in ks < start_num
  while modk + residues[r] < start_num; r +=1; m +=1 end
  (maxprms-m).times do          # find primes from this num pcs within range
	primes << modk + residues[r] if prms[m] == 1
    r +=1; if r > rescnt; r=1; modk +=mod end
	m +=1
  end
  primes
end

#primes_utils ⇒ Object 



274
275
276
 
# File 'lib/primes/utils.rb', line 274

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

#primescnt(start_num = 0) ⇒ Object 



197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/primes/utils.rb', line 197

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

  primes = [2,3,5,7,11,13]      # P13 excluded primes lists
  plast  = primes.last          # last prime in primes
  return primes.select {|p| p >= start_num && p <= num}.size if num <= plast

  ks, mod, residues, maxprms, 
  max_range, prms, prms_range = sozcore2(num, start_num, primes)

  # starting at start_num's location, count primes within given range
  primes = start_num <= plast ? primes.drop_while {|p| p < start_num} : []
  prms = prms_range if ks > 0
  m=0; r=1; modk = mod*ks       # find number of pcs, m, in ks < start_num
  while modk + residues[r] < start_num; r +=1; m +=1 end
  primecnt = primes.size + prms[m..-1].count(1)
end

#primescntf(start_num = 0) ⇒ Object 



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

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
  return sozdata[1] if sozdata[0]
  pcs_in_range, r, mod, modk, rescnt, residues, primes = sozdata[1..-1]
  primescnt = primes.size
  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 



260
261
262
263
264
265
266
267
268
269
270
271
272
 
# File 'lib/primes/utils.rb', line 260

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
  return sozdata[1] if sozdata[0]
  pcs_in_range, r, mod, modk, rescnt, residues, primes = sozdata[1..-1]
  primescnt = primes.size
  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 



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

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
  return sozdata[1] if sozdata[0]
  pcs_in_range, r, mod, modk, rescnt, residues, primes = sozdata[1..-1]
  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 



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

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
  return sozdata[1] if sozdata[0]
  pcs_in_range, r, mod, modk, rescnt, residues, primes = sozdata[1..-1]
  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