Semi-Primes

September 6, 2019

We have on several occasions seen functions for generating the primes less than n. Sometimes, what you want instead of primes are semi-primes, numbers which are the product of two primes. For instance, the six semi-primes less than 25 are 2×3=6, 2×5=10, 2×7=14, 3×5=15, 3×7=21 and 2×11=22.

Your task is to write a function that makes a list of the semi-primes less than n; use it to discover the number of semi-primes less than 10,000. 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.

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: