Problem:


Score : 400 points

Problem Statement

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.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N = int(input())
    A = sorted([int(a) for a in input().strip().split()])
    Acnt = Counter(A)
    if 1 in A:
        print(A.count(1))
        return True

    max_A = max(A)
    f = [True] * (max_A + 1)
    ans = 0
    for i in range(2, max_A + 1):
        if Acnt[i] > 0 and f[i]:
            if Acnt[i] == 1:
                ans += 1
            j = 1
            k = i
            while k <= max_A:
                f[k] = False
                j += 1
                k = i * j

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N = int(input())
    A = sorted([int(a) for a in input().strip().split()])
    Acnt = Counter(A)
    if 1 in A:
        print(A.count(1))
        return True

    max_A = max(A)
    f = [True] * (max_A + 1)
    ans = 0
    for i in range(2, max_A + 1):
        if Acnt[i] > 0 and f[i]:
            if Acnt[i] == 1:
                ans += 1
            j = 2
            k = i * j
            while k <= max_A:
                f[k] = False
                j += 1
                k = i * j

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [int(i) for i in input().split()]
from collections import defaultdict
dict_A = defaultdict(int)
for a in A:
  dict_A[a] += 1
A = []
for key in dict_A.keys():
  if dict_A[key] == 1:
    A.append(key)
A = sorted(A)
from collections import deque
Q = deque(A)
ans = 0
while Q:
  q = Q.popleft()
  ans += 1
  temp_Q = deque([])
  while Q:
    r = Q.popleft()
    if r%q!=0:
      temp_Q.append(r)
  Q = temp_Q
print(ans)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    #s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if 2*i > len(dp)-1:
            None
        elif dp[2*i] == 0:
            None
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    #s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if 2*i > len(dp)-1:
            pass
        elif dp[2*i] == 0:
            pass
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    #s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if 2*i > len(dp)-1:
            pass
        elif dp[2*i] == 0:
            pass
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    if len(l_a) == 1:
        count = 0
    print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
from collections import defaultdict
dict_A = defaultdict(int)
for a in A:
  dict_A[a] += 1
A = []
for key in dict_A.keys():
  if dict_A[key] == 1:
    A.append(key)
A = sorted(A)
from collections import deque
Q = deque(A)
ans = 0
while Q:
  q = Q.popleft()
  ans += 1
  temp_Q = deque([])
  while Q:
    r = Q.popleft()
    if r%q!=0:
      temp_Q.append(r)
  Q = temp_Q
print(ans)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if 2*i > len(dp)-1:
            pass
        elif dp[2*i] == 0:
            pass
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    if len(l_a) == 1:
        count = 0
    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = sorted(list(map(int,input().split())))

num = max(l)+1

rcd = [0 for _ in range(num)]

for i in l:
    for j in range(1, num):
        if i == j and rcd[j] == 2:
            break

        if j % i == 0:
            if rcd[j] == 2:
                break
            else:
                rcd[j] += 1
        else:
            continue

ans = 0
for k in l:
    if rcd[k] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
ans = 0
for a in A:
  flag = True
  for i in range(len(A)):
    if a % A[i] == 0:
      flag = False
  if flag:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = sorted(list(map(int,input().split())))

num = max(l)+1
rcd = [0 for _ in range(num)]

for i in l:
    for j in range(1, num):
        if i == j and rcd[j] == 2:
            break

        if j % i == 0:
            if rcd[j] == 2:
                break
            else:
                rcd[j] += 1
        else:
            continue

ans = 0
for k in l:
    if rcd[k] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
array = list(map(int,input().split()))
if sum(array)/N == array[0]:
    print(0)
    exit()
