Find length of the smallest subarray whose product has atleast K prime factors

general
, ,
1

Here is my attempt which didn’t work. Could anyone guide how to proceed with it?

import sys
import math
from collections import defaultdict
def sieve(n):
    prime=[True for j in range(n+1)]
    i=2
    while( i*i<=n):
        if prime[i]:
            for j in range(i*i,n+1,i):
                prime[j]=False
        i+=1
    primeset=[]
    for j in range(2,n+1):
        if prime[j]:
            primeset.append(j)
    return primeset
prime=sieve(1000001)
def solve(backlog,new,curr):
    
    for j in prime:
        if j <=new and new%j==0:
            if backlog[j]==0:
                curr+=1
            backlog[j]+=1
        if j>new:
            break
         
    ans=curr
            
    return [ans,backlog]

def remove(backlog,new,curr):
    
    for j in prime:
        if j <=new and new%j==0:
                    backlog[j]-=1
                    if backlog[j]==0:
                        curr-=1
        if j>new:
            break
    ans=curr
    return [ans,backlog]


        


def minSubarray(K, Arr):
    
    curr=0
    minlen=1000000000
    start=0
    end=0
    backlog=defaultdict(int)
    n=len(Arr)
    while (end<n):
        
        while (curr<K and end<n):
            
            ans=solve(backlog,Arr[end],curr)
            #print(backlog,Arr[end])
            curr,backlog=ans[0],ans[1]
            end+=1
        while(curr>=K and start<end):
            minlen=min(minlen,end-start)
            #print(backlog,Arr[start],'fuck')
            ans=remove(backlog,Arr[start],curr)
            curr,backlog=ans[0],ans[1]
            start+=1
    if minlen==1000000:
        return -1
    return minlen



def main():
    N = int(sys.stdin.readline().strip())
    K = int(sys.stdin.readline().strip())
    Arr = []
    for _ in range(N):
        Arr.append(int(sys.stdin.readline().strip()))
    result = minSubarray(K, Arr)
    print(result)
if __name__ == "__main__":
    main()