# Perl Weekly Challenge 150: Square-free Integer

by Abigail ## Challenge

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 \cdot 5$$ is square-free, but $$18 = 2 \cdot 3 \cdot 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, ...


## Discussion

This is sequence A005117 in The On-Line Encyclopedia of Integer Sequences. We want the first 306 terms.

We could take each of the numbers $$1 \leq n \leq 500$$, calculate the factors and check whether there are no duplicates. But that does more work than we need to do. Instead, we look at squares of all the primes $$p, 1 < p \leq \sqrt{500}$$. If any of those divides a number $$n$$, $$n$$ is not square-free. Else, it is.

There are only 8 such primes, as $$361 = 19^2 < 500 < 23^2 = 529$$.

## Solutions

### Perl

After setting $,, this is just a one-liner: say grep {$a = $_; 8 == grep {$a % \$_ ** 2} 2, 3, 5, 7, 11, 13, 17, 19} 1 .. 500


Find the full program on GitHub.

### Go

Explicit loops in Go:

func main () {
primes :=  int {2, 3, 5, 7, 11, 13, 17, 19}
for n := 1; n <= 500; n ++ {
s := false
for _, p := range primes {
if (n % (p * p) == 0) {
s = true
break
}
}
if !s {
fmt . Printf ("%d ", n)
}
}
fmt . Printf ("\n")
}


Find the full program on GitHub.

### Other languages

We also have similar implementations in:

AWK, Bash, bc, C, Java, Lua, Node.js, Pascal, Python, R, Ruby, Scheme, and Tcl.