Task — Square-free integer

Write a script to generate all square-free integers <= 500. In mathematics, a square-free integer is an integer which is divisible by no perfect square other than 1. That is, its prime factorisation 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.

Examples

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, ...

Analysis

This is going to be one of those tasks where someone will have a quick solution using number theory, someone else will tell us there's a Perl module to do it, and we'll probably see a few one-line answers as well.

Mine is none of these. I modified the method of my good friend Eratosthenes to say:

• Let's assume all numbers are square free
• Then strike out those that are multiples of squares

A little thought allows some optimisation of the striking out:

• We only need to consider squares of numbers up to the square root of the limit (500)
• We can ignore squares of numbers that we already know are square free

But the optimisation makes no discernable difference even if we extend the limit to a million.

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2022-01-31
# PWC 150 task 2

use v5.28;
use strict;
use warnings;
use utf8;

my ($j, $mult, $no_good, $square, $top, @sfi, $results, $count);

$top = 500;

# let's start by guessing that all integers are square-free
for $j (1 .. $top) {
    $sfi[$j] = 1;
}

# now let's knock out anything that is a multiple of a square
for $j (2 .. int(sqrt($top))) {       
    next unless $sfi[$j];   # no need to bother if $j is a known non-square-free
    $square = $j ** 2;
    for ($mult = 1;; $mult ++) {
        $no_good = $mult * $square;
        last if $no_good > $top;
        $sfi[$no_good] = 0;
    }
}

# output what's left neatly
say qq[Square-free integers <= $top: ];
$count = 1;
for $j (1 .. $top) {
    next unless $sfi[$j];
    $results .= sprintf('%3d',$j) . ', ';
    $results .= qq[\n] unless ($count++ % 10);
}
$results =~ s|[, \n]+$||;
say $results;

Output

Square-free integers <= 500: 
  1,   2,   3,   5,   6,   7,  10,  11,  13,  14, 
 15,  17,  19,  21,  22,  23,  26,  29,  30,  31, 
 33,  34,  35,  37,  38,  39,  41,  42,  43,  46, 
 47,  51,  53,  55,  57,  58,  59,  61,  62,  65, 
 66,  67,  69,  70,  71,  73,  74,  77,  78,  79, 
 82,  83,  85,  86,  87,  89,  91,  93,  94,  95, 
 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 
113, 114, 115, 118, 119, 122, 123, 127, 129, 130, 
131, 133, 134, 137, 138, 139, 141, 142, 143, 145, 
146, 149, 151, 154, 155, 157, 158, 159, 161, 163, 
165, 166, 167, 170, 173, 174, 177, 178, 179, 181, 
182, 183, 185, 186, 187, 190, 191, 193, 194, 195, 
197, 199, 201, 202, 203, 205, 206, 209, 210, 211, 
213, 214, 215, 217, 218, 219, 221, 222, 223, 226, 
227, 229, 230, 231, 233, 235, 237, 238, 239, 241, 
246, 247, 249, 251, 253, 254, 255, 257, 258, 259, 
262, 263, 265, 266, 267, 269, 271, 273, 274, 277, 
278, 281, 282, 283, 285, 286, 287, 290, 291, 293, 
295, 298, 299, 301, 302, 303, 305, 307, 309, 310, 
311, 313, 314, 317, 318, 319, 321, 322, 323, 326, 
327, 329, 330, 331, 334, 335, 337, 339, 341, 345, 
346, 347, 349, 353, 354, 355, 357, 358, 359, 362, 
365, 366, 367, 370, 371, 373, 374, 377, 379, 381, 
382, 383, 385, 386, 389, 390, 391, 393, 394, 395, 
397, 398, 399, 401, 402, 403, 406, 407, 409, 410, 
411, 413, 415, 417, 418, 419, 421, 422, 426, 427, 
429, 430, 431, 433, 434, 435, 437, 438, 439, 442, 
443, 445, 446, 447, 449, 451, 453, 454, 455, 457, 
458, 461, 462, 463, 465, 466, 467, 469, 470, 471, 
473, 474, 478, 479, 481, 482, 483, 485, 487, 489, 
491, 493, 494, 497, 498, 499