Semi-Primes

September 6, 2019

If you have a function that lists primes, it is easy to make a function that lists semi-primes:

(define (semi-primes n)
  (let ((ps (primes (quotient n 2))))
    (let loop ((ps ps) (qs (cdr ps)) (ss (list)))
      (cond ((< n (* (car ps) (cadr ps))) (sort < ss))
            ((or (null? qs) (< n (* (car ps) (car qs))))
              (loop (cdr ps) (cddr ps) ss))
            (else (loop ps (cdr qs) (cons (* (car ps) (car qs)) ss)))))))

The program iterates over the primes ps, looping through the remaining primes at each step to form semi-primes, stopping when the product exceeds the desired n. Here we calculate the number of semi-primes at each power of ten (A036351).

> (do ((k 1 (+ k 1))) ((= k 8))
    (display k) (display #\tab)
    (display (length (semi-primes (expt 10 k))))
    (newline))
1       2
2       30
3       288
4       2600
5       23313
6       209867
7       1903878

You can run the program at https://ideone.com/jH2sF6.

Pages: 1 2

4 Responses to “Semi-Primes”

  1. Paul said

    In Python. The semiprimes are generated in order.

    from heapq import merge
    from itertools import takewhile
    
    def semiprimes(limit):
        prs = list(primes(limit // 2))
        seqs = [list(takewhile(lambda p: p <= limit, (a*b for b in prs[i+1:]))) for i, a in enumerate(prs)]
        return list(merge(*seqs))
    
    print(semiprimes(25))  # -> [6, 10, 14, 15, 21, 22]
    print(len(semiprimes(10**4)))  # -> 2600
    
  2. Paul said

    An faster version in Python. The Python sort function is very efficient for a sequence of runs of already sorted items, so there is no point in using merge.

    def semiprimes4(limit):
        prs = list(primes(limit // 2))
        semis = []
        for i, a in enumerate(prs):
            if a * prs[i+1] > limit:  # saves  a lot of time
                break
            for b in prs[i+1:]:
                ab = a * b
                if ab > limit:
                    break
                semis.append(ab)
        return sorted(semis)
    
  3. aman said

    bool isPrime(int n)
    {
    if (n <= 1)
    return false;

        for (int i = 2; i < n; i++)
            if (n % i == 0)
              return false;
    
        return true;
    }
    
    void SemiPrimes()
    {
        List<int> primeNos = new List<int>();
        List<int> semiPrimes = new List<int>();
        bool primeListFilled = false;
    
        for (int i=0;i<num;i++)
        {
            bool isprime = isPrime(i);
            if (i == num-1)
            {
                primeListFilled = true;
            }
            if (isprime)
            {
                primeNos.Add(i);
            }
            Debug.Log(" primeListFilled " + primeListFilled);
        }
        if (primeListFilled)
        {
          for(int i=0;i< primeNos.Count; i++)
          {
            Debug.Log("primeNos "+ primeNos[i]);
                for (int j = i+1; j < primeNos.Count; j++)
                {
                 if (primeNos[i] * primeNos[j] < num)
                 {
                  semiPrimes.Add(primeNos[i] * primeNos[j]);
                 }
               }
          }
        }
    
        foreach (int n in semiPrimes)
        {
            Debug.Log(n);
        }
    }
    
  4. matthew said

    Here’s some Haskell, making use of lazy lists:

    import Data.Lists
    
    primes = 2 : filter f [3,5..] where
      f n = all (\p -> n `mod` p /= 0) (takeWhile (\p -> p*p <= n) primes)
    
    semiprimes = products primes where
      products (p:q:ps) = p*q : merge (map (p*) ps) (products (q:ps))
    
    main = print $ take 100 semiprimes
    
    $ runghc semiprimes.hs 
    [6,10,14,15,21,22,26,33,34,35,38,39,46,51,55,57,58,62,65,69,74,77,82,85,86,87,91,93,94,95,106,111,115,118,119,122,123,129,133,134,141,142,143,145,146,155,158,159,161,166,177,178,183,185,187,194,201,202,203,205,206,209,213,214,215,217,218,219,221,226,235,237,247,249,253,254,259,262,265,267,274,278,287,291,295,298,299,301,302,303,305,309,314,319,321,323,326,327,329,334]
    

    All those merges build up in memory, but we can find eg. 5111663, the 1000000th semiprime without too much trouble in 30 seconds or so.

    If we include the squares of primes in the semiprimes, the code is even simpler:

    semiprimes = products primes where
      products (p:ps) = p*p : merge (map (p*) ps) (products ps)
    
    $ runghc semiprimes.hs 
    [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,106,111,115,118,119,121,122,123,129,133,134,141,142,143,145,146,155,158,159,161,166,169,177,178,183,185,187,194,201,202,203,205,206,209,213,214,215,217,218,219,221,226,235,237,247,249,253,254,259,262,265,267,274,278,287,289,291,295,298,299,301,302,303,305,309,314]
    

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: