Problem regarding TLE in KPRIME problem

limit = 10 ** 5 + 1
dp = [0 for i in range(limit)]
for i in range(2, limit):
if(dp[i] != 0): continue
for j in range(i, limit, i):
dp[j] += 1
mat1 = [(x-1) for x in dp]
mat2 = [(x-2) for x in dp]
mat3 = [(x-3) for x in dp]
mat4 = [(x-4) for x in dp]
mat5 = [(x-5) for x in dp]
ans=[mat1,mat2,mat3,mat4,mat5]
t = int(input())
for i in range(0,t):
a, b, k = map(int, input().split(" "))
print(ans[k-1][a:b+1].count(0))I

I have written in code for the KPRIME problem. After checking it on local ide i found that it was very quick and efficient yet codechef on submission is showing TLE. Please do point out what i am doing wrong.

Check the following update to your code.

Accepted Python

Let dp[x][y] be equal to the number of y-prime positive integers less than or equal to x,
where 1 <= x <= 100,000 and 0 <= y <= 5. The query-processing loop then answers each query in O(1) time using the following simple integer subtraction operation.

answer(A,B,K) = dp[B][K] - dp[A-1][K]

The two-dimensional array dp[x][y] can be computed using sieve algorithm for prime-number factorization.

The following is recursive C++14 implementation of this DP approach.

Accepted C++14

1 Like

Can you compare the entire time complexity of my program with the answer you have given ? I would like to know.

The time-complexity for answering each query in your program is definitely not O(1), as the function call ans[k-1][a:b+1].count(0) can perform up to O(N) iterations to count the number of items. For T queries, the time-complexity of your program is at least O(T\times N).

Check the following alternative update to your code.

Accepted

1 Like

Thank you very much