14. Unique prime factors

One obvious way to find a number's unique prime factors is to find all of its prime factors and then remove duplicates. That would be relatively straightforward and fast.

An alternative strategy would be to modify the code that factors numbers so that it only saves one copy of each prime factor. The following method takes this approach:

// Find a number's unique prime factors.
private List<long> FindUniquePrimeFactors(long number)
{
    checked
    {
        List<long> factors = new List<long>();

        // Pull out 2s.
        if (number % 2 == 0)
        {
            factors.Add(2);
            while (number % 2 == 0) number /= 2;
        }

        // Pull out odd factors.
        long limit = (long)Math.Sqrt(number);
        for (long factor = 3; factor <= limit; factor += 2)
        {
            if (number % factor == 0)
            {
                factors.Add(factor);
                while (number % factor == 0)
                {
                    number /= factor;
                    limit = (long)Math.Sqrt(number);
                }
            }
        }

        // Add the leftover.
        if (number != 1) factors.Add(number);
        return factors;
    }
}

This method is similar to the one used in the preceding solution, except it only keeps one copy of each prime factor.

Like the preceding solution, you can make this solution faster if you build a prefilled list of prime numbers to use when searching for factors.

The lesson to be learned here is that you can sometimes solve a new problem by reusing an existing solution, but sometimes it's worth modifying the existing solution to make the new approach simpler.

Download the UniquePrimeFactors example solution to see additional details.