Task — Semiprime

Write a script to generate all Semiprime number <= 100. In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers.

There is more info in Wikipedia.

Examples

Example
10 is Semiprime as 10 = 2 × 5
15 is Semiprime as 15 = 3 × 5

Analysis

I reckon the easiest way to do this is to make a sieve of Eratosthenes up to $limit (100) and then use two nested loops, the outer being

for $j (2 .. int(sqrt($limit)))

and the inner one being

for $k ($j .. int($limit / $j))

In each loop we immediately do next if $j or $k isn't prime (ie isn't in our sieve), any any $j and $k that survive that can be multiplied together to form a number which is semiprime and no more than $limit.

I tried that with a limit of 1 000 000 and it ran in under 2 seconds (the last one is 999 997 = 757 × 1321), so I would say further optimisation is not needed.

Try it 

Try running the script with any input:

Your $limit =

example: 1000

⤡

#!/usr/bin/perl

# Peter Campbell Smith - 2021-12-20
# PWC 144 task 1

use v5.20;
use warnings;
use strict;

my ($limit, $sqrt_limit, @is_prime, @semiprimes, $j, $k, $p);

# find semiprimes <= $limit
$limit = 100;

# find primes up to $limit / 2
@is_prime = make_sieve(int($limit / 2));   # $j is prime if $primes[$j] == 1
say qq[\nSemiprimes no greater than $limit are:];

# the smaller prime cannot exceed sqrt($limit)
for $j (2 .. int(sqrt($limit))) {
    next unless $is_prime[$j];
    
    # the larger one cannot exceed $limit / the smaller one
    for $k ($j .. int($limit / $j)) {
        next unless $is_prime[$k];
        @semiprimes[$j * $k] = qq[$j × $k];
    }
}

for $j (1 .. $limit) {
    say qq[$j = $semiprimes[$j]] if (defined $semiprimes[$j]);
}
say '';

sub make_sieve {
    
    # make sieve of Eratosthenes
    my ($arg, $j, $k, @sieve);
    
    # set all values provisionally to 1 (ie prime)
    $arg = $_[0];
    for $j (0 .. $arg) {
        $sieve[$j] = 1;
    }
    
    # for each prime in turn, set its multiples to 0 (ie not prime)
    for $j (2 .. $arg) {
        next unless $sieve[$j];   # $j is not prime     
        last if $j ** 2 > $arg;
        for $k ($j .. $arg) {
            last if $k * $j > $arg;
            $sieve[$k * $j] = 0;
        }
    }
    return @sieve;
}

Output

Semiprimes no greater than 100 are:
4 = 2 × 2
6 = 2 × 3
9 = 3 × 3
10 = 2 × 5
14 = 2 × 7
15 = 3 × 5
21 = 3 × 7
22 = 2 × 11
25 = 5 × 5
26 = 2 × 13
33 = 3 × 11
34 = 2 × 17
35 = 5 × 7
38 = 2 × 19
39 = 3 × 13
46 = 2 × 23
49 = 7 × 7
51 = 3 × 17
55 = 5 × 11
57 = 3 × 19
58 = 2 × 29
62 = 2 × 31
65 = 5 × 13
69 = 3 × 23
74 = 2 × 37
77 = 7 × 11
82 = 2 × 41
85 = 5 × 17
86 = 2 × 43
87 = 3 × 29
91 = 7 × 13
93 = 3 × 31
94 = 2 × 47
95 = 5 × 19