[Haskell-cafe] how to make haskell faster than python at finding
primes?
david48
dav.vire+haskell at gmail.com
Mon Aug 6 05:25:04 EDT 2007
On 8/6/07, Vimal <j.vimal at gmail.com> wrote:
> I am unable to see how exactly this will run. Given that primes is an infinite
> list, and that when it reaches numbers say, as large as 10000, it will have to
> keep track of all the numbers (essentially prime numbers, which is the answer),
> whose mutliples it has to remove!
>
> Say for eg: I give
> > take 100 primes
> 2 : [ 3...]
> then 2:3:[4 ... ]
> It will *now* have to remove 4,
> 2:3:[5...]
> Then 2:3:5:[6 ...]
Isn't it how it runs ? :
2: sieve [3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,
47,49,... ]
then
2:3:sieve [5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,... ]
then
2:3:5:sieve [7,11,13,17,19,23,29,31,37,41,43,47,49,... ]
then
2:3:5:7:sieve [11,13,17,19,23,29,31,37,41,43,47,... ]
then
2:3:5:7:11:sieve [13,17,19,23,29,31,37,41,43,47,... ]
etc...
More information about the Haskell-Cafe
mailing list