Module: Primes::Utils

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

Constant Summary collapse

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


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

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

#primemr?(k = 20) ⇒ Boolean

increase k for more reliability

Returns:

  • (Boolean) 


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

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 



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
 
# File 'lib/primes/utils.rb', line 138

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,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)]

  prms, m, mod, modk, residues, rescnt, * = sozcore2(num, start_num, primes)
  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 + rescnt*(modk/mod)).divmod rescnt  # (m+pcs2ks).divmod rescnt
  mod*k + residues[r]
end

#primes(start_num = 0) ⇒ Object 



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 167

def primes(start_num=0)
  # Find primes between a number range: end_num - start_num
  # Uses the P5 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]              # P5 excluded primes lists
  plast  = primes.last          # last prime in primes
  return primes.select {|p| p >= start_num && p <= num} if num <= plast

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

  # starting at start_num's location, extract primes within given range
  primes = start_num <= plast ? primes.select {|p| p >= start_num} : [] 
  while m < maxprms              # find primes from pcs within given 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 



271
272
273
 
# File 'lib/primes/utils.rb', line 271

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
211
212
213
 
# 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

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

  if start_num == 0
    start_num, nth, nthflag = set_start_value(num,false)
    return nth if !nthflag      # output nth's number if n a ref nth prime
  end

  primes = nthflag ? [2,3,5,7] : [2,3,5]  # choose P7 or P5
  prms, m, * = sozcore2(num, start_num, primes)
  return if prms == nil         # exit gracefully if sozcore2 mem error

  # starting at start_num's location, count primes within given range
  prmcnt = start_num <= plast ? primes.select {|p| p >= start_num}.size : 0
  prmcnt = nth > 0 ? nth-1 : primes.size if nthflag  # 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
62
 
# 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
  return sozdata[1] if !sozdata[0]           # if sozdata[0] false
  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 



257
258
259
260
261
262
263
264
265
266
267
268
269
 
# File 'lib/primes/utils.rb', line 257

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]           # if sozdata[0] false
  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
  return sozdata[1] if !sozdata[0]          # if sozdata[0] false
  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 



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

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]           # if sozdata[0] false
  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