Trial Division Factorizer Algorithm
The Trial Division Factorizer Algorithm is a simple, yet fundamental method for finding the prime factors of a given integer. It is based on the principle of division, where the algorithm iteratively divides the input number by a sequence of integers, starting from the smallest prime number (2) and increasing until the square root of the input number is reached. When a division results in an exact whole number, the divisor is identified as a prime factor, and the process is repeated with the quotient obtained until the quotient itself is a prime number. At this point, all the prime factors of the given integer have been identified.
While the Trial Division Factorization Algorithm is easy to understand and implement, it is not the most efficient method for factoring large numbers. The algorithm's time complexity is proportional to the square root of the input number, which means that as the input number increases, the time it takes to factorize it grows exponentially. This makes it impractical for use in cryptographic applications where large prime factors are involved, such as RSA encryption. However, the algorithm's simplicity makes it a good starting point for understanding the basics of number theory and prime factorization, and it can still be effectively used for small-scale calculations and educational purposes.
using System;
using System.Linq;
namespace Algorithms.Numeric.Factorization
{
/// <summary>
/// Factors number using trial division algorithm.
/// </summary>
public class TrialDivisionFactorizer : IFactorizer
{
/// <summary>
/// Finds a factor of a given number or returns false if it's prime.
/// </summary>
/// <param name="n">Integer to factor.</param>s
/// <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;
}
}
}