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.

Advertisements

Pages: 1 2

3 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);
        }
    }
    

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: