SEMIPRIMES

Testing the Waters with Semiprime Numbers... thanks to this LinkedIn Post bringing them to my awereness.

Iota Range Filtering Approach

Source code

import std.stdio: writeln, writefln;
import std.range;
import std.algorithm;

/// OEIS coding as a naming convention
/// Refer to https://oeis.org/A001358
/// Semiprimes (or biprimes): products of two primes.

bool isA001358(ulong n) pure nothrow @safe {
    if (n < 4)
        return false;

    ulong factorCount = 0;
    
    for (ulong i = 2; i * i <= n && factorCount < 3; ++i) {
        while (n % i == 0) {
            ++factorCount;
            n /= i;
        }
    }
    
    if (n > 1)
        ++factorCount;
    
    return factorCount == 2;
}

void main() {    
    const N = 100uL;
    auto immutable semiprimes = iota(N+1).filter!isA001358.array;
    
    writeln;
    semiprimes.writeln;
    
    writefln("\nSum of the 1st %s semiprime = %d", N, semiprimes.sum);
    
}

Output

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

Sum of the 1st 100 semiprime = 1707

Direct Semiprime generation Approach

Source code

import std.stdio: writefln;
import std.datetime.stopwatch: StopWatch;
import std.algorithm: all, filter, until;
import std.range: iota;
import std.array: Appender, array;
import std.algorithm: sort;
import std.algorithm.iteration;

auto generate_sp(ulong limit) {
    auto isPrime = (ulong number) => number >= 2 && iota(2, number).until!(x => x * x > number).all!(x => (number % x) != 0);
    auto primes = (iota(limit).filter!isPrime).array;
    
    Appender!(ulong[]) semiprimes;

    foreach (p1; primes) {
        if (p1 * p1 > limit) {
            // Limit exceeded
            break;  
        }
        
        foreach (p2; primes) {
            auto semiprime = p1 * p2;
            
            if (semiprime <= limit) {
                semiprimes ~= semiprime;
            } else {
                // Limit exceeded
                break;  
            }
        }
    }

    return semiprimes.data.sort.uniq;
}

void main() {
    StopWatch timer;
    timer.start();
    
    const LIMIT = 100uL;
    
    auto semiprimes = generate_sp(LIMIT);
    
    auto sumOfSp = semiprimes.sum;
    
    writefln("\nSum of the 1st. %,3?d semiprimes: %,3?d", '_', LIMIT, '_', sumOfSp);
    
    timer.stop();
    writefln("Elapsed time: %s milliseconds.\n", timer.peek.total!"msecs"());
}

Output

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

Sum of the 1st. 100 semiprimes: 1_707
Elapsed time: 7 milliseconds.

Extra Bonus

When tackling number theory problems and developing algorithms, I occasionally employ Pari GP, a lightweight computer algebra system. I came up with the following:

generate_sp(limit) = {
    my(semiprimes);
    semiprimes = [];
    forprime(p1=2, limit, forprime(p2=2, limit, semiprime = p1 * p2; if (semiprime <= limit, semiprimes = concat(semiprimes, semiprime))));
    semiprimes = Set(semiprimes);
    semiprimes = Vec(semiprimes); 
    semiprimes = vecsort(semiprimes);
    semiprimes
}

Simple session example:

(10:24) gp > generate_sp(100)
%2 = [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]
(10:29) gp > vecsum(%2)
%3 = 1707
(10:29) gp >

References

A001358 Sequence