34 lines
829 B
Text
34 lines
829 B
Text
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}"
|
|
}
|