TLE in APS - Amazing Prime Sequence in Python at Spoj This series is similar to Fibonacci Series defined as : a[0] = a[1] = 0  and For n &gt; 1, a[n] = a[n - 1] + f(n), where f(n) is smallest prime factor of n.
for N in (1 &lt; N &lt; 10^7). Spoj Link for this problem . 

I have solved this problem in c &amp; 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 &lt;10000000 :
    t = 2
    while t &lt;= 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())])
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.