Julia functions for computing prime numbers.

This repository contains some functions relating to prime numbers which have been duplicated from Base Julia, as well as new functions and improvements.

factor(n) -> Dict

Compute the prime factorization of an integer n. Returns a dictionary. The keys of the dictionary correspond to the factors, and hence are of the same type as n. The value associated with each key indicates the number of times the factor appears in the factorization.

julia> factor(100) # == 225*5 Dict{Int64,Int64} with 2 entries: 2 => 2 5 => 2

factor(ContainerType, n) -> ContainerType

Return the factorization of n using ContainerType (a subtype of Associative or AbstractArray).

julia> factor(DataStructures.SortedDict, 100) DataStructures.SortedDict{Int64,Int64,Base.Order.ForwardOrdering} with 2 entries: 2 => 2 5 => 2

When ContainerType <: AbstractArray, this returns the list of all prime factors of n with multiplicities, in sorted order.

julia> factor(Vector, 100) 4-element Array{Int64,1}: 2 2 5 5

isprime(x::Integer) -> Bool

Returns true if x is prime, and false otherwise.

julia> isprime(3) true

isprime(x::BigInt, [reps = 25]) -> Bool

Probabilistic primality test. Returns true if x is prime with high probability (pseudoprime); and false if x is composite (not prime). The false positive rate is about 0.25^reps. reps = 25 is considered safe for cryptographic applications (Knuth, Seminumerical Algorithms).

julia> isprime(big(3)) true

primes([lo,] hi)

Returns a collection of the prime numbers (from lo, if specified) up to hi.

primesmask([lo,] hi)

Returns a prime sieve, as a BitArray, of the positive integers (from lo, if specified) up to hi. Useful when working with either primes or composite numbers.

To avoid naming conflicts with Base, these are not exported for Julia version 0.4. In this case you will need to explicitly import the symbols:

using Primes
import Primes: isprime, primes, primesmask, factor