# 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`:

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

Then install dependencies:

```bash
mix deps.get
```

## Usage

### Basic Prime Factorization

```elixir
# 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

```elixir
# 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

```elixir
# 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

```elixir
# 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](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](CHANGELOG.md) for a list of changes and version history.