## 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)
{
}
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)
{
}
}
}
}

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]
```