# Perl Weekly Challenge 141: Number Divisors

by Abigail ## Challenge

Write a script to find lowest 10 positive integers having exactly 8 divisors.

### Example

24 is the first such number having exactly 8 divisors.
1, 2, 3, 4, 6, 8, 12 and 24.


## Discussion

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.

### Other Language

We also have implementations (all very similar to the Ruby implementation) in AWK, Bash, bc, C, Go, Java, Lua, Node.js, Pascal, Python, R, Scheme, and Tcl.