Re: [PrimeNumbers] Re: NewPGen Sieve Algorithm ?
- Mohsen wrote:
> I have read somewhere that NewPGen uses BSBG (Baby Step Giant Step)!You can Google Baby Step Giant Step. It's an algorithm for discrete
> Anybody knows? Although NewPGen is a native app vs Mathematica as
> being managed and under JVM overhead, but I should be able to sieve not
> faster but at least equal to NewPGen. Please help me.
logarithms. It's used for "fixed k sieves", i.e forms like k*2^n+/-1 where
k is fixed and n varies. This is very different from arithmetic progressions
like k*n#+/-1 where n is fixed and k varies.
You have unrealistic expectations about the efficiency of Mathematica.
It has a lot of functions and makes it easy to program many problems
but it's not particularly fast, at least not for the operations needed to
The 5000 largest known primes at http://primes.utm.edu/primes/ were
found with a variety of sieves, prp testers and primality provers, but
I haven't heard of anyone who used Mathematica for any of the steps.
Jens Kruse Andersen