PrimeFactorization (Prime factorization v1.1.0)

A library for prime factorization of integers using efficient algorithms.

This module provides functions to decompose integers into their prime factors. The implementation uses the trial division algorithm, which is efficient for small to medium-sized integers.

Examples

iex> PrimeFactorization.of(12)
[2, 2, 3]

iex> PrimeFactorization.of(17)
[17]

iex> PrimeFactorization.of(100)
[2, 2, 5, 5]

Summary

Functions

of(integer)

Decomposes a positive integer into its prime factors.

trial_division(integer)

Decomposes a positive integer into its prime factors using trial division.

Functions

of(integer)

@spec of(pos_integer()) :: [pos_integer()]

Decomposes a positive integer into its prime factors.

Returns a list of prime factors in ascending order. For prime numbers, the result will be a single-element list containing the number itself. For 1, returns an empty list.

Parameters

  • integer - A positive integer to factorize

Returns

  • list(pos_integer()) - List of prime factors in ascending order

Examples

iex> PrimeFactorization.of(1)
[]

iex> PrimeFactorization.of(2)
[2]

iex> PrimeFactorization.of(12)
[2, 2, 3]

iex> PrimeFactorization.of(17)
[17]

iex> PrimeFactorization.of(100)
[2, 2, 5, 5]

iex> PrimeFactorization.of(2_147_483_647)
[2_147_483_647]

trial_division(integer)

@spec trial_division(pos_integer()) :: [pos_integer()]

Decomposes a positive integer into its prime factors using trial division.

Returns a list of prime factors in ascending order. For prime numbers, the result will be a single-element list containing the number itself. For 1, returns an empty list.

Parameters

  • integer - A positive integer to factorize

Returns

  • list(pos_integer()) - List of prime factors in ascending order

Examples

iex> PrimeFactorization.trial_division(1)
[]

iex> PrimeFactorization.trial_division(2)
[2]

iex> PrimeFactorization.trial_division(12)
[2, 2, 3]

iex> PrimeFactorization.trial_division(17)
[17]

iex> PrimeFactorization.trial_division(100)
[2, 2, 5, 5]

iex> PrimeFactorization.trial_division(2_147_483_647)
[2_147_483_647]

Performance

The trial division algorithm has a time complexity of O($\sqrt{n}$) in the worst case, making it suitable for integers up to approximately $10^{10}$ for interactive use and $10^{12}$ for batch processing. For larger numbers, more sophisticated algorithms like Pollard's rho or the quadratic sieve would be more appropriate.

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

Notes

  • The function uses the LehmerGcd library for efficient GCD calculations
  • Factors are returned in ascending order for consistency
  • The implementation is optimized with early termination conditions