by alex
16. February 2009 20:48
I've being intrigued to find fast algorithms for the prime numbers and the latest advances in this field, because, as you probably know, this is the problem which can be solved using several algorithms known since old times. Despite some shortcuts and several very huge numbers proved to be primes such as Mersenne's Numbers (GIMPS), several other algorithms include Rabin-Miller which is a standard primality test, ancient Sieve of Eratosthenes, and a bit faster Sieve of Atkin. The running time of these algorithms is a logarithmic function, where the Sieve of Atkin FFT implementation computes the result in O(k × log2 n). In reality, if you try to find the prime numbers on the latest computer hardware, it still takes a considerable amount of time and the problem is a good candidate for parallelization.