The Algorithms logo
The Algorithms
AboutDonate

Trial division Factorization

using System;
using System.Linq;

namespace Algorithms.Numeric.Factorization;

/// <summary>
///     Factors number using trial division algorithm.
/// </summary>
public class TrialDivisionFactorizer : IFactorizer
{
    /// <summary>
    ///     Finds the smallest non trivial factor (i.e.: 1 &lt; factor &lt;= sqrt(<paramref name="n" />)) of a given number or returns false if it's prime.
    /// </summary>
    /// <param name="n">Integer to factor.</param>
    /// <param name="factor">Found factor.</param>
    /// <returns><see langword="true" /> if factor is found, <see langword="false" /> if <paramref name="n" /> is prime.</returns>
    public bool TryFactor(int n, out int factor)
    {
        n = Math.Abs(n);
        factor = Enumerable.Range(2, (int)Math.Sqrt(n) - 1).FirstOrDefault(i => n % i == 0);
        return factor != 0;
    }
}