PrimeFactorize method for int

I have written this PrimeFactorize utility method in C# (using LINQPad) which works fine, but feels like it is a bit slow, I was wondering what might be improved. Also looking for any criticism not related to efficiency to make the code better.

// Generate prime factors for a number, e.g., input 12 returns 2 2 3
public static IEnumerable PrimeFactorize(int number)
{
if(IntUtils.IsPrime(number))
{
yield return number;
}
else
{
List primes = IntUtils.GetPrimesBetween(2, number);
while(!IntUtils.IsPrime(number))
{
foreach(var p in primes)
{
if(number % p == 0)
{
yield return p;
number /= p;
break;
}
}
}
yield return number;
}
}


As a note, the IntUtils.IsPrime and IntUtils.GetPrimesBetween are two other utility methods I wrote. I am including GetPrimesBetween below. IsPrime has already been reviewed and it is quite fast by itself and can be found on GitHub.

public static List GetPrimesBetween(int min, int max)
{
var primes = new List();
for(var i = min; i

Here is a test run, along with the execution times:

void Main()
{
var N = 12;
for(var i = 1; i

Results:

`Run # 1 | Number to factorize: 12
Result: 2 2 3
Time elapsed since start: 00:00:00.0130129
Run # 2 | Number to factorize: 49
Result: 7 7
Time elapsed since start: 00:00:00.0132697
Run # 3 | Number to factorize: 198
Result: 2 3 3 11
Time elapsed since start: 00:00:00.0133637
Run # 4 | Number to factorize: 795
Result: 3 5 53
Time elapsed since start: 00:00:00.0139543
Run # 5 | Number to factorize: 3184
Result: 2 2 2 2 199
Time elapsed since start: 00:00:00.0183778
Run # 6 | Number to factorize: 12741
Result: 3 31 137
Time elapsed since start: 00:00:00.0528457
Run # 7 | Number to factorize: 50970
Result: 2 3 5 1699
Time elapsed since start: 00:00:00

First of all, the PrimeFactorize() does never terminate for number = 1
because the check IntUtils.IsPrime(number) will never return true.
The call PrimeFactorize(1) should return an empty list.

To compare the performance of various implementations, I used the following simple
test program which computes all prime factors of the numbers up to 10,000. The sum
is calculated to prevent the compiler from removing function calls whose result is
not used, and to verify that all implementations give the same results.

using System.Diagnostics; // for StopWatch

public static void Main()
{
    Stopwatch stopWatch = Stopwatch.StartNew();
    var sum = 0;
    for(var N = 2; N <= 10000; N++) 
    {
        foreach(var P in IntUtils.PrimeFactorize(N))
        {
            sum += P;
        }
    }
    stopWatch.Stop();
    Console.WriteLine("Sum: {0}, Time: {1} ms", sum, stopWatch.Elapsed.TotalMilliseconds);
}

The tests were done on a MacBook, using
Mono.

For your code, the result is

Sum: 10243046, Time: 2945.7256 ms

Your code creates a list of primes in order to find the lowest factor of the given number,
and the GetPrimesBetween() function seems be the performance bottleneck.

The IsPrime() function can be improved slightly. Since divisibility by 2, 3, 5 is
checked upfront, the loop can start with i = 7. Inside the loop, divisibility by
both i and i+2 is checked, so that the next possible divisor is i+4. Therefore
the loop should be

// iterate with trial division
    int i = 7;
    while (i * i <= n)
    {
        if (n % i == 0 || n % (i + 2) == 0)
        {
            return false;
        }
        i += 4;
    }

This reduces the execution time to

Sum: 10243046, Time: 1193.3498 ms

To improve the PrimeFactorize() function, note that every composite number \$ n \$ necessarily
has a factor \$ p \le \sqrt n \$. Also, if a factor is found,
you can repeatedly check that factor instead of breaking out of the
loop and starting with the first prime again.

This leads to the following implementation:

public static IEnumerable PrimeFactorize(int number)
{
    List primes = IntUtils.GetPrimesBetween(2, (int)Math.Sqrt(number));            
    foreach (var p in primes)
    {
        while (number % p == 0)
        {
            yield return p;
            number /= p;
        }
    }
    // Now either number == 1 or number is a prime:
    if (number > 1) {
        yield return number;
    }
}

which reduces the execution time considerably:

Sum: 10243046, Time: 15.6476 ms

A faster way to determine all prime numbers in a given range are sieving methods.
A simple implementation of the sieve of Eratosthenes is
(taken from https://codereview.stackexchange.com/a/62158/35991, but
as an enumerator):

public static IEnumerableGetPrimesUpto(int number) {
    bool[] isComposite = new bool[number + 1];
    for (int x = 2; x <= number; x++)
    {
        if (!isComposite[x])
        {
            yield return x;
            for (int y = x * x; y <= number; y = y + x)
            {
                isComposite[y] = true;
            }
        }
    }
}

which can then be used as:

public static IEnumerable PrimeFactorize(int number)
{
    var primes = IntUtils.GetPrimesUpto((int)Math.Sqrt(number));            
    foreach(var p in primes)
    {
        while (number % p == 0)
        {
            yield return p;
            number /= p;
        }
    }
    if (number > 1) {
        yield return number;
    }
}

Execution time:

Sum: 10243046, Time: 9.6804 ms

But actually you don't need to compute a list of primes first
(and I am essentially repeating the arguments from https://codereview.stackexchange.com/a/64795/35991).

The smallest factor of a number is necessarily a prime. You already
divide the number by any factor found, but this means that the lowest
factor of the updated number is again a prime. So by repeatedly
searching for the lowest factor you'll find all prime factors without
doing any extra test for primality.

Again it suffices to check for factors up
to the square root of the (remaining) number. After that, number is
either equal to one or a prime.

This leads to the following function:

// Generate prime factors for a number, e.g., input 12 returns 2 2 3
public static IEnumerable PrimeFactorize(int number)
{
    // Check divisibility by 2:
    while (number % 2 == 0) {
        yield return 2;
        number /= 2;
    }
    // Check divisibility by 3, 5, 7, ...
    for (var i = 3; i * i  1) {
        yield return number;
    }
}

Execution time:

Sum: 10243046, Time: 2.6631 ms

(C# is not my primary language, but I hope that the code demonstrates the idea.)

StackExchange Code Review Q#134394, answer score: 12