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.

Semiprimes in Python

Someone added a Semiprime task to Rosetta Code:

    > Semiprime numbers are natural numbers that are products of exactly two (possibly equal) prime numbers. 

    > Example: 1679 = 23 × 73 (This particular number was chosen as the length of the Arecibo message). 

    > Write a function determining whether a given number is semiprime.

I first looked for a prime generator and found one in part of an existing Prime decomposition tasks example code, where decompose is a generator for the prime factors of its argument.

In [ ]:

from __future__ import print_function

import sys
 
def is_prime(n):
    return zip((True, False), decompose(n))[-1][0]
 
class IsPrimeCached(dict):
    def __missing__(self, n):
        r = is_prime(n)
        self[n] = r
        return r
 
is_prime_cached = IsPrimeCached()
 
def primes():
    yield 2
    n = 3
    while n < sys.maxint - 2:
        yield n
        n += 2
        while n < sys.maxint - 2 and not is_prime_cached[n]:
            n += 2
 
def decompose(n):
    for p in primes():
        if p*p > n: break
        while n % p == 0:
            yield p
            n /=p
    if n > 1:
        yield n
 
if __name__ == '__main__':
    # Example: calculate factors of Mersenne numbers to M59 #
 
    import time
 
    for m in primes():
        p = 2 ** m - 1
        print( "2**{0:d}-1 = {0:d}, with factors:".format(m, p) )
        start = time.time()
        for factor in decompose(p):
            print (factor, end=' ')
            sys.stdout.flush()
 
        print( "=> {0:.2f}s".format( time.time()-start ) )
        if m >= 59:
            break

Semiprime

The code for semiprime kind'a wrote itself from the description. I have a generator of prime factors. Lets check if the first two prime factors multiply to give n for a semiprime. Any errors and it isn't:

In [8]

from prime_decomposition import decompose

def semiprime(n):
    d = decompose(n)
    try:
        return d.next() * d.next() == n
    except:
        return False

You can then play around in the interpreter with it:

In [9]:

semiprime(1679)

Out[9]:

True

In [10]:

[n for n in range(1,101) if semiprime(n)]

Out[10]:

[4,
 6,
 9,
 10,
 14,
 15,
 21,
 22,
 25,
 26,
 33,
 34,
 35,
 38,
 39,
 46,
 49,
 51,
 55,
 57,
 58,
 62,
 65,
 69,
 74,
 77,
 82,
 85,
 86,
 87,
 91,
 93,
 94,
 95]