Almost Primes

April 19, 2019

Today’s exercise was inspired by a task at Rosetta Code:

An integer n > 1 is a k-almost-prime if it is the product of k primes. Further, a k-almost prime is squarefree if all k primes are distinct.

You can learn more about k-almost-primes and their uses in number theory at Wikipedia or MathWorld.

Your task is to write programs that calculate the first ten k-almost-primes and squarefree k-almost-primes for 1 ≤ k ≤ 5. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

2 Responses to “Almost Primes”

  1. Paul said

    In Python. almost_prime simply iterates over all numbers, factorises them and checks if they comply. This is slow for higher k and n. almost_prime3 builds numbers from factors and is a lot faster.

    from heapq import heappop, heappush
    from itertools import count
    from functools import partial, reduce
    from operator import mul
    
    from primesieve import n_primes  # primesieve from pypi.org
    
    from ma.primee import factors_auto  # td_factors and rho_factors
    
    def almost_prime(k, n, squarefree=False):
        """generate n k-almost_primes
           simply try all numbers and see if they check
        """
        res = []
        for i in count(2):
            facs = factors_auto(i)
            if len(facs) == k:
                if not squarefree or len(set(facs)) == k:
                    res.append(i)
                    if len(res) == n:
                        return res  
    
    # these are slow (especially skap)
    kap, skap = (partial(almost_prime, squarefree=b) for b in (False, True))
    
    def almost_prime3(k, n, squarefree=False):
        """generate n k-almost_primes
           use a priority queue (heap) with the value of the number as key
           pop the lowest number and increase the primes to get new candidate numbers
        """
        res = []
        prs = n_primes(k+n)
        next_prime = {k: v for k, v in zip(prs, prs[1:])}
        first = prs[:k] if squarefree else [2] * k
        heap = [(reduce(mul, first), first)]
        lastn = 0
        while heap:
            number, factors = heappop(heap)
            if number == lastn: # sometimes combinations are repeated
                continue
            lastn = number
            res.append(number)
            if len(res) == n:
                return res
            lastf = 0
            for i, f in enumerate(factors):
                if f == lastf:  # avoid as much as possible repetitions
                    continue
                lastf = f
                p = next_prime[f]
                if p and (not squarefree or p not in factors):
                    factors2 = list(factors)
                    factors2[i] = p
                    factors2.sort()
                    heappush(heap, (reduce(mul, factors2), factors2))
    
    kap3, skap3 = (partial(almost_prime3, squarefree=b) for b in (False, True))
    
    k, n = 20, 10
    print(kap3(k, n))
    print(skap3(k, n))
    
    [1048576, 1572864, 2359296, 2621440, 3538944, 3670016, 3932160, 5308416, 5505024, 5767168]
    [557940830126698960967415390, 573657473228859495079173570, 607905680585806330606288410, 620807402535341097414448110, 652240688739662165637964470, 657870531044913700245161430, 667699681954902035256087270, 676402095299700001660518090, 690333569478797019502056330, 691180431350985280004410110]
    
  2. Ernie said

    Here is a faster algorithm for square free

    Select the smallest k-almost-prime (the product of the first k primes)
    Create z, the list of candidates from the smallest k-almost-prime. A candidate is an array
    of primes of length k
    Create a list, y, of next possible candidates from min of z.
    Example: say the current min for k = 3 is {0,3,4} where the values in min are indices
    into a list of primes. Increment each value. Then y is {1,3,4}, {0,4,5}, {0,3,5}. Note
    that {0,4,4} is not allowed because we require square free.
    Select the smallest of these candidates, add its product to result, remove it from y and
    then add the remaining y[i] to z
    Go to 3. Stop when result.Count = 10

    For k = 5 there is little difference between brute force and this algorithm but for k > 5 the difference in execution time
    becomes pronounced; for k = 7, brute force = 550 msec; above algorithm = 10 msec

    Still working on not square free

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: