Codility

-lesson11

CountNonDivisible

def solution(A):

    N=len(A)
    result_li=[]
    length=2*N+1
    
    sieve=[0] * N 
    count=[0]* length   #1~ 2N index 에 접근 가능하도록. A의 element들의 갯수 담을 배열
    saved=[0]*length
    for i in A:
        count[i]+=1


    for num in range(0,N): #1 ~ 2N 까지 약수개수 담기위해
        e=A[num]
        if saved[e]!=0:
            continue


        for i in range(1,int(e**0.5)+1): #1 ~ 재곱근 까지
            if e%i==0:
                sieve[num]+=count[i]
                if e//i!=i:
                    sieve[num]+=count[e//i]

        
        saved[e]=sieve[num] #약수 개수 저장
        re=N-sieve[num]
        
        result_li.append(re)
            




    return result_li