Prime number functions

factor(n::Integer) -> 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) # == 2^2 * 5^2
Dict{Int64,Int64} with 2 entries:
  2 => 2
  5 => 2

For convenience, a negative number n is factored as -1*(-n) (i.e. -1 is considered to be a factor), and 0 is factored as 0^1:

julia> factor(-9) # == -1 * 3^2
Dict{Int64,Int64} with 2 entries:
  -1 => 1
   3 => 2

julia> factor(0)
Dict{Int64,Int64} with 1 entries:
  0 => 1

factor(ContainerType, n::Integer) -> ContainerType

Return the factorization of n stored in a ContainerType, which must be a subtype of Associative or AbstractArray, a Set, or an IntSet.

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

julia> prod(factor(Vector, 100)) == 100
true

When ContainerType == Set, this returns the distinct prime factors as a set.

julia> factor(Set, 100)
Set([2,5])

primes([lo,] hi)

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

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

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.