TLE in APS - Amazing Prime Sequence in Python at Spoj
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.