Perl Weekly Challenge 141: Number Divisors

A positive integer has an odd number of divisors if and only the number is a square.

If $d$ is a divisor of $n$, then $\frac{n}{d}$ is also a divisor of $n$.

For every divisor $d$ of a number $n$, where $n$ is not a square, exactly one of $d$ and $\frac{n}{d}$ is less than $\sqrt{n}$.

This means that any number which is a square cannot have exactly eight divisors. And for non-squares $n$, the number has exactly eight divisors, if, and only if, $n$ has exactly four divisors less than $\sqrt{n}$.

Solutions

Perl

The module Math::Prime::Util has a method divisors which, in scalar context, returns the number if divisors a number has.

Which means that, after using the module, we're left with a one-liner:

use Math::Prime::Util qw [divisors];

8 == divisors (++ $::n) && say ($::n) && $::c ++ while $::c < 10;

Don't turn on warnings, as $::c starts off as undefined.

Find the full program on GitHub.

Ruby

For all our other implementations, we start inspecting numbers n starting from 1. We can skip squares immediately. If the number isn't a square, we count divisors, by checking all numbers d from 1 to the square root of n. If d is a divisor of n, we increment the divisor count by 2.

We can break the loop if we have seen more than 8 divisors.

If a number n has 8 divisors, we print n. Once we have printed 10 such numbers, we're done.

count          = 10
nr_of_divisors =  8

n = 0
while count > 0 do
    n = n + 1
    s = Math . sqrt(n) . floor()
    if n == s * s then
       next
    end
    c = 0
    for d in 1 .. s do
        if n % d == 0 then
            c = c + 2
            if c > nr_of_divisors then
                break
            end
        end
    end
    if c == nr_of_divisors then
        puts (n)
        count = count - 1
    end
end

Find the full program on GitHub.

Perl Weekly Challenge 141: Number Divisors

Challenge

Example

Discussion

Solutions

Perl

Ruby

Other Language