Challenge 150 Task #2 - Squarefree integers
Task #2
Description
Write a script to generate all square-free integers <= 500.
In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no perfect square other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 3**2.
Example
The smallest positive square-free integers are
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, ...
Solution
From the description of the task we learn what we have to do for this challenge:
Search through the first 500 integers for the ones that are squarefree and print out the result.
So how do we check if a number is squarefree?
According to the task description we will factorize the given number into its prime components and check if there are any duplicates in the factors. We’ll start by laying out this framework and filling in the details later.
We will employ Perls built-in grep
routine to do the filtering for us. The
filter predicate is a is_squarefree
routine that we are about to define in the
next step. We then go on to print out the filtered lists as comma separated
values.
my @square_free = grep { is_squarefree($_) } 1 .. 500;
say join( ', ', @square_free );
is_squarefree
is defined by a straightforward translation of the process described
above into Perl syntax.
sub is_squarefree($x) {
my @prime_factors = prime_factors($x);
return no_dupes(@prime_factors);
}
With this in place we can now start getting our hands dirty on the details.
Let’s take care of the prime factors. First it’s important to know, that
every natural number has a unique prime factorization. In other words, we should
be able to define a routine that works for every integer input.
If we had an ordered list of all primes, we could walk this list, until
we find a prime that evenly divides our number. This will then be our first
prime factor. If we continue this process with the quotient of the division
until it reaches 1 we have found all prime factors. Since it’s impossible to
calculate all primes, and we don’t know the maximum prime we will need, we need a
way to lazily get and calculate the nth
prime. (Actually we know the maximum
prime we require for the task will be 499, but I think it’s boring to pre-calculate
them and build a solution that will not work for inputs greater than 500)
In Haskell or Raku we would probably reach for a lazy list for our primes, but
in Perl we don’t have that at hand. Instead, we will use a subroutine that we can
ask for the nth
prime and have it calculate it for us.
sub prime_factors($x) {
my @factors;
my $prime = 0;
while ( $x > 1 ) {
my $test_factor = primes($prime);
$prime++;
next unless $x % $test_factor == 0;
push @factors, $test_factor;
$x = $x / $test_factor;
$prime = 0;
}return @factors;
}
For our makeshift lazy prime list we use a state
list that will persist
previously calculated primes across different invocations of the sub
. We can
then check if we already calculated the prime at the requested index $n
and
only if we don’t have it, yet we kick off the process of generating the missing
primes up to the index. At last, we return the requested index from our @primes
list.
sub primes($n) {
state @primes = (2);
for ( my $i = $primes[-1] + 1 ; $#primes < $n ; $i++ ) {
push @primes, $i if is_prime($i);
}
return $primes[$n];
}
To check if a number is prime we hardcode the result for values up to 3. For all
other values we walk from 2 to the symmetry axis of division and check if we
find an even divisor of $x
. If we didn’t find a divisor we know our number is
a prime. This is by far not the fastest or most optimal process of finding prime
numbers. It’s fast enough for our purposes though, straightforward to implement
and easy to understand. That’s why I’m using it here.
sub is_prime($x) {
return 0 if $x <= 1;
return 1 if $x <= 3;
for ( my $i = 2 ; $i < sqrt($x) ; $i++ ) {
return 0 if $x % $i == 0;
}return 1;
}
The final piece needed to finish the implementation is the no_dupes
routine
that checks if the given list is free of duplicates. We do this by iterating
through the list, incrementing a counter in a %seen
hash for each value in the
list. In each iteration we also check if the counter gets bigger than one and
return 0 when that is the case, as it means we found a duplicate. If we make it
through the loop we know, that no duplicates have been found, and we return a 1.
sub no_dupes(@xs) {
my %seen;
for my $x (@xs) {
$seen{$x} += 1;
return 0 if $seen{$x} > 1;
}return 1;
}
There is no comment section on this site. For questions, suggestions or errors in my post or solution, please create an issue over here or drop me a mail:
my $mail = join('@', 'pwc', join('.', 'pankoff', 'net'));