new_array = []
for i in range(N):
    for j in range(N):
        if i != j:
            device = array[i] % array[j]
            if (device == 0) and (array[i] // array[j]>=1):
                new_array.append(True)
                break

print(N-len(new_array))

Submission status: Wrong Answer

Solution code:
N = int(input())
array = [int(x) for x in input().split()]
if sum(array)/N == array[0]:
    print(0)
    exit()
new_array = []
for i in range(N):
    for j in range(N):
        if i != j:
            device = array[i] % array[j]
            if (device == 0) and (array[i] // array[j]>=1):
                new_array.append(True)
                break

print(N-len(new_array))

Submission status: Wrong Answer

Solution code:
N = int(input())
array = [int(x) for x in input().split()]
if sum(array)/N == array[0]:
    print(0)
    exit()

Submission status: Wrong Answer

Solution code:

# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
couter =Counter(A)
multiple =set()
for a in A_set:
    if couter[a] >=2:
        multiple.add(a)
        continue
    elif a in multiple:
        continue
    else:
        for i in range(2,10**6+1):
            if i*a  in A_set:
                multiple.add(i*a)
            elif i*a > 10**6 :
                break
if couter[1] >=2:
    ans =0
else:
    ans =len(A_set - multiple)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = sorted(list(map(int,input().split())))

num = max(l)+1
rcd = [0 for _ in range(num)]

for i in l:
    for j in range(1, num):
        if j % i == 0:
            if rcd[j] <= 1:
                rcd[j] += 1
            else:
                break
        else:
            continue

ans = 0
for k in l:
    if rcd[k] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
array = [int(x) for x in input().split()]
if sum(array)/N == array[0]:
    print(0)
    exit()
new_array = []
for i in range(N):
    for j in range(N):
        if i != j:
            device = array[i] % array[j]
            if (device == 0) and (array[i] // array[j]>=1):
                new_array.append(True)
                break
count = 0
for x in new_array:
    if x == True:
        count+=1
print(N-count)

Submission status: Wrong Answer

Solution code:
vN = int(input())
A = list(map(int,input().split()))
A.sort()
L = [1] * (max(A) + 1)
duplist = list()
ret = 0
for i in range(len(A)):
    if L[A[i]] == 1:
        if A[i] in duplist:
            continue
        elif i < len(A) - 1 and A[i] == A[i+1]:
            duplist.append(A[i])
        else:
            ret += 1
            num = 2
            while True:
                if A[i] * num > len(L) - 1 :
                    break
                L[A[i] * num] = 0
                num += 1
    
print(ret)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
L = [1] * (max(A) + 1)
duplist = list()
ret = 0
for i in range(len(A)):
    if A[i] in duplist:
        continue
    elif i < len(A) - 1 and A[i] == A[i+1]:
        duplist.append(A[i])
    elif L[A[i]] == 1:
        ret += 1
        num = 2
        while True:
            if A[i] * num > len(L) - 1 :
                break
            L[A[i] * num] = 0
            num += 1
    
print(ret)

Submission status: Wrong Answer

Solution code:

# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
couter =Counter(A)
multiple =set()
for a in A_set:
    if couter[a] >=2:
        multiple.add(a)
        continue
    elif a in multiple:
        continue
    else:
        for i in range(2,10**6):
            #if i*a  in A_set:
            multiple.add(i*a)
            if i*a >10**6 +1:
                break
if couter[1] >=2:
    ans =0
else:
    ans =len(A_set - multiple)
print(ans)

Submission status: Wrong Answer

Solution code:

# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
couter =Counter(A)
multiple =set()
for a in A_set:
    if couter[a] >=2:
        multiple.add(a)
        continue
    elif a in multiple:
        continue
    else:
        for i in range(2,10**6):
            if i*a  in A_set:
                multiple.add(i*a)
            elif i*a >10**6 +1:
                break
if couter[1] >=2:
    ans =0
else:
    ans =len(A_set - multiple)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

def main():
  N = int(input())
  A = list(map(int, input().split()))
  A.sort()
  devide = sorted(set(A), key=A.index)
  target = copy.copy(devide)
  target.reverse()
  
  length_devide = len(devide)  
  if length_devide == 1:
    print(0)
    exit()
    
  i = 0
  while i < length_devide:
    j = 0
    length_target = len(target)
    while j < length_target:
      if devide[i] > target[j]:
        break
      elif devide[i] == target[j]:
        j += 1
      elif target[j] % devide[i] == 0:
        del(target[j])
        length_target -= 1
      else:
        j += 1
    i += 1
  print(len(target))
    
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
couter =Counter(A)
multiple =set()
for a in A_set:
    if couter[a] >=2:
        multiple.add(a)
        continue
    elif a in multiple:
        continue
    else:
        for i in range(2,10**6):
            if i*a  in A_set:
                multiple.add(i*a)
            elif i*a >10**6 +1:
                break
ans =len(A_set - multiple)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

def main():
  N = int(input())
  A = list(map(int, input().split()))
  A.sort()
  devide = sorted(set(A), key=A.index)
  target = copy.copy(devide)
  
  length_devide = len(devide)  
  if length_devide == 1:
    print(0)
    exit()
    
  i = 0
  while i < length_devide:
    j = 0
    length_target = len(target)
    while j < length_target:
      if devide[i] > target[j]:
        break
      elif devide[i] == target[j]:
        j += 1
      elif target[j] % devide[i] == 0:
        del(target[j])
        length_target -= 1
      else:
        j += 1
    i += 1
  print(len(target))
    
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))


A.sort(reverse=True)
S=0
if len(set(A)) == 1:
    print(int(0))

else:
    for i in set(A):
        for j in set(A):
            if i%j==0 and i!=j:
                S+=1
                break

    print(int(N-S))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    is_divable = [True]*(n)
    for i in range(len(a)):
        if is_divable[i]:
            k = i+1
            while k < n:
                if a[k]%a[i] == 0:
                    is_divable[k] = False
                k+=1
    ans = is_divable.count(True)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()

num_tmp = [0]*(10**6+1)

for a in A:
    if num_tmp[a] == 1:
        num_tmp[a] = 2
        continue
    for tmp in range(a,10**6+1,a):
        num_tmp[tmp] = 1

ans = 0
for a in A:
    if num_tmp[a] == 1:
        ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
S = set(A)
ret = 0
for i in range(len(A)):
  A_ = A.copy()
  b = A_.pop(i)
  if b not in A_:
    for s in S:
      if b % s == 0:
        break
      elif s > b // 2:
        break
    ret += 1
    
print(ret)

Submission status: Wrong Answer

Solution code:

# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
count =set()
couter =Counter(A)
multiple =set()
for a in A:
    if couter[a] >=2:
        multiple.add(a)
        continue
    elif a in multiple:
        continue
    else:
        for i in range(2,10**6):
            if i*a  in A_set:
                multiple.add(i*a)
            elif i*a >10**6 +1:
                break
ans =len(A_set - multiple)
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
List=list(map(int,input().split()))
container=collections.Counter(List)
if(1 in container):
    if(container[1]==1):
        print(1)
    else:
        print(0)
else:
    List.sort()
    seive=[True]*(List[~0]+1)
    count=0
    for each in List:
        i=2
        if(seive[each]):
            while i*each<=List[~0]:
                seive[i*each]=False
                i+=1
            if container[each]==1:
                count+=1
    print(seive)
    print(count)

Submission status: Wrong Answer

Solution code:

# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
count =set()
couter =Counter(A)
multiple =set()
for a in A:
    if couter[a] >=2:
        multiple.add(a)
    elif a in multiple:
        continue
    else:
        for i in range(2,10**6):
            if i*a  in A_set:
                multiple.add(i*a)

ans =len(A_set - multiple)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
A = list(map(int, input().split()))

A = [int(k) for k, v in Counter(A).items() if v == 1]
A = sorted(A)

seed = []

while A:    
    wareta = set()
    warenai = []

    q = A.pop(0)
    for a in A:
        if a % q == 0:
            wareta.add(a)
        else:
            warenai.append(a)

    if q not in wareta:
        seed.append(q) 

    A = warenai[:]

print(len(seed))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

cnt = [0] * ((10**6) + 1)

for elem in a:
    cnt[elem] += 1

unique = []

for i in range((10**6) + 1):
    if cnt[i] == 1:
        unique.append(i)

cnt = [0] * ((10**6) + 1)

for elem in unique:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

ans = 0

for elem in unique:
    if cnt[elem] == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

a.sort()

ans = []
ss = []


ans.append(a[0])

for i in a[1:]:
    if i in ss:
        continue
    for check in ans:
        if i == check:
            ss.append(ans.pop())
            break
        if i % check == 0:
            break
    else:
        ans.append(i)

print(len(ans))

Submission status: Wrong Answer

Solution code:
def main():
  N=int(input())
  A=sorted(set(int(a) for a in input().split()))
  D=[False for _ in range(A[-1]+1)]

  if len(A)==1:
    print(0)
  else:
    for a in A:
      D[a]=True
    for i in range(A[-1]+1):
      if D[i]==False:
        continue
      c=2
      while i*c<=A[-1]:
        D[i*c]=False
        c+=1
    print(D.count(True))

main()

Submission status: Wrong Answer

Solution code:
def main():
  N=int(input())
  A=sorted(int(a) for a in input().split())

  if len(set(A))==1:
    A=[]

  c=0
  while A:
    A=[a for a in A[1:] if a%A[0]]
    c+=1

  print(c)

main()

Submission status: Wrong Answer

Solution code:
def main():
  N=int(input())
  A=sorted(set(int(a) for a in input().split()))

  if len(A)==1:
    A=[]
  c=0
  while A:
    A=[a for a in A[1:] if a%A[0]]
    c+=1
  print(c)

main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(set(int(a) for a in input().split()))

if len(A)==1:
  A=[]

c=0
while A:
  A=[a for a in A[1:] if a%A[0]]
  c+=1

print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
A = list(set(a))
A.sort()
amax = A[-1]
sieve = [1]*(amax+1)
ans = []

for i in A:
  for j in range(2,amax//i + 1):
    sieve[i*j] = 0

for i in A:
  if sieve[i] == 1:
    ans.append(i)

c = Counter(a)
ansl =len(ans)

for k,v in c.items():
  if v >= 2:
    ansl -= 1
    
print(ansl)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = 0

for i in range(n):
	for j in range(i,n):
		if i != j:
			if a[i]%a[j] == 0:
				c+=1
				break


print(n-c)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)

f2 = False
f3 = False
f5 = False

if 2 in a:
    f2 = True

if 3 in a:
    f3 = True

if 5 in a:
    f5 = True

ans = 0
for i in range(n):
    if f2 and a[i] % 2 == 0:
        continue
    if f3 and a[i] % 3 == 0:
        continue
    if f5 and a[i] % 5 == 0:
        continue
    for j in range(n - 1, i, -1):
        if a[i] % a[j] == 0:
            break
    else:
        ans += 1

if f2 and a.count(2) == 1:
    ans += 1
if f3 and a.count(3) == 1:
    ans += 1
if f5 and a.count(5) == 1:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))


