Sum of all prime numbers between 1 and N in Python [Part 2]

user_10823585 0
Viewed 374

Just to clarify :) This is part 2 of my previous question. I'm posting a new question because the previous one got a bit messy and since I'm new to Stack, I'm still learning how things work here.

After implementing the suggestions, my previous code started working but the problem of Time Limit Exceed started occurring. I've tried my best to reduce the code, but TLE is still occurring. Here is my new code: 

from math import sqrt 
test = int(input())
for i in range(test):
    summ = 0
    maxx = int(input())
    if maxx==1:
        summ = 0
    elif maxx==2:
        summ += 2
    else:    
        summ = summ + 2
        for x in range(3,maxx+1,2):
            half = int(sqrt(x)) + 1
            for y in range(3,half,2):
                if x%y==0:
                    break
            else:    
                summ = summ + x  
    print(summ)

This time the code is producing the correct result. I just want to know how can I make my code more efficient and reduce Time Limit? TLE Image

python-3.x python
1 Answers

There are too many nested loops which increase the time complexity.

Here is a simple function which takes much less time.

import time

def sum_of_prime(n):
    prime =[]
    for num in range(2,int(n)):
        if all(num%i!=0 for i in range(2,num)):
            prime.append(num)
    return sum(prime[0:len(prime)])


n = input("Enter value of n:")
start = time.clock()
print(sum_of_prime(n))
print (time.clock() - start)
user_61673830
Related