# PrimeSieve

*Prime number and factoring functions*

This package provides functions related to prime numbers and factoring,
mostly for generating and counting primes and factoring integers. This package
uses some of the fastest open-source libraries for these functions.
The name `Primes`

would be better, but that might cause collisions.

Note: Dec 5, 2016. Bitrot rests for no man. Quite a bit still works, but quite a bit not.
Broken tests are commented out, so tests suite should pass. If you want to fix something and
make a PR, please do. The most challenging problem is the C wrapper to make `libsmsieve.so`

from a standalone program no longer works for all inputs.

See LICENSE.md for links to the authors of the tables and the libraries used in this package.

I am unaware of binaries of libprimesieve and libprimecount for Windows and OSX, so there is no easy installation for these platforms.

This is not a registered package, and it has a non-registered dependency. You can install it (at least on Unix) with

```
Pkg.clone("https://github.com/jlapeyre/DeepConvert.jl")
Pkg.clone("https://github.com/jlapeyre/PrimeSieve.jl")
Pkg.build("PrimeSieve")
```

Some functions in this package

`genprimes(a,b)`

generate array of primes between`a`

and`b`

, inclusive`genprimes(b)`

generate array of primes between 2 and`b`

`mfactor(n)`

factor integers up to about 100 decimal digits.`primepi(n)`

the prime counting function: number of primes < n`countprimes(a,b)`

number of primes between a and b`nextprime(n)`

,`prevprime(n)`

first prime greater (or smaller) than n`someprimes(n1,n2)`

iterator. all primes from n1 through n2`someprimes(n2)`

all primes from 2 through n2`allprimes(n)`

iterator. all primes >= n`allprimes()`

all primes`nthprime(n)`

the nth prime`nprimes(n,start)`

generate array of the first n primes > start`isprime(z)`

primality test for Gaussian integers`randprime(a,b)`

random prime between`a`

and`b`

This package uses the following tables and libraries.