if len(list(set(A)))==1:
    print(0)
    exit()

f=[True]*(max(A)+1)
chk=[0]*(max(A)+1)

for a in A:
    chk[a]+=1

for a in A:
    cnt=2
    while a*cnt<=max(A):
        f[a*cnt]=False
        cnt+=1
ans=0
for a in A:
    if f[a]==True and chk[a]==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))


if len(list(set(A)))==1:
    print(0)
    exit()

f=[True]*(max(A)+1)
chk=[0]*(max(A)+1)

for a in A:
    chk[a]=1

for a in A:
    cnt=2
    while a*cnt<=max(A):
        f[a*cnt]=False
        cnt+=1
ans=0
for i in range(1,max(A)+1):
    if f[i]==True and chk[i]==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]


l = [0] * 1000000


for i in a:

    c = 2
    while True:
        if i*c-1 >= 1000000:
            break
        l[i*c - 1] = 1
        c += 1


sa = sorted(a)
ans = 0

for i in range(len(sa)):
    if l[sa[i]-1] == 0 and sa[i-1] != sa[i]:
        if i != 0:
            ans += 1
        else:
            if sa[i+1] != sa[i]: ans += 1 

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))


if len(list(set(A)))==1:
    print(0)
    exit()

f=[0]*(max(A)+1)
for a in A:
    f[a]=1

