Python: Reduce runtime?

user_12984751 0
Viewed 180

I recently started to learn python and i'm using CodeWars to train. The task is to return a list [p, p + 4, p + 6, p + 10, p + 12, p + 16] where all of them are primes. The sum of them should be higher than sum_limit. For low values it is working, but at high values (about 2 million) the runtime is high. How can I reduce the runtime? 

from math import sqrt; from itertools import count, islice

def find_primes_sextuplet(sum_limit):
    for x in range(sum_limit):
        if isPrime(x) and isPrime(x+4) and isPrime(x+6) and isPrime(x+10) and isPrime(x+12) and isPrime(x+16):
            possible = [x, x+4, x+6, x+10, x+12, x+16]
            if sum(possible) > sum_limit:
                return possible


def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))


print(find_primes_sextuplet(2000000))
runtime python
3 Answers

For non-negative integer values of n, you can use this:

def isPrime(n):
    if n == 1 or n % 2 == 0 or n % 3 == 0:
        return False

    end = int(sqrt(n)+1)
    for start in [5, 7]:
        for k in range(start, end, 6):
            if n % k == 0:
                return False

    return True

It won't change the theoretical complexity, but it will reduce the practical running-time.

And if you change the outer loop to for x in range(5, sum_limit), then you can also get rid of the initial check if n == 1 or n % 2 == 0 or n % 3 == 0.

user_74009030

There are various ways to improve the runtime of your code. For example a lot of numbers are checked for being prime numbers even though their sum is not eligible as a result. Calculating the sum of 6 numbers is faster than checking if they are prime. You could move the sum check above the prime check and only check the numbers for primes if their sum would be eligible.

To improve this further you could skip numbers which will not result in an eligible sum by starting the range at the floor of possible numbers.

x + x + 4 + x + 6 + x + 10 + x + 12 + x + 16 = 6x + 48

which is supposed to be above your sum_limit

6x + 48 >= sum_limit
x >=(sum_limit - 48) / 6

So if your range starts at x you will skip all numbers which would not result in an eligible sum anyway. You would also be able to improve runtime by skipping even numbers in your loop(via range(y,x,2)). Further improving the runtime would require you to adjust the isPrime function.

user_106133970

Here's my thinking about reducing complexity and run time.

You can write a sieve in O(n log log n). Here's a reasonable implementation:

def sieve(n):
    grid = [None for _ in range(n+1)]
    i = 2
    while i < n+1:
       if grid[i] is None:
           grid[i] = True
           for p in range(2*i, n+1, i):
               grid[p] = False
       else:
           i += 1
    return (index for index, b in enumerate(grid) if b)

There are 6 numbers, and the total amount added to the first number is 48. So the minimum possible value for the first number is (n - 48) / 6. In my sieve we can iterate the generator until number is greater than that.

def get_remaining_sieve(n):
    g = sieve(n)
    current = next(g)
    min_value = (n - 48) / 6
    while current < min_value:
        current = next(g)
    return [current] + list(g)

Now just iterate through every slice of length 6, and check if the separation matches the desired separation (4, 2, 4, 2, 4).

remaining = get_remaining_sieve(n)
for start in range(len(remaining) - 5):
    slice = remaining[start:start+6]
    differences = [slice[j] - slice[j-1] for j in range(1, 6)]
    if differences == [4, 2, 4, 2, 4]:
        print(slice)

Summary

Based on those principles, I've come up with this solution:

from itertools import dropwhile, islice
def get_solutions(n):
    grid = [None for _ in range(n+1)]
    i = 2
    while i < n+1:
        if grid[i] is None:
            grid[i] = True
            for p in range(2*i, n+1, i):
                grid[p] = False
        else:
            i += 1
    sieve = (index for index, b in enumerate(grid) if b)
    min_value = (n - 48) / 6
    reduced_sieve = dropwhile(lambda v: v < min_value, sieve)
    reference_slice = list(islice(reduced_sieve, 6))
    while True:
        try:
            ref = reference_slice[0]
            differences = [v - ref for v in reference_slice[1:]]
            if differences == [4, 6, 10, 12, 16]:
                yield reference_slice
            reference_slice = reference_slice[1:] + [next(reduced_sieve)]
        except StopIteration:
            break


n = 2000000
print(next(get_solutions(n)))  # 695ms

# or for all solutions
for solution in get_solutions(n):  # 755ms
    print(solution)

This runs in less than a second on my computer.

user_19041460
Related