3

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

SySu
  • 619
  • 1
  • 7
  • 15
  • you should use a prime sieve (google it there are many implementations...) unfortunately however SO is not really for improving runtimes ... you might want to try codereview.stackexchange – Joran Beasley Dec 27 '18 at 06:17
  • provide sample input and expected output. – varatharajan Dec 27 '18 at 06:30
  • Possible duplicate of [How do I find the sum of prime numbers in a given range in Python 3.5?](https://stackoverflow.com/questions/36251137/how-do-i-find-the-sum-of-prime-numbers-in-a-given-range-in-python-3-5) – Alexei Levenkov Dec 27 '18 at 06:31
  • Very detailed explanation is in [Euler 10 - sum of primes](https://stackoverflow.com/questions/36830418/project-euler-10-sum-of-primes) post - please read it carefully. I don't believe you can get solution you are trying to optimize to be accepted on Project Euler (or anywhere else). – Alexei Levenkov Dec 27 '18 at 06:33
  • one way to optimize prime checking is to limit your factors to only the primes that are smaller than the one you just found, if you are already calculating all of the primes up to a certain number then there is no downsize – AntiMatterDynamite Dec 27 '18 at 07:59

1 Answers1

1

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)
Aravind
  • 534
  • 1
  • 6
  • 18