PrimeFactorization

A fast and efficient Elixir library for prime factorization of integers.

Features

• Efficient Implementation: Uses optimized trial division algorithm with early termination
• Type Safety: Full type specifications for all functions
• Comprehensive Testing: Extensive test coverage with doctests
• Code Quality: Follows Elixir best practices with Credo, Dialyzer, and SpellWeaver
• Well Documented: Complete documentation with examples and performance notes

Installation

Add prime_factorization to your list of dependencies in mix.exs:

def deps do
  [
    {:prime_factorization, "~> 1.0"}
  ]
end

Then install dependencies:

mix deps.get

Usage

Basic Prime Factorization

# Factorize a simple number
PrimeFactorization.of(12)
# Returns: [2, 2, 3]

# Factorize a prime number
PrimeFactorization.of(17)
# Returns: [17]

# Factorize a larger number
PrimeFactorization.of(100)
# Returns: [2, 2, 5, 5]

# Edge case: factorize 1
PrimeFactorization.of(1)
# Returns: []

Working with Prime Numbers

# Check if a number is prime (has only one factor and it's the number itself)
def is_prime?(n) when n > 1 do
  factors = PrimeFactorization.of(n)
  length(factors) == 1 and hd(factors) == n
end

# Examples
is_prime?(17)  # true
is_prime?(12)  # false

Finding Unique Prime Factors

# Get unique prime factors
def unique_prime_factors(n) do
  PrimeFactorization.of(n)
  |> Enum.uniq()
end

# Examples
unique_prime_factors(12)  # [2, 3]
unique_prime_factors(100) # [2, 5]

Using the Trial Division Function Directly

# Use the specific trial division implementation
PrimeFactorization.trial_division(12)
# Returns: [2, 2, 3]

Performance

• Time Complexity: O(√n) in the worst case
• Memory: Constant space usage due to tail recursion
• Interactive Use: Up to approximately 10^10
• Batch Processing: Up to approximately 10^12

Practical Performance Guidelines

• 10^6: Very fast (< 1 second)
• 10^8: Fast (seconds)
• 10^10: Moderate (minutes) - recommended interactive limit
• 10^12: Slow (hours) - batch processing limit
• 10^14: Very slow (days) - not recommended

For larger numbers, consider more sophisticated algorithms like:

• Pollard's rho algorithm
• Quadratic sieve
• General number field sieve

License

Copyright (c) 2025 University of Kitakyushu

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Changelog

See CHANGELOG.md for a list of changes and version history.