(Random observation: Hmmm, strange, in the Data.Map version of primes above, we are missing 5 primes?)<br><br>Hi Chaddai,<br><br>Your algorithm does work significantly better than the others I've posted here :-)<br><br>
So much so, that we're going for a grid of 10000000 to get the timings in an easy-to-measure range. Here are the results:<br><br>J:\dev\haskell>ghc -O2 -fglasgow-exts -o PrimeChaddai.exe PrimeChaddai.hs<br><br>J:\dev\haskell>primechaddai
<br>number of primes: 664579<br>30.984<br><br>J:\dev\test\testperf>csc /nologo primecs.cs<br><br>J:\dev\test\testperf>primecs<br>number of primes: 664579<br>elapsed time: 0,859375<br><br>So, only 30 times faster now, which is quite a lot better :-D
<br><br>Here's the full .hs code:<br><br>module Main<br> where<br><br>import IO<br>import Char<br>import GHC.Float<br>import List<br>import qualified Data.Map as Map<br>import Control.Monad<br>import System.Time<br>
import System.Locale<br><br>merge xs@(x:xt) ys@(y:yt) = case compare x y of<br> LT -> x : (merge xt ys)<br> EQ -> x : (merge xt yt)<br> GT -> y : (merge xs yt)<br><br>diff xs@(x:xt) ys@(y:yt) = case compare x y of
<br> LT -> x : (diff xt ys)<br> EQ -> diff xt yt<br> GT -> diff xs yt<br><br>primes, nonprimes :: [Int]<br>primes = [2,3,5] ++ (diff [7,9..] (nonprimes))<br>nonprimes = foldr1 f . map g $ tail (primes)<br>
where f (x:xt) ys = x : (merge xt ys)<br> g p = [ n*p | n <- [p,p+2..]]<br><br>calculateNumberOfPrimes max = length $ takeWhile ( < max ) primes<br><br>gettime :: IO ClockTime<br>gettime = getClockTime<br>
<br>main = do starttime <- gettime<br> let numberOfPrimes = (calculateNumberOfPrimes 10000000) <br> putStrLn( "number of primes: " ++ show( numberOfPrimes ) )<br> endtime <- gettime
<br> let timediff = diffClockTimes endtime starttime<br> let secondsfloat = realToFrac( tdSec timediff ) + realToFrac(tdPicosec timediff) / 1000000000000<br> putStrLn( show(secondsfloat) )<br> return ()
<br><br><br><div><span class="gmail_quote">On 7/15/07, <b class="gmail_sendername">Chaddaï Fouché</b> <<a href="mailto:chaddai.fouche@gmail.com">chaddai.fouche@gmail.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Or if you really want a function with your requirement, maybe you<br>could take the painful steps needed to write :<br>let numberOfPrimes = length $ takeWhile (< 200000) primes<br>?<br></blockquote></div><br>