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