Problem: Given is a number sequence A of length N.  Find the number of integers i \left(1 \leq i \leq N\right) with the following property:    * For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Submission attempts (in order):
def d170(n,a):
    sa=sorted(a)
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in sa:
            if dp[x]==0:
                for j in range(x,n):
                    if j%x==0:
                            dp[j]+1
        return dp.count(1)
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))
            

def d170(n,a):
    sa=sorted(a)
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in sa:
            if dp[x]==0:
                for j in range(x,n):
                    if j%x==0:
                            dp[j]+=1
        return dp.count(1)
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))
            

def d170(n,a):
    count=0
    sa=sorted(a)
    dp=[True for i in range(n)]
    return dp.count(True)
    
n=int(input())
a= list(map(int, input().split()))    
print(d170(n,a))
            

n=int(input())
a= list(map(int, input().split()))    
t=set([x for x in set(a) if a.count(x)>1])
print(0)
    

def d170(n,a):
    count=0
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in a:
            if dp[x]!=0:
                dp[x]=2
            else:
                for j in range(x,max(a)+1,x):
                        dp[j]+=1
        for x in sa:
            if dp[x]==1:
                count+=1
        return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))
            

def d170(n,a):
    count=0
    sa=sorted(list(set(a)))
    if sa[0]==1:
        if 1 in t:
            return 0
        else:
            return 1
    else:
        for i in range(sa) :
            if i>=len(sa):
                break
            else:
                p=sa[i]
                k=[]
                for j in range(i+1,len(sa)):
                     if sa[j]%p==0:
                        k.append(sa[j])
                sa=sorted(list(set(sa)-set(k)))
        return len(set(sa))
    
n=int(input())
a= list(map(int, input().split()))    
print(d170(n,a))
            

def d170(n,a):
    count=0
    sa=sorted(list(set(a)))
    print(sa)
    t=set([x for x in set(a) if a.count(x)>1])
    if sa[0]==1:
        if 1 in t:
            return 0
        else:
            return 1
    else:
        for i in range(len(sa)) :
            if i>=len(sa):
                break
            else:
                p=sa[i]
                k=[]
                for j in range(i+1,len(sa)):
                     if sa[j]%p==0:
                        k.append(sa[j])
                sa=sorted(list(set(sa)-set(k)))
        print(sa)
        return len(set(sa)-t)
    
n=int(input())
a= list(map(int, input().split()))    
print(d170(n,a))
            

def d170(n,a):
    count=0
    sa=sorted(a)
    dp=[True for i in range(n)]
        return dp.count(True)
    
n=int(input())
a= list(map(int, input().split()))    
print(d170(n,a))
            

def d170(n,a):
    k=max(a)+1
    count=0
    dp=[0 for i in range(k)]
    for x in a:
        if dp[x]!=0:
                dp[x]=2
                
        else:
            for j in range(x,k,x):
                     dp[j]+=1
    for x in a:
        if dp[x]==1:
            count+=1
    return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))
            

Verdicts: Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Accepted