primes-utils

Introduction

primes-utils is a Rubygem which provides a suite of extremely fast (relative to Ruby's standard library) utility methods for testing and generating primes.

For details on best use practices and implementation details see:

PRIMES-UTILS HANDBOOK

https://www.scribd.com/doc/266461408/Primes-Utils-Handbook

Periodically check for updates.

Installation

Add this line to your application's Gemfile:

gem 'primes-utils'

And then execute:

$ bundle

Or install it yourself as:

$ gem install primes-utils

Then require as:

require 'primes/utils'

Methods

prime?

Determine if the absolute value of an integer is prime. Return 'true' or 'false'. This replaces the prime? method in the prime.rb standard library.

101.prime? => true
100.prime? => false
-71.prime? => true
0.prime? => false
1.prime? => false

primemr?(k=20)

Using Miller-Rabin primality test for integers, return 'true' or 'false'. Miller-Rabin [6] is super fast, but probabilistic (not deterministic), primality test. The reliability can be increased by increasing the default input parameter of k=20.

1111111111111111111.primemr? => true
1111111111111111111.primemr? 50  => true
1111111111111111111.primemr?(50) => true
11111111111111111111.primemr? => false
-3333333333333333333.primemr? => false
0.prime? => false
1.prime? => false

factors(p=13) or prime_division(p=13)

Determine the prime factorization of the absolute value of an integer. This replaces the prime_division method in the prime.rb standard library. Output is array of arrays of factors and exponents: [[p1,e1],[p2,e2]..[pn,en]]. Default Strictly Prime (SP) Prime Generator (PG) used here is P13. Can change SP PG used on input. Acceptable primes range: [3 - 19].

1111111111111111111.prime_division => [[1111111111111111111, 1]]
11111111111111111111.prime_division  => [[11, 1], [41, 1], [101, 1], [271, 1], [3541, 1], [9091, 1], [27961, 1]]
123456789.factors => [[3, 2], [3607, 1], [3803, 1]]
123456789.factors 17 => [[3, 2], [3607, 1], [3803, 1]]
123456789.factors(17) => [[3, 2], [3607, 1], [3803, 1]]
-12345678.factors => [[2, 1], [3, 2], [47, 1], [14593, 1]]
0.factors => []
1.factors => []

primes(start=0), primesf(start=0), primesmr(start=0)

Return an array of primes within the absolute value range (|start| - |end|). The order of the range doesn't matter if both given: start.primes end <=> end.prime start. If only one parameter used, then all the primes upto that number will be returned. See PRIMES-UTILS HANDBOOK for details on best use practices. Also see Error Handling.

50.primes => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
50.primesf 125 => [53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
300.primes 250 => [251, 257, 263, 269, 271, 277, 281, 283, 293]
n=10**100; (n-250).primesmr(n+250) => []
541.primes.size => 100
1000.primes(5000).size => 501
(prms = 1000000.primes(1000100)).size => 6
prms.size => 6
prms => [1000003, 1000033, 1000037, 1000039, 1000081, 1000099]
-10.primes -50  => [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
0.primesf  => []
1.primesmr => []

primescnt(start=0), primescntf(start=0), primescntmr(start=0)

Provide count of primes within the absolute value range (|start| - |end|). The order of the range doesn't matter if both given: start.primes end <=> end.prime start. If only one parameter used, the count of all the primes upto that number will be returned. See PRIMES-UTILS HANDBOOK for details on best use practices. Also see Error Handling.

100001.primescnt => 9592
100002.primescnt => 9592
100003.primescnt => 9593
100000.primescntf 100500 => 40
n=10**400; (n-500).primescntmr(n+500) => 1
-10.primescnt -50  => 11
0.primescntf  => 0
1.primescntmr => 0

primenth(p=7) or nthprime(p=7)

Return the value of the (absolute value of) nth prime. Default Strictly Prime (SP) Prime Generator (PG) used here is P7. Can change SP PG used on input. Acceptable primes range: [3 - 13]. Indexed nth primes now upto 1.6 billionth. Also see Error Handling.

1000000.primenth => 15485863
1500000.nthprime => 23879519
2000000.nthprime 11 => 32452843
-500000.nthprime => 7368787
1122951705.nthprime => 25741879847
0.nthprime => 0
1.primenth => 2

primes_utils

Displays a list of all the primes-utils methods available for your system. Use as x.primes_utils where x is any class Integer value.

0.primes_utils => "prime? primemr? primes primesf primesmr primescnt primescntf primescntmr primenth|nthprime factors|prime_division"

Error Handling

Starting with 2.2.0, error handling has been implemented to gracefully handle when array creation requires more memory than available. This occurs when the range size, or end_num, need arrays greater than the amount of avalable memory. The first case shows the message ERROR1: range size too big for available memory. and the second case ERROR2: end_num too big for available memory. The affected methods are nthprime|primenth, primes, and primescnt. nthprime|primenth also displays the error message <yyyy> not enough primes, approx nth too small. (where <yyyy> is an integer value) when the computed approx_nth value < nth value. For all errors, the return value for each method is nil.

This behavior is referenced to MRI Ruby.

Coding Implementations

The methods primemr?, nthprime|primenth, primes, primescnt, primesmr, and primescnt are coded in pure ruby. The methods prime? and prime_division|factors have two implementations. Each has a pure ruby implementation, and a hybrid implementation using the Unix cli command factor if its available on the host OS. The methods primesf and primescntf use the factor version of prime? and are created if it exits. factor [5] is an extremely fast C coded factoring algorithm, part of the GNU Core Utilities package [4].

Upon loading, the gem tests if the command factor exists on the host OS. If so, it performs a system call to it within prime? and prime_division|factors, which uses its output. If not, each method uses a fast pure ruby implementation based on the Sieve of Zakiya (SoZ)[1][2][3]. New in 2.2.0, upon loading with Ruby 1.8 require 'rubygems' is invoked to enable installing gems.

All the primes-utils methods are instance_methods for class Integer.

History

2.3.0 

Author

Jabari Zakiya

References

[1]https://www.scribd.com/doc/150217723/Improved-Primality-Testing-and-Factorization-in-Ruby-revised [2]https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ [3]https://www.scribd.com/doc/73385696/The-Sieve-of-Zakiya [4]https://en.wikipedia.org/wiki/GNU_Core_Utilities [5]https://en.wikipedia.org/wiki/Factor_(Unix) [6]https://en.wikipedia.org/wiki/Miller-Rabin_primality_test

License

GPLv2+