CODEWITHSUNDEEP
pythonpython-3.xalgorithmnumber-theory
JerSci
JerSci

Reputation: 197

How can i make my code run faster for large values(upto 100 million)?

Okay so background: I'm solving a question which requires me to find a number 'n' such that n-9, n-3, n+3, n+9 are consecutive prime numbers and n-8, n-4, n+4, n+8 are practical numbers and then I have to add the first four n that satisfy this condition.

The problem: Whether the logic of the code is correct or incorrect is irrelevant here because my code crashes before it reaches 100 million. I can't even check the output of the code, it works fine for 1million but doesn't scale to well for larger numbers.

What i did: I used the sieve of erath... to get the prime numbers up to 100 million which we will call M. And since practical numbers are divisible by 6 or by 4, I created another set to store those numbers and from that list i then created a set that contained the numbers that satisfy this condition: 'n-8, n-4, n+4, n+8 are practical numbers' which we will call N. Finally I iterate through each element, a, in N and check whether a - 9, a - 3, a + 3, a + 9 are part of the prime number set.

If anyone has any tips on how i can speed this up or any better algorithms it would be greatly appreciated

code

def SieveOfEratosthenes(n):
    m = set()
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    prime[0]= False
    prime[1]= False
    for p in range(n + 1):
        if prime[p]:
            m.add(p)
    return m

#creates set that stores multiples of 4 and 6

def ps1(n):
    s = set()
    for i in range(1, n+1):
        if i%4 == 0 and i%6 == 0:
            s.add(i)
    return s

#checks whether any number satisfies n -8, n-4, n+4, n+8 must be practical and stores it in a set

def ps2(l):
    q = set()
    for i in l:
        if ((i-8) in l) and ((i-4) in l) and ((i+4) in l) and ((i+8) in l):
            q.add(i)
    return q

#using the numbers stored in the prev set, i check the last condition n-9, n-3, n+3, n+9 must be in the 
prime list
def TotalSieve(k, l):
    q = set()
    inc = 0
    for i in k:
        if inc != 4:
            if ((i-9) in l) and ((i-3) in l) and ((i+3) in l) and ((i+9) in l):
                inc = inc + 1
                q.add(i)
        else:
            print("Found 4")
    return q
                                                                       
# driver program
if __name__=='__main__':
    n = 1000000000
    m = SieveOfEratosthenes(n)
    p = ps1(n)
    p = ps2(p)
    f = TotalSieve(p, m)
    elem1 = f.pop()
    elem2 = f.pop()
    elem3 = f.pop()
    elem4 = f.pop()
#add the first four numbers that satisfy the conditions
    tot = elem1 + elem2 + elem3 + elem4
    print(tot)

Upvotes: 0

Views: 140

Answers (1)

user58697
user58697

Reputation: 7923

First, ps1 is wrong. The test should say or, not and.

Next, if n is divisible by 4, all n-8, n-4, n+4, n+8 are also divisible by 4. If n is not divisible by 4, none of them are divisible by 4, and some of them are also not divisible by 4. Which means you are only interested in n being a multiple of 4.

Finally, I know that this problem implies some serious number-theoretical homework. Brute force wouldn't do it.

Upvotes: 1

Related Questions