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