<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi,<div><br></div><div>I have bungled the <a href="http://www.spoj.pl/problems/PRIME1/">Prime Generator</a> on SPOJ for many times. Although the program is faster and faster on my machine, but it keeps "time limited exceeded" on SPOJ (6 seconds limit). Now my approach is for every number in the range, check if it is prime by checking if can be divided by all the primes smaller than or equal its square root. For the numbers between 999900000 and 1000000000, it take 0.64 seconds on my laptop. Could anyone give me some hints to enhance it? Thanks.</div><div><br></div><div>=== Test Data ===</div><div><div>1</div><div>999900000 1000000000</div></div><div>=== Test Data ===</div><div><br></div><div>=== Code ===</div><div><div>{-# OPTIONS_GHC -O2 -fno-cse #-}</div><div><br></div><div>import System.IO</div><div><br></div><div>data Wheel a = Wheel a [a]</div><div><br></div><div>roll :: Integral a => Wheel a -> [a]</div><div>roll (Wheel n rs) = [n*k+r | k <- [0..], r <- rs]</div><div><br></div><div>nextSize :: Integral a => Wheel a -> a -> Wheel a</div><div>nextSize (Wheel n rs) p =</div><div> Wheel (p*n) [r' | k <- [0..(p-1)], r <- rs,</div><div> let r' = n*k+r, r' `mod` p /= 0]</div><div><br></div><div>mkWheel :: Integral a => [a] -> Wheel a</div><div>mkWheel ds = foldl nextSize (Wheel 1 [1]) ds</div><div><br></div><div>primes :: Integral a => [a]</div><div>primes = small ++ large where</div><div> 1:p:candidates = roll $ mkWheel small</div><div> small = [2,3,5,7]</div><div> large = p : filter isPrime candidates</div><div> isPrime n = all (not . divides n) </div><div> $ takeWhile (\p -> p*p <= n) large</div><div><br></div><div>divides :: Integral a => a -> a -> Bool</div><div>divides n p = n `mod` p == 0</div><div><br></div><div>sqrt' :: Integral a => a -> a</div><div>sqrt' = floor . sqrt . fromIntegral</div><div><br></div><div>primesFromTo :: [Int] -> [Int]</div><div>primesFromTo [x, y] = filter isPrime [x..y]</div><div><br></div><div>isPrime :: Integral a => a -> Bool</div><div>isPrime 1 = False</div><div>isPrime 2 = True</div><div>isPrime n = all (not . divides n) $ takeWhile (<= sqrt' n) primes</div><div><br></div><div>main :: IO ()</div><div>main = do</div><div> count <- fmap read getLine</div><div> inputLines <- fmap (take count . lines) getContents</div><div> let answers = map (primesFromTo . map read . words) inputLines</div><div> putStr . unlines . map (unlines . map show) $ answers</div></div><div><br></div><div>=== Code ===<br><div apple-content-edited="true">
<div><br class="Apple-interchange-newline">Best regards,<br class="Apple-interchange-newline">Zhi-Qiang Lei</div><div><a href="mailto:zhiqiang.lei@gmail.com">zhiqiang.lei@gmail.com</a></div>
</div>
<br></div></body></html>