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