for a in A:
    if f[a]==0:continue
    cnt=2
    while cnt*a<=max(A):
        f[cnt*a]=0
        cnt+=1
print(sum(f))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))


if list(set(A))==1:
    print(0)
    exit()

f=[0]*(max(A)+1)
for a in A:
    f[a]=1

for a in A:
    if f[a]==0:continue
    cnt=2
    while cnt*a<=max(A):
        f[cnt*a]=0
        cnt+=1
print(sum(f))

Submission status: Wrong Answer

Solution code:
lst=[]
c=0
flag=0
n = int(input())
str = input()
lst = str.split(' ')
for i in range(0,n):
  lst[i] = int(lst[i])
for i in range(0,n):
  for j in range(0,n):
    if i==j:
      pass
    else:
      if lst[i]%lst[j]==0:
        flag=1
      else:
        pass
  if flag==0:
    c = c+1
        
print(c)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))

A=list(set(A))

L=len(A)

if L==1:
    print(0)
    exit()

f=[0]*(max(A)+1)

for a in A:
    f[a]=1

for a in A:
    if f[a]==0:continue
    cnt=2
    while cnt*a<=max(A):
        f[cnt*a]=0
        cnt+=1
print(sum(f))

Submission status: Wrong Answer

Solution code:
lst=[]
c=0
n = int(input())
str = input()
lst = str.split(' ')
for i in range(0,n):
  lst[i] = int(lst[i])
