Prime Checker without doing any division or modulo

IsPrime.hs

{-#OPTIONS_GHC -O2 -optc-O3 #-}

{-
Author: Wiebe-Marten Wijnja
Date: 2018-02-12

This simple program is a Prime Checker.
It is special, in that does not perform any
division or modulo operations to check if a number is a prime,
which most prime checkers or prime sieves do.

Rather, a list of primes is generated by comparing each next natural number to a list of known prime multiples.

How do we get prime multiples? By multiplying each prime we know so far with all possible natural numbers larger than one.
And these lists of prime multiples can be combined again to form an infinite list of infinite lists of numbers we know for certain are not prime.

Interestingly, this two-dimensional infinite stream is increasing in both dimensions:
- The numbers to the head of the inner lists are never larger than the ones in the tail.
- The numbers in the head of the first list are never larger than the ones in the next list on.

These invariants allow us to cleverly construct a multi-merge that combines them to one flat list.

Now since we have a list of non-primes (which includes adjacent duplicates, but this does not matter),
we can easily compare the list of all natural numbers to this list, to find the next primes.

And now we have enough ingredients to tie the loop, and build out primes and primeMultiples at the same time.


-}

import System.Environment
import System.IO

main :: IO ()
main = do
  args <- getArgs
  case args of
    [possiblePrimeStr] | [(possiblePrime,_)] <- reads possiblePrimeStr -> do
      if possiblePrime > 0 then do
        if isPrime possiblePrime then
          putStrLn $ (show possiblePrime) ++  " is a Prime!"
        else
          putStrLn $ (show possiblePrime) ++ " is NOT Prime."
      else
        printUsage
    _ -> do
      printUsage

printUsage :: IO ()
printUsage = do
      name <- getProgName
      hPutStrLn stderr $ "usage: " ++ name ++ " <positive_integer>"
      putStrLn "Here are the first 500 primes: "
      putStrLn (show $ take 500 primes)

primeMultiples :: [Integer]
primeMultiples = infiniteMergeSortedInfiniteLists $ nestedPrimeMultiples
  where
    nestedPrimeMultiples =  map (\x -> map (x*)  [2..]) primes

primes :: [Integer]
primes = [2,3,5] ++ filterPrimes [6..] primeMultiples
  where
    filterPrimes (a:as) (b:bs) = case compare a b of
      EQ -> filterPrimes as (b:bs)
      LT -> (a : filterPrimes as (b:bs))
      GT -> filterPrimes (a:as) bs
    filterPrimes _ _ = []

isPrime :: Integer -> Bool
isPrime x = x == (head $ dropWhile (<x) primes)


{- Merges an infinite number of potentially infinite lists in order,
given the invariant(s) that:
1. each of these lists is ordered
2. that the list of lists is ordered.

Based on https://stackoverflow.com/a/2395505/1067339
which is based on https://hackage.haskell.org/package/ListTree-0.1/docs/src/Data-List-Tree.html#mergeOnSortedHeads
-}
infiniteMergeSortedInfiniteLists :: Ord a => [[a]] -> [a]
infiniteMergeSortedInfiniteLists [] = []
infiniteMergeSortedInfiniteLists ([]:xs) = infiniteMergeSortedInfiniteLists xs
infiniteMergeSortedInfiniteLists ((x:xs):ys) =
  x : infiniteMergeSortedInfiniteLists (bury xs ys)
  where
    bury [] bs = bs
    bury as [] = [as]
    bury as ([] : bs) = bury as bs
    bury as@(a:_) cs@(bs@(b:_):ct)
      | a <= b = as : cs
      | otherwise = bs : bury as ct