Super B primes in range

Question

So I have this problem involving Super B primes. Super B prime is basically this.

If n- is prime
And sum of digits in n is prime
And sum of digits in binary(n) is prime

Then n is Super B prime. E.g.

41-is prime
4+1=5 -is prime
41(10)=101001(2) is 1+0+1+0+0+1=3 -is prime

=======

So 41 is Super B prime.

The problem is that I have to print every Super B Prime in range(a,b) and what I have now exceeds the time limit by alot. How can I improve it?

import math
from functools import lru_cache
@lru_cache()
def is_prime(n):
    if n<1:
        raise ValueError("Must be positive integer")

    elif n>1:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
        return True
@lru_cache()
def dec_to_binary(n):
    return int(bin(n)[2:])

a,b = map(int,input().split())
for i in range(a, b+1):
    l=0
    k=0
    for m in str(i):
        l=l+int(m)
    for o in str(dec_to_binary(i)):
        k=k+int(o)

    if is_prime(i) and is_prime(l) and is_prime(k):
        print(i)

This rather sounds like a case for [CodeReview](https://codereview.stackexchange.com/) — Mr. T, Dec 28 '17 at 20:14
But an obvious time improvement would be to test for divisibilty of 2 separately and then 3 + step 2. And why not store primes in a list and look them up instead of testing the same number several times? — Mr. T, Dec 28 '17 at 20:20
`is_prime(i)` should be the last check as it is by far the most expensive — user2390182, Dec 28 '17 at 20:23

user2390182 · Answer 1 · 2017-12-28T20:55:01.750

Several issues: Firstly, your prime check checks way too many numbers. The following implementation (derived from this answer) is a decent trade-off between not diving into serious advanced math and not entirely stupid brute-forcing:

@lru_cache()
def is_prime(n):
    """Returns True if n is prime."""
    if n in (2, 3):
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i, w = 5, 2
    while i * i <= n:
        if n % i == 0:
            return False
        i, w = w + i, 6 - w
    return True

Secondly, you should do the cheap checks (primality of the much smaller digit sums) first and only do the primality check of the number itself if the others pass:

def bin_sum(n):
    return sum(map(int, '{0:b}'.format(n)))

def digit_sum(n):
    return sum(map(int, str(n)))

a, b = map(int, input().split())

for n in range(a, b + 1):
    # cheapest checks first
    if is_prime(bin_sum(n)) and is_prime(digit_sum(n)) and is_prime(n):
        print(n)

Super B primes in range

So 41 is Super B prime.

1 Answers1