Big and little omega

You are given a positive integer $number and a mode flag $mode. If the mode flag is zero, calculate little omega (the count of all distinct prime factors of that number). If it is one, calculate big omega (the count of all prime factors including duplicates).

Examples

Example 1
Input: $number = 100061
       $mode = 0
Output: 3

Example 2
Input: $number = 971088
       $mode = 0
Output: 3

Example 3
Input: $number = 63640
       $mode = 1
Output: 6

Example 4
Input: $number = 988841
       $mode = 1
Output: 2

Example 5
Input: $number = 211529
       $mode = 0
Output: 2

Analysis

Of course there are modules to derive prime factors, but in the spirit of using 'pure' Perl I have used the good old Sieve of Eratosthenes.

I then check $number for being divisible by all the prime numbers up to $number / 2, checking for repeated factors if $mode == 1.

This note from Peter provides an outstandingly efficient method for solving Challenge 368, especially with regard to the "bits of conflict" analysis. The technical evaluation also features exceptional high-level mathematical intuition used in conjunction with using circular arithmetic to solve the problem of complex interval overlaps. Additionally, his Perl solutions are uniquely clean and optimized for speed.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-04-06
use utf8;     # Week 368 - task 2 - Big and little omega
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

big_and_little_omega(100061, 0);
big_and_little_omega(971088, 0);
big_and_little_omega(63640, 1);
big_and_little_omega(988841, 1);
big_and_little_omega(211529, 0);

sub big_and_little_omega {
    
    my ($number, $mode, $sieve, $p, $count, $explain, $try, $omega);
    
    # initialise
    ($number, $mode) = @_;
    
    # loop over primes < $number
    $sieve = make_sieve($number / 2);
    for $p (2 .. $number) {
        next unless $sieve->[$p];
        $try = $number;
        
        # is this prime a factor?
        while (1) {
            $try = $try / $p;
            last unless $try == int($try);
            $explain .= qq[$p, ];
            $count ++;
            
            # repeat unless looking for little omega
            last if ($mode == 0 or $try == 1);
        }
    }
    
    # report
    $explain = substr($explain, 0, -2); 
    $omega = $mode ? 'Ω' : 'ω' ;
    say qq[\nInput:  \$number = $number, \$mode = $mode];
    say qq[Output: $omega = $count ($explain)];
}

sub make_sieve {  # of Eratosthenes

    my ($arg, $j, $k, @sieve);
    
    # set all values provisionally to 1 (ie prime)
    $arg = shift;
    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;
}

29 lines of code

Output from script

Input:  $number = 100061, $mode = 0
Output: ω = 3 (13, 43, 179)

Input:  $number = 971088, $mode = 0
Output: ω = 3 (2, 3, 20231)

Input:  $number = 63640, $mode = 1
Output: Ω = 6 (2, 2, 2, 5, 37, 43)

Input:  $number = 988841, $mode = 1
Output: Ω = 2 (7, 141263)

Input:  $number = 211529, $mode = 0
Output: ω = 2 (37, 5717)