This algorithm runs pretty fast - try 4567891 and 123997277251 (~35 sec on 150Mhz)
Is prime?
About the algorithm