The problem with your approach is the gratuitous use of division, which tends to be very slow. In my solution, I first generate a list of "seed primes", all primes less than sqrt 1000000000. Then, for each input m and n, I generate all multiples of the seed primes between m and n. I then output each number that isn't a multiple of a seed prime. Tips: - Haskell will infer the Integer type by default, an unbounded type. Operations on Integer are often considerably slower than Int, the corresponding bounded type. - The accumArray function is a handy way to collect all the generated multiples. For maximum speed, use a UArray Int Bool. - gcd is a particularly expensive function to use here, perhaps you can use the mod function instead? - here is a handy function to generate your seed primes: sieve [] = [] sieve (x:xs) = x : [y | y <- xs, y `mod` x /= 0] Spencer Janssen On Nov 1, 2006, at 10:49 AM, alaiyeshi wrote:
Hi
I'm new to Haskell.
I found this site on the Haskell wiki https://www.spoj.pl. But I got some trouble on trying to solve the problem titled "Prime Generator" https://www.spoj.pl/problems/PRIME1.
The online-judge system tells me "time limit excedded" Would you be so kind to tell me how to make it more faster? And any other suggestion is welcome. Thanks in advance.
--------------------------------------Code begin------------------------------------------------------------ module Main where
import IO import List
main = do input_size<-getLine content<-get_contents (read input_size) mapM_ (\r-> do mapM_ (print) (primeGenerator (parse r)); putStrLn "") content
get_contents n | n == 0 = return [] | otherwise = do content<-getLine rests<-get_contents (n-1) return ([content]++rests)
primeGenerator [start,end] = [x | x<-[start..end], all (== 1) (map (gcd x) [2.. (x-1)]), x/=1]
parse s = unfoldr (\x-> case x of [] -> Nothing _ -> Just (head (reads x))) s
-------------------------------Code ends------------------------------------------------------------------ --------------
(BTW: I'm new to this mailling list also, forgive my rudeness if I am, and forgive my poor English) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe