On 7/14/07, <b class="gmail_sendername">Henk-Jan van Tuyl</b> &lt;<a href="mailto:hjgtuyl@chello.nl">hjgtuyl@chello.nl</a>&gt; wrote:<div><span class="gmail_quote"></span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>There was some discussion about prime number generators earlier this year:<br>&nbsp;&nbsp; <a href="http://www.haskell.org/pipermail/haskell-cafe/2007-February/022347.html">http://www.haskell.org/pipermail/haskell-cafe/2007-February/022347.html
</a><br>&nbsp;&nbsp; <a href="http://www.haskell.org/pipermail/haskell-cafe/2007-February/022699.html">http://www.haskell.org/pipermail/haskell-cafe/2007-February/022699.html</a><br><br></blockquote></div>Ok, so using the following code:
<br><br>module Main<br>&nbsp;&nbsp; where<br><br><br>import IO<br>import Char<br>import GHC.Float<br>import List<br>import Control.Monad<br>import System.Time<br>import System.Locale<br><br>sieve :: [Int] -&gt; [Int]<br>sieve [] = []
<br>sieve (p : xs) = p : sieve [x | x &lt;- xs, x `mod` p &gt; 0]<br><br>calculateNumberOfPrimes :: Int -&gt; Int<br>calculateNumberOfPrimes max = 1 + length( sieve [ 3,5.. (max -1) ] )<br><br>gettime :: IO ClockTime<br>gettime = getClockTime
<br><br>main = do starttime &lt;- gettime<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; let numberOfPrimes = (calculateNumberOfPrimes 200000) <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; putStrLn( &quot;number of primes: &quot; ++ show( numberOfPrimes ) )<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; endtime &lt;- gettime
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; let timediff = diffClockTimes endtime starttime<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; let secondsfloat = realToFrac( tdSec timediff ) + realToFrac(tdPicosec timediff) / 1000000000000<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; putStrLn( show(secondsfloat) )<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return ()
<br><br>With &quot;200000&quot; as the upper limit on the sieve, this gives:<br><br>O:\dev\haskell&gt;ghc -fglasgow-exts -O2 -o prime.exe Prime.hs<br><br>O:\dev\haskell&gt;prime<br>number of primes: 17984<br>8.734<br><br>
For comparison, on the same machine, in C# this gives:<br><br>O:\dev\test\testperf&gt;csc /nologo primecs.cs<br><br>O:\dev\test\testperf&gt;primecs<br>number of primes: 17984<br>elapsed time: 0,015625<br><br>That&#39;s over 500 times faster ;-)
<br><br>Here&#39;s the code in C#<br><br>using System;<br><br>class Primes<br>{<br>&nbsp;&nbsp;&nbsp; <br>&nbsp;&nbsp;&nbsp; public int&nbsp; CalculateNumberOfPrimes( int maxprime )<br>&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp; bool[]IsNotPrime = new bool[ maxprime ]; <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int NumberOfPrimes = 1;
<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for( int i = 3; i &lt; maxprime; i+= 2 )<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if( !IsNotPrime [i] )<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NumberOfPrimes++;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for( int j = ( i &lt;&lt; 1 ); j &lt; maxprime; j+= i )
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if( !IsNotPrime [j] )<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IsNotPrime [ j] = true;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return NumberOfPrimes;<br>&nbsp;&nbsp;&nbsp; }<br>
}<br><br>class EntryPoint<br>{<br>&nbsp;&nbsp;&nbsp; public static void Main()<br>&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; System.DateTime start = System.DateTime.Now;<br>&nbsp;&nbsp;&nbsp; <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int NumberOfPrimes = new Primes().CalculateNumberOfPrimes( 200000 );<br>&nbsp;&nbsp;&nbsp; 
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; System.DateTime finish = System.DateTime.Now;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; double time = finish.Subtract( start ).TotalMilliseconds;;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Console.WriteLine( &quot;number of primes: &quot; + NumberOfPrimes );<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Console.WriteLine( &quot;elapsed time: &quot; + ( time / 1000 ) );<br>&nbsp;&nbsp;&nbsp; }<br>}<br><br><br>