Move History

Rooted by: Prime Factorization
Fork Selected
  • Code 
    using System.Collections.Generic;
using System.Linq;

//using FactorSort = (int PrimeFactor, int Exponent);

public static class PrimeFactorization
{
    public static IList<(int PrimeFactor, int Exponent)> Factorize(int number)
    {
        List<(int PrimeFactor, int Exponent)> factors = new()
        {
            DetermineFrequency(ref number, 2)
        };
        for (int i = 3; i*i <= number; i += 2)
            factors.Add(DetermineFrequency(ref number, i));
        if (number > 1) factors.Add((number, 1));
        factors.RemoveAll(f => f.Exponent == 0);
        return factors;
    }

    private static (int PrimeFactor, int Exponent) DetermineFrequency(ref int number, int factor)
    {
        var exponent = 0;
        while (number % factor == 0)
        {
            exponent++;
            number /= factor;
        }
        return (factor, exponent);
    }
}
     Test Cases 
    using NUnit.Framework;
using System.Collections.Generic;

namespace Testing;

[TestFixture]
public class PrimeFactorizationTest
{
    private List<(int input, List<(int PrimeFactor, int Exponent)> expectedOutput)> _testCases = new()
    {
        (84, new() { (2, 2), (3, 1), (7, 1) }),
        (100, new() { (2, 2), (5, 2) }),
        (79, new() { (79, 1) }),
        (13195, new() { (5, 1), (7, 1), (13, 1), (29, 1) }),
        (30030, new() { (2, 1), (3, 1), (5, 1), (7, 1), (11, 1), (13, 1) })
    };

    [Test]
    public void Test()
    {
        foreach (var testCase in _testCases)
        {
            Assert.That(PrimeFactorization.Factorize(testCase.input), Is.EqualTo(testCase.expectedOutput));
        }
    }
}
    View Run Output
  • Code
    • using System.Collections.Generic;
    • using System.Linq;
    • //using FactorSort = (int PrimeFactor, int Exponent);
    • public static class PrimeFactorization
    • {
    • public static IEnumerable<(int PrimeFactor, int Exponent)> Factorize(int number)
    • public static IList<(int PrimeFactor, int Exponent)> Factorize(int number)
    • {
    • List<(int PrimeFactor, int Exponent)> factors = new()
    • {
    • DetermineFrequency(ref number, 2)
    • };
    • for (int i = 3; i*i <= number; i += 2)
    • factors.Add(DetermineFrequency(ref number, i));
    • if (number > 1) factors.Add((number, 1));
    • factors.RemoveAll(f => f.Exponent == 0);
    • return factors;
    • }
    • private static (int PrimeFactor, int Exponent) DetermineFrequency(ref int number, int factor)
    • {
    • SortedDictionary<int, int> factors = new(); //[];
    • for (int i = 2; i <= number / 2 + 1; i++)
    • var exponent = 0;
    • while (number % factor == 0)
    • {
    • while (number % i == 0)
    • {
    • factors[i] = factors.GetValueOrDefault(i, 0) + 1;
    • number /= i;
    • }
    • exponent++;
    • number /= factor;
    • }
    • if (number > 1) factors[number] = factors.GetValueOrDefault(number, 0) + 1;
    • return from factor in factors select (factor.Key, factor.Value);
    • return (factor, exponent);
    • }
    • }
     Test Cases
    • using NUnit.Framework;
    • using System.Collections.Generic;
    • namespace Testing;
    • [TestFixture]
    • public class PrimeFactorizationTest
    • {
    • private List<(int input, List<(int PrimeFactor, int Exponent)> expectedOutput)> _testCases = new()
    • {
    • (84, new() { (2, 2), (3, 1), (7, 1) }),
    • (100, new() { (2, 2), (5, 2) }),
    • (79, new() { (79, 1) }),
    • (13195, new() { (5, 1), (7, 1), (13, 1), (29, 1) }),
    • (30030, new() { (2, 1), (3, 1), (5, 1), (7, 1), (11, 1), (13, 1) })
    • };
    • // [
    • // (84, [(2, 2), (3, 1), (7, 1)]),
    • // (100, [(2, 2), (5, 2)]),
    • // (79, [(79, 1)]),
    • // (13195, [(5, 1), (7, 1), (13, 1), (29, 1)]),
    • // (30030, [(2, 1), (3, 1), (5, 1), (7, 1), (11, 1), (13, 1)])
    • // ];
    • [Test]
    • public void Test()
    • {
    • foreach (var testCase in _testCases)
    • {
    • Assert.That(PrimeFactorization.Factorize(testCase.input), Is.EqualTo(testCase.expectedOutput));
    • }
    • }
    • }