Yo publico uno hace tiempo, mejore el código como por un año investigando bastante me obsesiono por un tiempo este tema y en verdad va bastante rápido, claro hay números que por alguna razón matemática que aun no entiendo tardan demasiado, como por ejemplo 444445555511122222 o de ese tipo.

http://foro.elhacker.net/net/aporte_factorizacion_a_maxima_velocidad_actualizado_21102011-t321927.0.html

Normalmente siempre se recorren los números de 0 a N para hallar si un número es primo, eso serían N operaciones para cualquier N, si N es 100 mil millones entonces 100 mil millones serán las operaciones necesarias, a eso se debe la demora, sin embargo hay muchos métodos para acortar el tiempo, todos los que pude descubrir están aplicados en ese ejemplo, en tu código aplicas varios, como comenzar desde el 3, porque se sabe que el 2 es primo y el 1 no, avanzar de 2 en 2, porque sabemos que ningún primo es par, además de estos hay otros importantes como por ejemplo ningun número que se presume compuesto tiene más de un factor primo que supere su raíz por el simple hecho de que si F1 es una factor de N y es mayor que la raíz de N, N no puede tener 2 F1 de factores por que superarían a N, en otras palabras 2*F1>N, otros varios están explicados en esa publicación, nada más estos 3 disminuyen la cantidad de operaciones en

RaízCuadrada(N-3/2) en vez de N operaciones.

Como sea al menos hasta ahora no existe un método para factorizar en primos números grandes de una manera rápida, si alguien lo logra o lo matan o la seguridad informática debe volver a plantearse desde el principio

La tomare mucho en cuenta si la llegase a necesitar, voy a descargarla ahora, Gracias por compartirla hay una página WolframAlpha que también resuelve cualquier cosa, ofrece una API pero es paga

Para usar Regex debes importar System.Text.RegularExpressions.

Mi código será siempre más lento, porque está en .Net y porque así como he agregado muchas cosas también faltaran otras, pero es solo practica lo que buscaba era entender la teoría de los problemas y las ventajas de factorizar un número que se supone compuesto en sus primos .

Regex es la clase en .Net que controla las expresiones regulares, que son un lenguaje de programación descriptivo para capturar patrones en textos, Es un tema muy extenso, por medio de instrucciones que describen patrones un motor de búsqueda realiza las operaciones necesarias para capturar en el texto que desees si el patrón existe o no.

http://es.wikipedia.org/wiki/Expresi%C3%B3n_regular
http://www.elguille.info/regexp/indice.aspx
http://msdn.microsoft.com/es-es/library/hs600312%28v=vs.80%29.aspx