Prime Factoring

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PrimeFactoring {
  class Program {
    static void Main (string[] args) {
      while (true) {
        Solve(int.Parse(Console.ReadLine()));
      }
    }

    private static void Solve (int the_number) {
      List<int> answers = new List<int>();
      int remaining = the_number;
      int prime = GetFirstPrime();
      while (remaining > 1) {
        if (remaining % prime != 0) {
          prime = NextPrime(prime);
          continue;
        }
        remaining /= prime;
        answers.Add(prime);
      }

      StringBuilder result = new StringBuilder();
      result.AppendFormat("prime factoring of {0} is ", the_number);
      result.Append(string.Join(" * ", answers.ToArray()));
      Console.WriteLine(result.ToString());
    }

    private static int GetFirstPrime () {
      return cached_primes.First();
    }

    private static int NextPrime (int current_prime) {
      if (cached_primes.Last() == current_prime) {
        int candidate = current_prime;
        do {
          candidate += 2;
        } while(!IsPrime(candidate));
        cached_primes.Add(candidate);
      }
      return cached_primes.First(n => n > current_prime);
    }

    private static bool IsPrime (int prime) {
      for(int i = 2; i < prime; ++i) {
        if (prime % i == 0) {
          return false;
        }
      }
      return true;
    }

    private static List<int> cached_primes = new List<int>() { 2, 3 };
  }
}