[T. Oliveira's tables of the prime counting function] (http://www.ieeta.pt/~tos/primes.html)

Prime number sieve library [libprimesieve] (http://primesieve.org/) and prime counting function library libprimecount

Integer factoring libraries msieve and gmp-ecm

### Data types

The tables are encoded in Int128. The native type of the sieve (libprimesieve) is
Uint64. The input/output type of the fastest primepi algorithm in libprimecount, the Deleglise Rivat
algorithm, is Int128. There is a risk of overflow when constructing and giving
arguments to functions in this package. The easiest way to avoid this
is to put arguments in quotes: eg `countprimes("10^19","10^19+100")`

.
Also available are `@bigint`

and `@int128`

from DeepConvert.

## Functions

Most of the following functions are vectorized.

### genprimes

`genprimes(start,stop)`

Return an array of all primes `>= start`

and `<= stop`

.

`genprimes(stop)`

Return an array of all primes between 1 and `stop`

`genprimes(start,stop; alg = algorithm)`

Generate primes using a specified algorithm. The algorithm must be
one of `:auto`

(the default), `:sieve`

, or `:next`

. Which algorithm is
more efficient depends on the parameters. In general, `:sieve`

is
better for larger intervals, and `:next`

is better for larger values
of `start`

. The keyword `:sieve`

uses a very fast sieve (libprimesieve), and
`:next`

uses the function `nextprime`

.

If you exceed the upper limit for argument to the sieve, then `:next`

is chosen automatically.

```
julia> @bigint genprimes(10^20, 10^20+1000)
24-element Array{BigInt,1}:
100000000000000000039 ...
```

This could also have been written `genprimes(bi"10^20", bi"10^20+1000")`

### primepi

Computes the prime counting function.

`primepi(x; alg = algorithm)`

The efficient algorithms (or methods) are :auto (the default), :dr, and :tabsieve. The default, :auto, tries to choose the faster between :dr and :tabsieve (see Notes below). The other algorithms are slower in all cases. They are: :legendre, :lehmer, :meissel, :lmo, :sieve. The algorithm :dr uses an efficient parallel Deleglise Rivat method. The algorithm :tabsieve uses a combination of tables and a sieve and is more efficient when x is not too much greater than a table entry. (Note: Below, 10^14+10^8 is not too much greater than 10^14.) For example

```
julia> @time primepi(10^14+10^10; alg = :tabsieve)
elapsed time: 6.622672664 seconds (216 bytes allocated)
3205251958942
julia> @time primepi(10^14+10^10; alg = :dr) # Deleglise Rivat is faster
elapsed time: 0.495413145 seconds (208 bytes allocated)
3205251958942
julia> @time primepi(10^14+10^8; alg = :dr)
elapsed time: 0.505796298 seconds (208 bytes allocated)
3204944853481
julia> @time primepi(10^14+10^8; alg = :tabsieve) # Table and sieve is faster
elapsed time: 0.08235147 seconds (216 bytes allocated)
3204944853481
```

### mfactor

Factor an integer.

Example:

```
julia> @time mfactor("2^251-1")
elapsed time: 29.709989827 seconds (13283880 bytes allocated)
Dict{Int128,Int64} with 5 entries:
12070396178249893039969681 => 1
178230287214063289511 => 1
61676882198695257501367 => 1
503 => 1
54217 => 1
```

`mfactor(n; ecm = true)`

uses ecm
to search for factors larger than 15 digits, rather than less than 15 digits.

`mfactor(n; deadline = m)`

aborts the factoring after `m`

minutes.

`mfactor(n; logfile = "filename.log")`

writes information to a log file.

`mfactor(n; info = true)`

prints log information to the terminal.

`mfactor( @bigint [ 2^100 + i for i in -5:5] ) # returns an array of factorizations.`

`mfactor`

calls libmsieve and libecm.

### countprimes

Count the number of primes (or
prime tuplets in an interval. This
looks up the largest value in the table that is smaller than the
requested value and computes the remaining values. Note that `primepi`

is
logically equivalent to countprimes with `start=1`

. For `start=1`

,
The function `primepi`

is often much faster than, and is never slower than `countprimes`

```
countprimes(stop) # count the number of primes less than or equal to stop
countprimes(start,stop) # count the number of primes >= start and <= stop
countprimes([start], stop, tuplet=n) # Count prime n-tuplets
countprimes(start, stop, alg = algorithm) # Count prime n-tuplets
```

The default value of start is 1. The optional keyword argument 'tuplet' may take values between 1 and 6, that is primes, through prime sextuplets. Tables are implemented only for 'tuplet' equal to one, that is for primes, but not tuplets.

The optional keyword argument alg may be one of :tabsieve (the default),
:next, :nexta, or :sieve (:sieve will always be slower than :tabsieve).
As above, `:tabsieve`

uses a combination of tables and a fast sieve.
:next and :nexta are two different variants of `next_prime`

.

Examples

```
countprimes(100,1000) # the number of primes x satisfying 100 <= x <= 1000
143
countprimes(100,tuplet=3) # the number of prime triplets between 1 and 100
8
countprimes(10,1000,tuplet=6) # the number of prime sextuplets between 100 and 1000
1
```

If you quote the arguments (either as an expression or a string), they will be converted to Int128. This prevents overflow.

```
countprimes("10^19+10^9")
234057667299198865
```

If you use BigInt's, then the method :nexta will be chosen automatically. For example

```
julia> @bigint countprimes(10^50, 10^50+1000)
7
```

### nextprime, prevprime

`nextprime(n)`

returns the smallest prime greater than n.

`prevprime(n)`

returns the largest prime less than n.

`nextprime(n,k)`

returns the kth prime following n.

`prevprime(n,k)`

returns the kth prime preceeding n.

Several algorithms are used. Finding the optimal one (of the available) is partially automated. nextprime1 and prevprime1 use an alternate algorithm coded by H W Borcher.

### Iterators

`someprimes(n2)`

All primes n, 2 <= n <= n2

`someprimes(n1,n2)`

All primes n, n1 <= n <= n2

`allprimes(n1)`

All primes n, n > n1

`allprimes()`

All primes

For example, here is the primorial function defined using an iterator:

```
julia> primorial(n) = prod(someprimes(n))
julia> @bigint primorial(100)
2305567963945518424753102147331756070
```

### nthprime()

Returns the nth prime using a fast algorithm from libprimecount. The argument is converted to Int64.

`nthprime(n; alg = :sieve)`

uses the older algorithm from
libprimesieve, which is much slower.

### nprimes

Return an array of the first `n`

primes `>= start`

.

Usage

`nprimes(n,[start=1])`

### single threaded versions

Usage

`scountprimes([start],stop, tuplets=1)`

### printprimes

Print all primes (or prime n-tuplets) that are `>= start`

and `<= stop`

Usage

`printprimes([start],stop, [tuplet=1])`

The default value of 'start' is 1. The optional keyword argument 'tuplet' may take values between 1 and 6.

### legendrephi

The legendre sum or phi function

`legendre(x,a)`

The arguments are converted to Int64.

### primeLi

The offset logarithmic integral. The argument is converted to Int64.

### PrimeLiinv

The inverse Li function. The argument is converted to Int64.

### randprime

`randprime(a,b)`

choose a random prime between `a`

and `b`

. All primes in the range
are equally likely to be chosen.

`randprime(b)`

choose a random prime between 2 and `b`

.

`randprime(a,b; lim=n)`

find a maximum of `n`

random composite numbers
before giving up.

`randprime(a,b,n1,n2,...)`

return a n1xn2x... array of random primes

### isprime(z)

Returns `true`

if the
Gaussian integer `z`

is prime.

## Sieve Parameters

### primesievesize

Get, set the sieve size in kilobytes. (setting does not seem to work)
`sz`

must satisfy `1 <= sz <= 2048`

Usage

```
primesievesize()
primesievesize(sz)
```

### primesieve_num_threads

Get, set the number of threads used in the parallel sieve. By default, the number of cores is used.

Usage

```
primesieve_num_threads()
primesieve_num_threads(numthreads)
```

### primepi_num_threads

Get, set the number of threads used in the parallel primepi. By default, the number of cores is used.

Usage

```
primepi_num_threads()
primepi_num_threads(numthreads)
```

### primemaxstop

Return the largest value (as a `Uint64`

) that can be passed as the parameter
stop in the sieve.

Usage

`primemaxstop()`

### primepi_xmax()

Function that returns the largest allowed argument to `primepi`

when using the :dr algorithm.

### primetest

Run a test of the sieve algorithm.

Usage

`primetest()`

### primepi_test

Run a test of the primepi algorithms

## Tables of prime pi function

Some of the above functions use tables, but this is completley hidden from the user. But it is also possible to access them directly. The tables work like this:

```
julia> @time countprimes(10^17 + 10^14 + 10^10)
elapsed time: 3.729049749 seconds (168 bytes allocated)
2626112053757377
```

To see what happened, we can look in the tables:

```
julia> primelookup(10^17 + 10^14 + 10^10)
(14,(2626111798288135,100100000000000000,10000000000))
```

The 14th table was used. The value of prime pi for `10^17+10^14`

,
`2626111798288135`

is in the table, and the primes in an
interval of length `10^10`

must be found with the sieves.

### primetableinfo

Print information about the prime pi tables.

```
julia> primetableinfo()
Tables of π(x). Listed are: table number, increment in x (and first value of x),
number of entries in the table, largest x in table.
table incr tab len max x
1 10^1 10^4 10^5
2 10^2 10^4 10^6
3 10^3 10^4 10^7
4 10^4 10^4 10^8
5 10^5 10^4 10^9
6 10^6 10^4 10^10
7 10^7 10^4 10^11
8 10^8 10^4 10^12
9 10^9 10^4 10^13
10 10^10 10^4 10^14
11 10^11 10^4 10^15
12 10^12 10^4 10^16
13 10^13 10^4 10^17
14 10^14 10^4 10^18
15 10^15 10^4 10^19
16 10^16 10^4 10^20
17 10^17 10^3 10^20
18 10^18 10^2 10^20
19 10^19 10^2 10^21
20 10^20 10^2 10^22
21 10^21 10^2 10^23
22 10^22 10^1 10^23
```

### primelookup

Look up a value of the prime pi function in the tables. This is only provided
to aid in understanding the behavior of `countprimes`

.

Usage

`primelookup(x)`

A tuple of a single element and another tuple of three elements is returned:

`(j,(p,y,rem))`

`j`

is the number of the best table found`y`

is the largest index satisfying`y<x`

found.`p`

is the value of prime pi at`y`

`rem`

is`x-y`

### primetables

The array of type `Array{PrimeTable,1}`

containing the prime tables.
See tables.jl for the format.

Example

`show(map(length,primetables)) # see the number of tables and their lengths`

### primetablefilename

Function returning the path to the file containing the prime pi tables. The tables are loaded when the package is loaded.

## Other details

For `x>typemax(Int)`

, you need to explicitly ask for a bigger data type.
For instance,

```
julia> countprimes(int128(10)^23)
1925320391606803968923
```

This example returned a value from the table. The argument was larger than than primemaxstop().

With any of the routines, you can quote the arguments and they will be converted to the appropriate type.

```
julia> countprimes(:(10^23))
1925320391606803968923
julia> countprimes("10^19 + 10^9")
234057667299198865
```

Routines that use the tables will convert the arguments to Int128. This is because
some indices in the tables are greater than `typemax(Uint64)`

. Routines that
only use the sieve will be converted to `Uint64`

, which is the data type that
the sieve routines use.

The largest stop value that may be given is `2^64 - 10 * 2^32`

.
The largest start value that may be given is `2^64 - 11 * 2^32`

.
The sieve works with the `Uint64`

data type. But conversions are done depending
on the types of start, stop, and n.

`countprimes`

returns `Int128`

, because it uses tables and sieves
The other routines only support smaller data types.

### primetabletype()

Return data type of tables. This should be Int128. The largest values cannot be used together with the sieve.

### primesievetype()

Return the native prime sieve type. This should be Uint64. libprimesieve
returns the data in various integer formats. These are chosen by the Julia
interface by the type of the `start`

parameter.

### eltype(t::PrimeTable)

Return element type of values in table.

## Other functions

### apopcount

This is a only curiosity. It is supposed to be an optimized C (C++) function, but doing the same thing in a Julia loop is much faster.

`apopcount(arr)`

gives the number of 1's in the binary representation of
the array `arr`

. The length of the array is truncated to a multiple of 8.

Note that this treats the contents of the array as a bits type. In
particular, if `arr`

is not an array of bits type, then the number of 1's
in the pointers in the array are counted.

In the comments, Kim Walisch says this about the algorithm,

This algorithm counts the number of 1 bits (population count) in an array using 64-bit tree merging. To the best of my knowledge this is the fastest integer arithmetic bit population count algorithm, it uses only 8 operations for 8 bytes on 64-bit CPUs

Example:

```
julia> aa = Array(Uint64,100000000);
julia> fill!(aa,typemax(Uint64));
julia> @time apopcount(aa)
elapsed time: 0.140950344 seconds (96 bytes allocated) # test shows overhead is negligible
6400000000
julia> lpopcount(x) = ( s = 0; for i in 1:length(x) s += count_ones(x[i]) end; s)
julia> @time lpopcount(aa)
elapsed time: 0.106306266 seconds (96 bytes allocated) # Julia version is faster !
6400000000
```

The algorithm is by Cédric Lauradoux

### Notes

The algorithms used by `:auto`

in `genprimes`

and `primepi`

are
simple and do not always choose the best method. They could be improved.
However, the routines are still fast. In the worst case, `genprimes`

is more than an order of magnitude faster than `Base.primes`

.

### Bugs

Interrupting a call to the sieves usually does not cause a memory error. But, libprimesieve apparently has some static state, such that, after the interrupt, subsequent sieving runs much slower, and may not give correct results.

Interrupting a call to libprimecount, results in a segfault. We could
`disable_sigint`

, but there appear to be memory leaks in libprimecount.
Better to crash Julia than the whole system.

msieve interrupt handler is installed, then all c code uses it. We need to install and then uninstall it on every call.