search

hypirion / primes

Fetch, locate and use prime numbers in Clojure.
Eclipse Public License 1.0
6 stars 0 forks source link

last-below and first-above can be speeded up #7

Open hypirion opened 11 years ago

hypirion commented 11 years ago

last-below and first-above are very, very slow, because they generate every prime up to and including the element you get back if they don't exist from before. We could first check if we've generated the prime already (by looking at the last element in primeList) and then binary search if we've already generated numbers above the input value, or if the last prime number generated is within reasonable length from the input value. If this is the case, then binary search for the prime.

If not, do prime? over possible values by utilizing the wheel.

hypirion commented 11 years ago

Speed has been vastly improved through c0c5a000549f4ddc7ec7f1efe1a04247309e9f99 and 675f71037b38b2f8419525a839736a0920b07b10, but that's without a wheel. I'll leave this open as it is still possible to squeeze out some speed from this one.