Task

Write a function to test if a number is   square-free.



A   square-free   is an integer which is divisible by no perfect square other
than   1   (unity).

For this task, only positive square-free numbers will be used.



Show here (on this page) all square-free integers (in a horizontal format) that are between:

   1   ───►   145     (inclusive)
   1 trillion   ───►   1 trillion + 145     (inclusive)


(One trillion = 1,000,000,000,000)



Show here (on this page) the count of square-free integers from:

   1   ───►   one hundred     (inclusive)
   1   ───►   one thousand     (inclusive)
   1   ───►   ten thousand     (inclusive)
   1   ───►   one hundred thousand     (inclusive)
   1   ───►   one million     (inclusive)


See also

   the Wikipedia entry:   square-free integer


use ntheory qw/is_square_free moebius/;
 
sub square_free_count {
    my ($n) = @_;
    my $count = 0;
    foreach my $k (1 .. sqrt($n)) {
        $count += moebius($k) * int($n / $k**2);
    }
    return $count;
}
 
print "Square─free numbers between 1 and 145:\n";
print join(' ', grep { is_square_free($_) } 1 .. 145), "\n";
 
print "\nSquare-free numbers between 10^12 and 10^12 + 145:\n";
print join(' ', grep { is_square_free($_) } 1e12 .. 1e12 + 145), "\n";
 
print "\n";
foreach my $n (2 .. 6) {
    my $c = square_free_count(10**$n);
    print "The number of square-free numbers between 1 and 10^$n (inclusive) is: $c\n";
}