search

gorakhargosh / mom

The do-not-repeat-yourself-library. All your utils.py and compat.py are belong to us. Python 2.5+, PyPy, and Python 3.x
Apache License 2.0
39 stars 8 forks source link

mom.math.is_prime #2

Open rubik opened 13 years ago

rubik commented 13 years ago

is_prime returns True for 1. You should fix that.

Thanks, rubik

gorakhargosh commented 13 years ago

Heh. Yep. Haven't tested that routine yet. Soon soon. =)

Cheers.

rubik commented 13 years ago

Ok. Are you planning to add tests?

gorakhargosh commented 13 years ago

Yep. Only 4 modules in the library don't have tests yet. The rest already have 100% coverage.

mom/init 6 0 0 100% mom/codec/init 59 0 0 100% mom/functional 83 0 0 100% mom/security/init 3 0 0 100% mom/security/codec/init 21 0 0 100% mom/security/codec/asn1/init 3 0 0 100% mom/security/codec/asn1/rsadsa 15 0 0 100% mom/security/codec/asn1/x509 39 0 0 100% mom/security/codec/pem/init 38 0 0 100% mom/security/hash 30 0 0 100% mom/builtins 108 2 0 98% mom/security/codec/pem/rsa 66 8 0 88% mom/security/codec/pem/x509 48 6 0 88% mom/security/random 60 15 0 75% mom/_builtins 24 9 0 63% mom/decorators 10 4 0 60% mom/codec/json 34 18 0 47%

^ 100% coverage. Ignore the stats shown. They're because of compatibility imports.

Pending: mom/math 122 93 0 24% mom/_types/init 3 3 0 0% mom/_types/bytearray 49 49 0 0% mom/itertools 102 102 0 0% mom/security/rsa/init 26 26 0 0% mom/security/rsa/keys 43 43 0 0% mom/security/rsa/pycrypto 32 32 0 0%

So, yep. Writing tests right now. =)

rubik commented 13 years ago

Ok! :) I have noticed that sometimes mom.math.make_prime_sieve gives wrong results:

In [2]: filter(lambda n: not mom.math.is_prime(n), mom.math.make_prime_sieve(10))
Out[2]: [9]
In [3]: filter(lambda n: not mom.math.is_prime(n), mom.math.make_prime_sieve(100))
Out[3]: []
In [4]: filter(lambda n: not mom.math.is_prime(n), mom.math.make_prime_sieve(1000))
Out[4]: [961]
In [5]: filter(lambda n: not mom.math.is_prime(n), mom.math.make_prime_sieve(10000))
Out[5]: []
gorakhargosh commented 13 years ago

You're welcome to rewrite the routine. This one comes from tlslite. I've rewritten almost everything I've imported from scratch because of these problems. tlslite doesn't have a battery of tests, so... =)

rubik commented 13 years ago

Oh no, it wouldn't be fast enough! On stackoverflow I saw an optimized sieve, I only have to find it.

EDIT: Here it is!

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

It comes from this discussion: http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-pythonù It is very fast: it can compute primes up to 10 million within a second! And it uses half the list!

gorakhargosh commented 13 years ago

Awesome!

rubik commented 13 years ago

Yes it is! :)