A positive integer is square-free, if it is not divisible by any perfect square greater than one. That is, if we look at the prime factorization of , . For to be square-free, we must have for . All positive integers can be represented as , where is a perfect square and is square-free. The probability that a randomly picked number is square-free is .

There are a few problems in Project Euler that deal with square-free positive integers. Just a few days ago I solved a PE problem in Kotlin, it took 325 seconds to solve the problem. While I was thinking about solving the problem quicker, I realized that if a certain number was square-free, I should be able to prune some computations. Since we know that about percent of all numbers are square-free, I went ahead and added a check to my code. This reduced the running time to 260 seconds. A reasonable improvement.

Here is the actual snippet that makes the square-free check:

val (sqr_pfs, sqr_free_pfs) = split_square_square_free_pfs(m_pfs)
var of = Long.MAX_VALUE
var c_min = 1L
var skip = false
for ((p, _) in sqr_free_pfs) {
val p_long = p.toLong()
if (p_long > of) {
skip = true
break
}
of = of / p_long
c_min = c_min * p_long
if (c_min >= n_long) {
skip = true
break
}
}
if (skip == false) {
val trplts_for_a = triplets_for_a(n, a, sqr_pfs)
result = result + trplts_for_a
}