TLE in APS - Amazing Prime Sequence in Python at Spoj

Question

This series is similar to Fibonacci Series defined as : a[0] = a[1] = 0 and For n > 1, a[n] = a[n - 1] + f(n), where f(n) is smallest prime factor of n. for N in (1 < N < 10^7). Spoj Link for this problem .

I have solved this problem in c & Python. But due to long range, I am getting Time Limit Exceeded in Python. For small range this is working fine. Is there any alternative way do this in Python or can this be more optimized.

lst = []
lst.append(0)
lst.append(0)
i = 2
while i <10000000 :
 t = 2
 while t <= i :
 if i % t == 0 :
 break
 t +=1
 lst.append(lst[i-1]+t)
 i +=1
for _ in range(int(input())):
 print(lst[int(input())])

Answer 1

The best way to solve this is to precompute the prime factors of n for n in range(1:10**7) I would suggest using a sieve of Eratosthenes.

def sieve5(n):
"""Return a list of the primes below n."""
prime = [True] * n
result = [2]
append = result.append
sqrt_n = (int(n ** .5) + 1) | 1 # ensure it's odd
for p in range(3, sqrt_n, 2):
 if prime[p]:
 append(p)
 prime[p*p::2*p] = [False] * ((n - p*p - 1) // (2*p) + 1)
for p in range(sqrt_n, n, 2):
 if prime[p]:
 append(p)
return result

Once you have the list of primes, you can just run the same type of algorithm you would for the fibs.