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\).
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, ...
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\).
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.
Explicit loops in Go:
func main () {
primes := [8] 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.
We also have similar implementations in:
AWK, Bash, bc, C, Java, Lua, Node.js, Pascal, Python, R, Ruby, Scheme, and Tcl.