[Haskell-cafe]Prime Generator time limit exceeded

[Spencer Janssen]

On Nov 2, 2006, at 8:48 AM, alaiyeshi wrote:
> Also, I guess my code still waste too much time "parsing" input (I  
> compiled my code with -prof flag on)...
> Maybe ByteString may save me (or a smarter brain), What is your  
> opinion about doing faster IO, would you please tell me?

ByteString will likely make this problem go faster, but sadly SPOJ  
doesn't have the FPS library or GHC 6.6.  My submission doesn't use  
any fancy IO tricks and manages to complete in 2.28 seconds.

There is one major problem with your IO code.  get_contents will read  
every line of input before doing any other processing or output.   
This could potentially eat up a ton of memory, and thereby make your  
program slow.  A better approach is to interleave reading input and  
printing output.  Here is the input code from my submission:

\begin{code}
main = do
     cases <- readLn
     replicateM_ cases $ do
         s <- getLine
         let [m, n]     = map read $ words s
	{- fill in the blank! -}
\end{code}


Cheers,
Spencer Janssen