Mainly Tech projects on Python and Electronic Design Automation.

Friday, February 21, 2014

Almost primes (with a StopIteration twist)

I just created the Almost primes task on Rosetta Code:
A k-Almost-prime number is a natural number n, that is the exact multiple of k primes.
So, for example if k is 1, then this is the series of prime numbers themselves. If k is 2 then this is the series of semiprimes.
The task is to write a function/method/subroutine/... that generates k-almost primes and use it to create a table of the first ten members of k-Almost primes for 1 < = K < = 5
A curious thing about its Python code is that I had to introduce a name terms for a partial result:


from prime_decomposition import decompose
from itertools import islice, count
try: 
    from functools import reduce
except: 
    pass
 
 
def almostprime(n, k=2):
    d = decompose(n)
    try:
        terms = [d.next() for i in range(k)]
        return reduce(int.__mul__, terms, 1) == n
    except:
        return False
 
if __name__ == '__main__':
    for k in range(1,6):
        print('%i: %r' % (k, list(islice((n for n in count() if almostprime(n, k)), 10))))

Output:

1: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
2: [4, 6, 9, 10, 14, 15, 21, 22, 25, 26]
3: [8, 12, 18, 20, 27, 28, 30, 42, 44, 45]
4: [16, 24, 36, 40, 54, 56, 60, 81, 84, 88]
5: [32, 48, 72, 80, 108, 112, 120, 162, 168, 176]

StopIteration swallowing

The following will not work as any StopIteration exception raised by trying to pull more prime decomposition values from the decompose operator will just stop the iterator when we need the exception to propagate to the except clause and so return False:

        return reduce(int.__mul__, 
                      (d.next() for i in range(k)), 1) == n


END.

1 comment:

  1. So, you should just stop monkeying around and use islice like the normal folks. :-)

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive