3 ms·
Clearly much worse than the original solution. Basically, a nested sequence of filters is built, one to filter out multiples of each prime number. One way in wh
by cjfd 7y ago
Clearly much worse than the original solution. Basically, a nested sequence of filters is built, one to filter out multiples of each prime number. One way in which the complexity of this is bad is that if you want prime numbers < N you only need to filter out primes smaller than sqrt(N). It is telling that the first solution contains an sqrt but not the second one....
These kind of functional solutions are very cute mathematically, but...
I once wrote this way of generating an infinite list of primes in unlambda. That was kind of interesting to do.
- merijnv 7y ago> One way in which the complexity of this is bad is that if you want prime numbers < N you only need to filter out primes smaller than sqrt(N). It is telling that the first solution contains an sqrt but not the second one.... That's not really true, though, because that filter is applied lazily, so it only get evaluated up until the Nth prime and no further.