python solution in codewars could not pass time limit, needs optimization

Question

There is a question on codewars, life without primes. I solved it yet the time issue comes up. I really cannot find a better way. The instructions go like;

Consider an array that has no prime numbers, and none of its elements has any prime digit. It would start with: [1,4,6,8,9,10,14,16,18,..]. The element at index 1 is 4.

There will be given an integer n and the task will be return the number at that index in the array. For example, solve(1) = 4, as explained above.

Here is my solution

def solve(n):
    no_primes=[]
    a=1
    if n == 1:
        return 4
    else:
        while True:
            try:
                no_primes[n]
                break
            except IndexError:
                if is_prime(a) == True:
                    if is_num_prime(a) == False:
                        no_primes.append(a)
                a=a+1
        return no_primes[n]

def is_prime(num):
    numbers = list(map(int, list(str(num))))
    #primes=[0,2,3,5,7,9]
    non_primes=[0,1,4,6,8,9]
    return all(list(map(lambda x:x in non_primes,numbers)))

def is_num_prime(num):
    if num == 2:
        return True
    elif num >2:
        for i in range(2,num):
            if num%i == 0:
                return False
        else:
            return True
    else:
        return False

Getting rid of the while loop could help but I need to keep on appending until I can reach the value from the list. A recursive for loop with using range(1,n) where n increases recursively may be an option but I could not write it anyways.

there should be way more efficient ways to check whether a number is prime than yours. start the for-loop at 3 instead of 2, and increment in steps of 2. Run the for-loop until the squareroot of num are 2 things which will immensely speed this up. — Maarten Fabré
– Maarten Fabré, Commented Nov 2, 2017 at 9:19
another thing that slows this down is you evaluating the generators (list(map(int, list(str(num))))) while it is not needed. If your next step takes an iterable as input, there is no need for this — Maarten Fabré
– Maarten Fabré, Commented Nov 2, 2017 at 9:56

Maarten Fabré · Accepted Answer · 2017-11-02 09:55:29Z

2

You can easily break down this problem in simple steps:

Generate the all the combinations

You can make an endless generator making ever-longer combinations of these digits

def generate_numbers():
    digits= '014689'
    for i in itertools.count(1): # ever longer number
        for x in itertools.product(digits, repeat=i): # combine the digits
            number = ''.join(x)
            if number[0] != '0':
                yield int(number)

print(list(itertools.islice(generate_numbers(), 40)))

[1, 4, 6, 8, 9, 10, 11, 14, 16, 18, 19, 40, 41, 44, 46, 48, 49, 60, 61, 64, 66, 68, 69, 80, 81, 84, 86, 88, 89, 90, 91, 94, 96, 98, 99, 100, 101, 104, 106, 108]

Check whether a number is prime

def is_prime(num):
    if num in {0, 1,}:
        return False
    if num == 2:
        return True
    if not (num % 2):
        return False
    for i in range(3, round(num **.5 + 1), 2):
        if not (num % i):
            return False
    return True

return the `n`th non-prime number

def solve(n):
    non_prime_solutions = (i for i in generate_numbers() if not is_prime(i))
    return next(itertools.islice(non_prime_solutions, n, None))

[solve(i) for i in (1, 2, 10, 100)]

[4, 6, 44, 644]

Since all of this is lazily evaluated, this should go pretty fast. The one thing that can be optimised is the is_prime

answered Nov 2, 2017 at 9:55

Maarten Fabré

7,0781 gold badge19 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Fırat Uyulur Over a year ago

Generating a combination list of those numbers is a great idea.

Fırat Uyulur Over a year ago

I both tried your version of solution and my modified version(which I only changed the is_num_prime to your is_prime) and both worked. Thanks!

score 1 · Accepted Answer · 2017-11-02 11:33:44Z

1

import math
import itertools

def is_prime(n):
    return all(n % i for i in range(2, int(math.sqrt(n) + 1)))

prime_digits = {"2", "3", "5", "7"}
def no_prime_digit(n):
    return not any(x in prime_digits for x in str(n))

def non_primes():
    return (i for i in itertools.count() if no_prime_digit(i) and not is_prime(i))

def get_non_prime(n):
    return next(x for i, x in enumerate(non_primes()) if i == n - 1)

print([(x, get_non_prime(x)) for x in [1, 10, 100]])

edited Nov 2, 2017 at 11:33

answered Nov 2, 2017 at 10:03

user3278460

2 Comments

Maarten Fabré Over a year ago

you could use a set instead of a list for the in ["2", "3", "5", "7"]. Making it a global variable might speed things up too, preventing from having to instantiate this list all the time

Maarten Fabré Over a year ago

using not any(x in {"2", "3", "5", "7"} for x in str(n)) is an alternative for the no_prime_digit

Collectives™ on Stack Overflow

python solution in codewars could not pass time limit, needs optimization

2 Answers 2

Generate the all the combinations

Check whether a number is prime

return the `n`th non-prime number

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Generate the all the combinations

Check whether a number is prime

return the nth non-prime number

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related

return the `n`th non-prime number