Square-free integers

In Sidef, the functions is_square_free(n) and square_free_count(min, max) are built-in. However, we can very easily reimplement them in Sidef code, as fast integer factorization methods are also available in the language.

func is_square_free(n) {

    n.abs!       if (n <  0)
    return false if (n == 0)

    n.factor_exp + [[1,1]] -> all { .[1] == 1 }
}

func square_free_count(n) {
    1 .. n.isqrt -> sum {|k|
        moebius(k) * idiv(n, k*k)
    }
}

func display_results(a, c, f = { _ }) {
    a.each_slice(c, {|*s|
        say s.map(f).join(' ')
    })
}

var a = range(   1,      145).grep {|n| is_square_free(n) }
var b = range(1e12, 1e12+145).grep {|n| is_square_free(n) }

say "There are #{a.len} square─free numbers between 1 and 145:"
display_results(a, 17, {|n| "%3s" % n })

say "\nThere are #{b.len} square─free numbers between 10^12 and 10^12 + 145:"
display_results(b, 5)
say ''

for (2 .. 6) { |n|
    var c = square_free_count(10**n)
    say "The number of square─free numbers between 1 and 10^#{n} (inclusive) is: #{c}"
}

Output:

PreviousSQL-based authenticationNextSquare but not cube

Last updated

Was this helpful?