Re: Confusing performance results for prime

From: Greg Brunet (gregbrunet_at_NOSPAMsempersoft.com)
Date: 10/19/03 

Date: Sat, 18 Oct 2003 19:08:35 -0500

"Lulu of the Lotus-Eaters" <mertz@gnosis.cx> wrote in message
news:mailman.188.1066456959.2192.python-list@python.org...
> bokr@oz.net (Bengt Richter) wrote previously:
> |In doing some testing of different but simple algorithms for getting
a
> |list of prime numbers
>
> This general topic came up quite recently. I myself wrote a bunch
about
> various data structures to cache primes and the like. But that was
all
> fairly idle.
>
> If you want to test primality quickly, using the sieve of erotosthenes
> is pretty terrible. At least if you only want to check relatively few
> numbers, rather than assemble all the primes. Orders of magnitude
> better is to use Miller-Rabin pseudoprimality tests (well, complexity
> orders really).
>
> Pick the right algorithm before worrying about micro-optimizations.

Well, actually I was trying to get the list of primes (as well as a
count of them) below a specified value - so perhaps the sieve is the
better algorithm to use. I also was just testing simple, easy to
understand algorithms. Finally, the question was really more about
understanding the cause of the behavior I was seeing after making the
changes. I think that has been acheived. Thanks, 

-- 
Greg

Relevant Pages

  • Re: SF: Back to theory
    ... >> f and g are generated exactly the same way in the algorithms that try ... Let T = the product of the primes in S. ... variety of prime factors, this one stuffs a variety of primes into T ... algorithm beat random-gcd 456 of 561 factoring cases ...
    (sci.math)
  • Re: Factoring problem and the SFT
    ... you and Nora _both_ lying to James about this, ... of 20-bit primes, and toward the end cut that to 15-bit primes as the ... algorithms got ever more expensive to try). ... The set of all integers divisible by 101 is infinite. ...
    (sci.math)
  • Re: SF: Back to theory
    ... >> f and g are generated exactly the same way in the algorithms that try ... Let T = the product of the primes in S. ... variety of prime factors, this one stuffs a variety of primes into T ... algorithm beat random-gcd 456 of 561 factoring cases ...
    (sci.crypt)
  • Re: Confusing performance results for prime
    ... bokr@oz.net (Bengt Richter) wrote previously: ... various data structures to cache primes and the like. ... better is to use Miller-Rabin pseudoprimality tests (well, ...
    (comp.lang.python)
  • Re: SF: Any other research out there?
    ... > couldn't afford to pay for the kinds of verification, ... You knowingly posted incorrect algorithms. ... Well, knowing the value of A is provably unimportant, and that doesn't ... even bigger primes depending on special circumstances. ...
    (sci.crypt)