1
\$\begingroup\$

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())])
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.