for i in range(0,n):
  for j in range(0,n):
    if i==j:
      pass
    else:
      if lst[i]%lst[j]==0:
        pass
      else:
        c = c+1
        break
print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))

A.sort()

dp = np.ones(max(A)+1, dtype=bool)

for a in A:
    for i in range(2,len(dp)):
        if a*i > max(A):
            break
        if not dp[a*i]:
            break
        dp[a*i] = False

for i in range(1,len(A)):
    if A[i] == A[i-1]:
        dp[A[i]] = False

cnt = 0
for a in A:
    if dp[a]:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))

ans = N

for i in range(N):
  for j in range(0,N,2):
    if j == i:
      continue
    else:
      if A[i]%A[j] == 0:
        ans -= 1
        break
        
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))

A=list(set(A))

L=len(A)

if L==1:
    print(0)
    exit()

mx=max(A)

f=[1]*L

A.sort()

for i in range(L):
    if A[i]*2>mx:break
    if f[i] == 0: continue
    for j in range(i+1,L):
        if f[j]==0:continue
        if A[j]%A[i]==0:
            f[j]=0

print(sum(f))

Submission status: Wrong Answer

Solution code:
N = int(input())
A_array = [int(x) for x in input().split(" ")]

flag = [True] * N

for i, ai in enumerate(zip(A_array, flag)):
    target_array = [val % ai[0] for val in A_array]
    for index, val in enumerate(target_array):
      if i == index or flag[i] == False:
        continue
      if val == 0:
        flag[index] = False
print(flag.count(True))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))

A=list(set(A))

L=len(A)

if L==1:
    print(0)
    exit()

mx=max(A)

f=[1]*L

A.sort()

