Radical of an integer
editable example
Click the pencil to open this in an editor, change it, and run it in your browser. The same solution is posted on Rosetta Code.
ghul
use IO.Std.write_line
use Collections.LIST
use Ghul.Pipes
let limit = 1000000
let radical = LIST[int]()
let factor_counts = LIST[int]()
let composite = LIST[bool]()
for _ in 0::limit do
radical.add(1)
factor_counts.add(0)
composite.add(false)
od
for prime in 2..(limit + 1) do
if !composite[prime] then
let multiple mut = prime
while multiple <= limit do
radical[multiple] = radical[multiple] * prime
factor_counts[multiple] = factor_counts[multiple] + 1
composite[multiple] = true
multiple = multiple + prime
od
fi
od
write_line("radicals of the first 50 positive integers:")
for row in 0..5 do
write_line(
(row * 10 + 1..row * 10 + 11)
|> map(n => "{radical[n],3}")
|> join(" "))
od
for n in [99999, 499999, 999999] do
write_line("radical[{n}] = {radical[n]}")
od
let distribution = LIST[int]()
for _ in 0..8 do
distribution.add(0)
od
for n in 1..(limit + 1) do
let count = factor_counts[n]
distribution[count] = distribution[count] + 1
od
write_line("first 1000000 integers by distinct prime factors:")
for count in 0..8 do
if distribution[count] > 0 then
write_line("{count}: {distribution[count]:N0}")
fi
od
prime(n: int, factors: LIST[int], radicals: LIST[int]) -> bool =>
n >= 2 /\ factors[n] == 1 /\ radicals[n] == n
let primes = (2..(limit + 1))
|> filter(n => prime(n, factor_counts, radical))
|> collect_list()
let powers mut = 0
for base in primes do
let power mut = cast long(base) * cast long(base)
while power <= cast long(limit) do
powers = powers + 1
power = power * cast long(base)
od
od
write_line(
"{primes.count:N0} primes plus {powers} prime powers "
"= {primes.count + powers:N0}, matching the one-factor "
"count {distribution[1]:N0}")