How do I reduce the execution time for the following code

Question

n=int(input(" enter the limiting value"))
sum=0
for i in range(1,n+1):
c=0
for j in range(1,i+1):
if i%j==0:
c+=1
if c==2:
sum+=i

print("sum of all prime numbers upto ", n ,"is ",sum)

It takes a lot of time for any value of n entered greater than 5000 pls help

Answer 1

Hi.

You can use j only in range (1, i//2+1). Any number greater than half of i will return a value below 2 but greater 1, ergo no prime. Also, skip any even number. These are definitely no prime, except 2. i in range(1, n, 2) (not validated, pls check before using)
This should help somewhat. You could also check into parallel implementation, there are no sync points in between needed. Sum up at the end.

Hope this helps. Cheers. C.