for i in range(L):
    if A[i]*2>mx:break
    for j in range(i+1,L):
        if A[j]%A[i]==0:
            f[j]=0

print(sum(f))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

Amx = max(A)
A.sort()
As = set(A)
# DP
ca = Counter(A)
ans = 0
dp = [True] * (Amx + 1)
for a in A:
    if not dp[a]:
        continue
    elif ca[a] <= 1:
        ans += 1
        ad = Amx // a
        for i in range(1, ad+1):
            dp[i * a] = False

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

Amx = max(A)
A.sort()
As = set(A)
if len(As) == 1:
    print(0)
    sys.exit()
# DP
ca = Counter(A)
ans = 0
dp = [True] * (Amx + 1)
for a in A:
    if not dp[a]:
        continue
    elif ca[a] <= 1:
        ans += 1
        ad = Amx // a
        for i in range(1, ad+1):
            dp[i * a] = False

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

Amx = max(A)
A.sort()
As = set(A)
if len(As) == 1:
    print(0)
    sys.exit()
# DP
ca = Counter(A)
ans = 0
dp = [True] * (Amx + 1)
for a in A:
    if not dp[a]:
        continue
    elif ca[a] <= 1:
        ans += 1
        ad = Amx // a
        for i in range(2, ad+1):
            dp[i * a] = False

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
*a, = sorted(map(int, input().split()))
a_max = a[n-1]
dp = [True] * a_max
ans = 0
recent = 0

if n == 1:
    print(0)
    exit()

for i in a:
    if recent == i:
        ans -= 1
        recent = 0
    if dp[i-1] == False:
        continue
    else:
        for j in range(i, a_max+1, i):
            dp[j-1] = False
        ans += 1
        recent = i

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
A = list(map(int, input().split()))

Amx = max(A)
A.sort()
As = set(A)
if len(As) == 1:
    print(0)
    sys.exit()
# DP
ans = 0
dp = [True] * (Amx + 1)
for a in As:
    if not dp[a]:
        continue
    ans += 1
    ad = Amx // a
    for i in range(2, ad+1):
        dp[i * a] = False

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_array = [int(x) for x in input().split(" ")]

counter = 0

for i, ai in enumerate(A_array):
    target_array = [val % ai for j, val in enumerate(A_array) if i != j]
    zeros = target_array.count(0)
    if zeros == N:
      print(0)
      break
    if target_array.count(0) > 0 and target_array.count(0) > counter:
        counter = target_array.count(0)

print(N - counter)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

# 13:42- kaisetsu and try again


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0
            continue

        for i in range(2, M+1):
            if a*i > M:
                break
            is_ans_flag[a*i] = 0

    return sum(is_ans_flag)


print(main())

Submission status: Wrong Answer

Solution code:
# coding: utf-8

# 13:42- kaisetsu and try again


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0
            continue

        for i in range(2, (M - M % a)//a + 1):
            is_ans_flag[a*i] = 0

    # print(is_ans_flag[:10])
    return sum(is_ans_flag)


print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque,Counter
n,*a = map(int,open(0).read().split())
c = Counter(a)
r = len([i for i in c.values() if i > 1])
a = deque(sorted(set(a)))
ans = 0
while a:
    f = a.popleft()
    z = deque()
    for u in a:
        if u%f != 0:
            z.append(u)
    a = z
    ans += 1
print(ans-r)

Submission status: Wrong Answer

Solution code:
from collections import deque,Counter
import bisect
n,*a = map(int,open(0).read().split())
c = Counter(a)
c = sorted(c.items())
a = deque(c)
p_set = set()
ans,r = 0,0
while a:
    f,count = a.popleft()
    if count == 1:
        z = []
        for u in range(len(a)):
            if a[u][0]%f != 0:
                z.append(a[u])
        a = deque(z[:])
    else:
        r += 1
    p_set.add(f)
print(len(p_set)-r)