You are given a positive integer
$numberand 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).
Input: $number = 100061, $mode = 0
Output: 3
Prime factors are 13, 43, 179. Count is 3.
Input: $number = 971088, $mode = 0
Output: 3
Prime factors are 2, 2, 2, 2, 3, 20231. Count of distinct numbers is 3.
Input: $number = 63640, $mode = 1
Output: 6
Prime factors are 2, 2, 2, 5, 37, 43. Count including duplicates is 6.
Input: $number = 988841, $mode = 1
Output: 2
Input: $number = 211529, $mode = 0
Output: 2
Although the problem speaks about prime numbers, we don't need to calculate
any prime numbers, nor determine whether any number is prime. What we will
do is starting from 2, 3, and then all subsequent odd numbers, determine
whether any divide the given number. If they do, we update the number of
factors, and divide the number by it. We can stop if the divisor is larger
than the square root of the number. It's easy to see we'll never divide by
a composite number: suppose our number $number has a composite number $c
as divisor. Then $c has prime factor $p, with $p < $c, and $p is
either 2, or odd. But this means we have encountered $p before, and have
divided it out from $number. Hence, $c cannot divide $number.
We will count the number of different prime factors, and the total number of
prime factors. Only at the end of the program, when printing the result,
we'll inspect the $mode, and decide which tally to print.
Our programs will read their input from standard input. Each line consists of a number and a mode, separated by a space.
We'll start off by parsing the input, and to initialize the tallies:
my ($number, $mode) = split;
my $diff_factors = 0;
my $factors = 0;
We now try to find divisors. Starting with 2, and then all subsequent
odd numbers, if this number divides the target number, we did find a
different factor. We then divide out this number from the target number
as often as possible, incrementing the factor count by one each time:
for (my $d = 1; $d * $d <= $number; $d += 2) {
use integer; # Avoid rounding errors
my $n = $d == 1 ? 2 : $d;
if ($number % $n == 0) {
$diff_factors ++;
while ($number % $n == 0) {
$factors ++;
$number /= $n;
}
}
}
When this loop terminates, $number either equals 1, or contains a
prime number. In the latter case, we haven't encountered this factor,
so we need to increment both $factors and $diff_factors:
if ($number != 1) {
$diff_factors ++;
$factors ++;
}
The deciding factor on whether the loop ends with $number == 1 or not
depends on prime factorization of the original input number. If the highest
prime factor of this number appears multiple times, $number == 1 after
the loop. If the highest prime factor appears just once, this factor is
what will be left after the loop.
For instance, if $number == 7581, then after the loop $number == 1.
Since \(7581 = 3 \cdot 7 \cdot 19^2\) the loop divides out \(3\), \(7\),
and \(19\) twice. However, if $number == 8211, then the loop exits
with $number == 23, as \(8211 = 3 \cdot 5 \cdot 17 \cdot 23\), so
the loop divides out \(3\), \(5\), and \(17\), leaving \(23\) in $number.
We can now print out the result:
say $mode ? $factors : $diff_factors;
Find the full program on GitHub.
We have almost identical solutions in AWK, Bash, bc, C, Go, Lua, Node.js, Python, R, Ruby, and Tcl.