Task

Write a function to test if a number is   square-free.



A   square-free   is an integer which is divisible by no perfect square other
than   1   (unity).

For this task, only positive square-free numbers will be used.



Show here (on this page) all square-free integers (in a horizontal format) that are between:

   1   ───►   145     (inclusive)
   1 trillion   ───►   1 trillion + 145     (inclusive)


(One trillion = 1,000,000,000,000)



Show here (on this page) the count of square-free integers from:

   1   ───►   one hundred     (inclusive)
   1   ───►   one thousand     (inclusive)
   1   ───►   ten thousand     (inclusive)
   1   ───►   one hundred thousand     (inclusive)
   1   ───►   one million     (inclusive)


See also

   the Wikipedia entry:   square-free integer


import Data.List.Split (chunksOf)
import Math.NumberTheory.Primes (factorise)
import Text.Printf (printf)
 
-- True iff the argument is a square-free number.
isSquareFree :: Integer -> Bool
isSquareFree = all ((== 1) . snd) . factorise
 
-- All square-free numbers in the range [lo, hi].
squareFrees :: Integer -> Integer -> [Integer]
squareFrees lo hi = filter isSquareFree [lo..hi]
 
-- The result of `counts limits values' is the number of values less than or
-- equal to each successive limit.  Both limits and values are assumed to be
-- in increasing order.
counts :: (Ord a, Num b) => [a] -> [a] -> [b]
counts = go 0
  where go c lims@(l:ls) (v:vs) | v > l     = c : go (c+1) ls vs
                                | otherwise = go (c+1) lims vs
        go _ [] _  = []
        go c ls [] = replicate (length ls) c
 
printSquareFrees :: Int -> Integer -> Integer -> IO ()
printSquareFrees cols lo hi =
  let ns = squareFrees lo hi
      title = printf "Square free numbers from %d to %d\n" lo hi
      body = unlines $ map concat $ chunksOf cols $ map (printf " %3d") ns
  in putStrLn $ title ++ body
 
printSquareFreeCounts :: [Integer] -> Integer -> Integer -> IO ()
printSquareFreeCounts lims lo hi =
  let cs = counts lims $ squareFrees lo hi :: [Integer]
      title = printf "Counts of square-free numbers\n"
      body = unlines $ zipWith (printf "  from 1 to %d: %d") lims cs
  in putStrLn $ title ++ body
 
main :: IO ()
main = do
  printSquareFrees 20 1 145
  printSquareFrees 5 1000000000000 1000000000145
  printSquareFreeCounts [100, 1000, 10000, 100000, 1000000] 1 1000000