Skip to main content
Commonmark migration
Source Link

Prime sieve

#Prime sieve I'mI'm not an expert of prime sieves however I guess your implementation is very inefficient therefore here's the common implementation:

#Prime sieve I'm not an expert of prime sieves however I guess your implementation is very inefficient therefore here's the common implementation:

Prime sieve

I'm not an expert of prime sieves however I guess your implementation is very inefficient therefore here's the common implementation:

deleted 4 characters in body
Source Link
user203258
user203258
def get_longest_prime_sum(upper_bound):
    """Return sum of the longest prime sequence in range upper_bound exclusive."""
    primes = sieve(upper_bound)
    count = 1
    high = 0
    length = len(primes)
    while count <= length: 
        i = 0
        while(i<(length-count)):
            sub = primes[i:i+count]
            subSum = sum(sub)
            if(subSum < 1000000):
                if(subSum in primes):
                    if(subSum>high):
                        high = subSum
                    break
                else: 
                    i+=1
            else:
                break
        count += 1
        return high
def get_longest_prime_sum(upper_bound):
    """Return sum of the longest prime sequence in range upper_bound exclusive."""
    primes = sieve(upper_bound)
    count = 1
    high = 0
    length = len(primes)
    while count <= length: 
        i = 0
        while(i<(length-count)):
            sub = primes[i:i+count]
            subSum = sum(sub)
            if(subSum < 1000000):
                if(subSum in primes):
                    if(subSum>high):
                        high = subSum
                    break
                else: 
                    i+=1
            else:
                break
        count += 1
        return high
def get_longest_prime_sum(upper_bound):
    """Return sum of the longest prime sequence in range upper_bound exclusive."""
    primes = sieve(upper_bound)
    count = 1
    high = 0
    length = len(primes)
    while count <= length: 
        i = 0
        while(i<(length-count)):
            sub = primes[i:i+count]
            subSum = sum(sub)
            if(subSum < 1000000):
                if(subSum in primes):
                    if(subSum>high):
                        high = subSum
                    break
                else: 
                    i+=1
            else:
                break
        count += 1
    return high
Source Link
user203258
user203258

** This is not a full review but I will try to tackle some important points.

Import statements

def sieve(num):
    primes = []
    import math

According to pep8 https://www.python.org/dev/peps/pep-0008/ the official Python style guide: Imports are always put at the top of the file, just after any module comments and docstrings, and before module globals and constants, not inside a function like in the case of your sieve function.

#Prime sieve I'm not an expert of prime sieves however I guess your implementation is very inefficient therefore here's the common implementation:

def sieve(upper_bound):
    primes = [True] * upper_bound
    primes[0] = primes[1] = False

    for i, prime in enumerate(primes):
        if prime:
            yield i
            for n in range(i * i, upper_bound, i):
                primes[n] = False

You might try running your version of sieve and this one, they run in the following times when I ran the test on both on my i5 macbook pro for a 10 ** 7 input size:

Time: 18.267110993 seconds. (your version)

Time: 2.6265673870000015 seconds. (the other version)

you might want to try running the test yourself and see the results.

Functions

You use functions in programming to bundle a set of instructions that you want to use repeatedly or that, because of their complexity, are better self-contained in a sub-program and called when needed. That means that a function is a piece of code written to carry out a specified task. To carry out that specific task, the function might or might not need multiple inputs. When the task is carried out, the function can or can not return one or more values. Therefore we can enclose the following piece of code inside a function.

primes = sieve(1000000)
count = 1
high = 0
length = len(primes)
while count <= length: 
    i = 0
    while(i<(length-count)):
        sub = primes[i:i+count]
        subSum = sum(sub)
        if(subSum < 1000000):
            if(subSum in primes):
                if(subSum>high):
                    high = subSum
                break
            else: 
                i+=1
        else:
            break
    count += 1
print(high)

In the following way:

def get_longest_prime_sum(upper_bound):
    """Return sum of the longest prime sequence in range upper_bound exclusive."""
    primes = sieve(upper_bound)
    count = 1
    high = 0
    length = len(primes)
    while count <= length: 
        i = 0
        while(i<(length-count)):
            sub = primes[i:i+count]
            subSum = sum(sub)
            if(subSum < 1000000):
                if(subSum in primes):
                    if(subSum>high):
                        high = subSum
                    break
                else: 
                    i+=1
            else:
                break
        count += 1
        return high

The rest of the code:

unfortunately, I couldn't get myself to have enough patience to wait for 200 seconds to examine what the code actually does however here's a link to my own implementation to the same problem: Project Euler # 50 Consecutive prime sum in Python

Note *** this is not the most optimal solution

However it returns the right answer in almost 2 seconds, so you can examine how I implemented it and you will find a very useful review below my code, you might check it to give you some insights on other ways of solving the same problem.