素因数分解(PrimeDecomposition)

PrimeDecomposition.cs

using System;
using System.Collections.Generic;

namespace PrimeDecomposition
{
    public static class PrimeDecomposition
    {
        public static List<int> DoPrimeDecomposition(int num)
        {
            List<int> primaryFactors = new List<int>();
            
            //iを奇数だけとか、素数の必要条件で限定すればより効率がよくなる
            for (int i = 2; i <= Math.Sqrt(num); i++)
            {
                while (num % i == 0)
                {
                    primaryFactors.Add(i);
                    num = num / i;
                }
            }
            primaryFactors.Add(num);

            return primaryFactors;
        }
    }
}