Counting primes in a range whose digits are all prime

Question

Codewars Kata: Given integers a and b, count all primes p where a ≤ p < b and the digits of p are all prime. b may be as large as 10⁷.

To start with, I hardcoded all valid 1903 primes in \$[1, 10^7]\$ that can be formed from digits \$\{2, 3, 5, 7\}\$ and stored it in a list. Then I use binary search to locate the indexes corresponding to the given bounds, then return the difference of these indexes + 1, and my code times out. That is frankly baffling to me. Like I can't even coherently theorise why the program would be slow. All the heavy duty computation is handled by the binary search which is logarithmic time, and is called only a few times and on a 1903 element list (Also, the binary search function completes 1000 searches of 200,000 element lists in 228.67s in another kata, so I don't think I implemented it poorly).
enter image description here enter image description here

My Code

def xbinsearch(pred, lst, *extras, type = "min", default = None):
 low, hi, best = 0, len(lst)-1, default
 while low <= hi:
 mid = (low+hi)//2
 p = pred(mid, lst, *extras)
 if p[0]: #The current element satisfies the given predicate.
 if type == "min":
 if best == default or lst[mid] < lst[best]: best = mid
 hi = mid-1
 elif type == "max":
 if best == default or lst[mid] > lst[best]: best = mid
 low = mid+1
 elif p[1] == 1: #For all `x` > `lst[mid]` not `P(x)`.
 hi = mid - 1
 elif p[1] == -1: #For all `x` < `lst[mid]` not `P(x)`.
 low = mid + 1
 return best
def pred_a(idx, lst, *extras):
 tpl, val = [None, None], lst[idx], 
 if extras: a, b = extras[0], extras[1]
 tpl[0] = a <= val < b 
 if val > b: tpl[1] = 1
 elif val < a: tpl[1] = -1
 return tuple(tpl)
def get_total_primes(a, b):
 low, hi = xbinsearch(pred_a, primes, a, b), xbinsearch(pred_a, primes, a, b, type="max")
 return hi + 1 - low

• Tobi Alafin: I figured out the problem with this question. It was literally a missing token (well I checked for > instead of >= in my upper bounds check because I thought it was an inclusive upper bound while it was in reality exclusive. Should I delete my question or answer it.
• 301_Moved_Permanently: You can answer it, there are more to improve than a change in comparison operator.
• Matthieu M.: Note: once you have determined low, high cannot possibly be before it... therefore only searching primes[low:] could be faster!

Answer 1

Please read PEP8 and apply its advice; this will make your code look like Python code to others. Mainly, avoid code blocks on the same line as their conditions, and avoid cramming too many assignments on the same line.

You can also make your predicate function return a single value, as the first element of the returned tuple can be computed from the second (mainly p[0] is p[1] is None). You could also use the more common values -1, 0 and 1 and add an else clause in your xbinsearch loop to raise an exception. This would have caught the case where val == b in your usage.

Lastly, bisect should be the module to reach for when dealing with binary search in Python. In fact, having your list of primes ready, the code should be:

def get_total_primes(a, b):
 low = bisect.bisect_left(primes, a)
 high = bisect.bisect_left(primes, b)
 return high - low

And if you ever want to include the upper bound, you can:

def get_total_primes_inclusive(a, b):
 low = bisect.bisect_left(primes, a)
 high = bisect.bisect_right(primes, b)
 return high - low