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:
N=int(input())
A=list(map(int,input().split()))

A.sort(reverse=True)
d={}
for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1

ans=0

for i in range(N):
    a=A[i]
    p=1
    for j in range(2,int(a**0.5)+1):
        if a%j==0:
            if j in d or a//j in d:
                p=0
                break
    ans+=p
if A[-1]==1:
    if A[-1]>1:
        ans=1
    else:
        ans=0

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
div = set()
dict_a = collections.Counter(a)
for i in range(n):
    flag = True
    if dict_a[a[i]] >= 1:
        continue
    for j in range(1,int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            if j in div or a[i] // j in div:
                flag = False
                break
    div.add(a[i])
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

if len(set(orga)) == 1:
    print(0)
    exit()

import collections
c = collections.Counter(orga)

a=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        a.append(num)

def m_div(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

from collections import defaultdict
d = defaultdict(int)

ans=0
for num in a:
    found=False
    for div in m_div(num):
        if div in d:
            found=True
            break
    if not found:
        d[num]=1
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n = int(readline())
    a = list(map(int, readline().split()))
    if len(set(a)) == 1:
        print(0)
        exit()
    a.sort()
    memo = [True] * (10 ** 6 + 1)
    ans = 0
    for aa in a:
        if memo[aa]:
            ans += 1
            for i in range(1, 10 ** 6 + 1):
                if 10 ** 6 + 1 <= i * aa:
                    break
                memo[i * aa] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    A = np.array(A, np.int64)
    if np.all(A == A[0]):
        print(0)
        exit()
    #print(A)

    memo = [1] * n
    for i in range(n - 1):
        for j in range(i + 1, n):
            if A[j] % A[i] == 0:
                memo[j] = 0

    print(memo.count(1))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    # divisors.sort()
    return divisors

n = int(input())
dat = list(map(int, input().split()))
res = 0
import collections
buf = collections.Counter(dat)
dat = []
for k in buf:
    if buf[k] == 1:
        dat.append(k)
dat.sort()
#print(dat)
res = 0
used = [False] * (1000100)

for i in range(len(dat)):
    ok = True
    divList = make_divisors(dat[i])
    for j in range(len(divList)):
        if used[divList[j]]:
            ok = False
    used[dat[i]] = True
    if ok:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted([int(_) for _ in input().split()])
factors = set([])
for a in A:
    ok = True
    for f in factors:
        if a % f == 0:
            ok = False
            break
    if ok:
        factors.add(a)
print(len(factors))

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
l = prime_factorize(a[n-1])
c = Counter(l)
ans = 0
for i in range(n-2,-1,-1):
    l = prime_factorize(a[i])
    c2 = Counter(l)
    flag = 1
    for k,v in c2.items():
        if c[k] != 0:
            if v%c[k] == 0:
                flag = 0
        if c[k] == 0:
            c[k] = v
        else:
            c[k] = gcd(c[k],v)
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()
    ac=Counter(aa)
    aa=[]
    for a,c in sorted(ac.items()):
        if c==1:aa.append(a)
    #print(aa)

    dd=[]
    for a in aa:
        for d in dd:
            if a%d==0:break
        else:
            dd.append(a)
    print(len(dd))

main()

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

n=ni()
a=sorted(nl())

ans=0

for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if a[i]%a[j]==0:
      break
  if j==n-1:
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):
  flag=True
  s=l[-1-i]
  for j in range(n):
    if n-1-i==j:
      pass
    else:
      if s%l[j]==0:
        flag=False
        break
  if flag:
    ans+=1

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
b = set(a)

lim = pow(10, 6)+3
judge = [False]*(lim)
ans = 0
a.sort()
key = 0
for i in range(lim):
  if judge[i] == True:
    continue
  elif i not in b:
    continue
  else:
    if key != n-1 and a[key] == a[key+1]:
      pass
    else:
      ans += 1
    key += 1
    for j in range(i, lim, i):
      judge[j] = True
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = Counter(a)
ma = a[-1]

check = [True] * (ma+1)

for i in b:
    if b[i] >= 2:
        check[i] = False

ans = 0
for i in range(n):
    if check[a[i]]:
        ans += 1
        for j in range(a[i],ma+1,a[i]):
            check[j] = False
            
print(ans)

Submission status: Wrong Answer

Solution code:
num = int(input())
arr = input().split()
arr = [int(i) for i in arr]

arr = sorted(arr, reverse=True)

cnt = 0

for i in range(num):
  flg=0
  for j in range(i+1, num):
    print(arr[i], arr[j])
    if arr[i]%arr[j]==0:
      flg=1
      break
  if flg==1: cnt += 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = LI()

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1

b = [False]*(10**6+1)
for k in d.keys():
    if d[k] == 1:
        b[k] = True

for i in range(10**6+1):
    if b[i]:
        for j in range(2*i,10**6+1,i):
            b[j] = False

count = 0
for i in range(10**6+1):
    if b[i]:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
ct=0
a=list(map(int,input().split()))
b=[a[i] for i in range(n) if a[i]%(i+1)!=0]
print(len(set(b))-1)

Submission status: Wrong Answer

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

A.sort()
result = 0
for i in range(N):
    for j in range(i):
        if A[i] % A[j] == 0:
            break
    else:
        result += 1
print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != N-1:
        if a == A[i+1]:
            continue
    flag = True
    for j in range(i):
        if a % A[j] == 0:
            flag = False
            break
        elif a < A[j] ** 2:
            break
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0
for i in range(N - 1):
  flag = True
  for j in range(i + 1, N):
    if (A[i]//A[j])*A[j] == A[i]:
      flag = False
      break
  if flag:
    ans += 1
if N >= 2 and A[-1] != A[-2]:
  ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()

for i in range(n-1):
    if a[i] == a[i+1]:
        print(0)
        quit()

f = defaultdict(lambda : 0)

ans = 0
for i in a:
    if f[i] == 0:
        ans += 1
        j = 2
        f[i] = 1
        while i*j <= 10**6:
            f[i*j] = 1
            j += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = Counter(list(map(int, input().split())))
A = [x[0] for x in A.items() if x[1] == 1]
A.sort()
ans = 0
while A:
    x = A[0]
    ans += 1
    A = [a for a in A if a%x != 0]
print(ans)

Submission status: Wrong Answer

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

    a.sort()
    r = 0
    for i1 in range(n):
        flag = 1
        for i2 in range(i1):
            if a[i2] > a[i1]//2 + 1:
                continue
            else:
                if a[i1] % a[i2] == 0:
                    flag = 0
                    break
        if flag:
            r += 1
    print(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(map(int,input().split()))
dp=[1]*10**6
for a in A:
    if dp[a-1]==1:
        dp[a-1]=2
        for i in range(a*2,10**6,a):
            dp[i-1]=0
    elif dp[a-1]==2:
        dp[a-1]=0
print(sum([1 for a in A if dp[a-1]]))

Submission status: Wrong Answer

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

alist.sort()

count = 0

if alist.count(alist[0]) == 1:
  count += 1

for i in range(1, N):
  a = alist[i]
  flag = 0
  for j in range(i):
    if a % alist[j] == 0:
      flag = 1
      break
  if flag == 0:
    count += 1
      
print(count)

Submission status: Wrong Answer

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

A =sorted(A)

ans=0
while A:
    cur = A.pop(0)
    A = list(filter(lambda x:x%cur!=0,A))
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    MAX = 1000001
    N = int(input())
    arr = list(map(int, input().split(" ")))
    arr.sort()
    is_ans = [True]*MAX
    ans = 0

    dup = set()
    for a in arr :
        if a in dup:
            is_ans[a] = False
        dup.add(a)
        
    for a in arr :
        if is_ans[a]:
            ans += 1
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

    return ans

print(solve())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()
if a[0] == 1:
    print(1)
    quit()

for i in range(n-1):
    if a[i] == a[i+1]:
        print(0)
        quit()

f = defaultdict(lambda : 0)

ans = 0
for i in a:
    if f[i] == 0:
        ans += 1
        j = 2
        f[i] = 1
        while i*j <= 10**6:
            f[i*j] = 1
            j += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
ans=0
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        if A[i]<A[j]:
            break
        if A[i]%A[j]==0:
            break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

A = sorted(A)

tmp = A[0]
if all([i == tmp for i in A]):
  print(0)
  import sys
  sys.exit()

devide_list = []
cnt = 0

for a in A:
  flag = 1
  for d in devide_list:
    if a % d == 0:
      flag = 0
      break
  if flag == 1:
    cnt += 1
  else:
    pass
  devide_list.append(a)
  
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
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()))

x = [False]*(10**6+1)

a.sort()
for i in range(1, n):
    if a[i] == a[i-1]:
        if x[a[i]]:
            continue
        else:
            x[a[i]] = True
            for r in range(a[i], 10 ** 6 + 1, a[i]):
                x[i] = True
ans = 0
for v in a:
    if x[v]:
        continue
    ans += 1
    for i in range(v, 10**6+1, v):
        x[i] = True

print(ans)

Submission status: Wrong Answer

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

d = collections.defaultdict(int)


def divisors(n):
    ret = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ret.add(i)
            ret.add(n//i)
    return(ret)


A.sort(reverse=True)
ans = 0
while(A):
    x = A.pop()
    ans += 1
    next = []
    for y in A:
        if y % x != 0:
            next.append(y)

    A = list(next)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
from collections import Counter
a_cnt = Counter(a)
a = []
for k, v in a_cnt.items():
    if v == 1:
        a.append(k)
a.sort()
ans = 0
while a:
    min_a = a[0]
    b = []
    ans += 1
    for i in a[1:]:
        if i % min_a != 0:
            b.append(i)
    a = b
print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())

A = list(map(int, input().split()))
A.sort()
ans = set()
ans.add(A[0])
before = A[0]
for a in A[1:]:
    if before == a:
        if a in ans:
            ans.remove(a)
        continue
    flag = True
    for b in ans:
        if a % b == 0:
            flag = False
            break
    if flag:
        ans.add(a)
    before = a

print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != N-1:
        if a == A[i+1]:
            continue
    flag = True
    for j in range(i):
        if a % A[j] == 0:
            flag = False
            break
        elif a < 2 * A[j]:
            break
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

def henkan(LIST):
    ANS=[]
    for i in range(len(LIST)):
        if LIST[i]%LIST[0]==0:
            pass
        else:
            ANS.append(LIST[i])
    return ANS
cnt=0
if henkan(A)==[]:
    print(0)
    exit()
for i in range(10**9):
    cnt+=1
    A=henkan(A)
    if A==[]:
        print(cnt)
        exit()

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))

A.sort()

B = np.array(A)

if np.all(B == B[0]):
    print(0)
    exit()

cnt = 0
while B.size > 0:
    t = B[0]
    B = B[(B % t != 0)]
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
ok = [1]*(10**6+1)
ans = 0
for i in range(n):
    if ok[a[i]]:
        if i < n-1:
            if a[i+1] != a[i]:
                ans += 1
        else:
            ans += 1
        for j in range(1,10**6//a[i]):
            ok[a[i]*j] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = list(map(int, input().split()))
res = 0
import collections
buf = collections.Counter(dat)
dat = []
for k in buf:
    if buf[k] == 1:
        dat.append(k)
dat.sort()
#print(dat)
res = 0
for i in range(len(dat)):
    ok = True
    for j in range(0, i):
        if dat[i] % dat[j] == 0:
            ok = False
            break
    if ok:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
from itertools import islice
def solve(A):
    memo = [0]*(10**6+1)

    for a in A:
        memo[a] += 1
    if memo[1] > 0:
        return 1 if memo[1] == 1 else 0

    res = 0
    for i,v in enumerate(islice(memo,2,None),start=2):
        if v > 0:
            res += v
            j = i
            while j <= 10**6:
                memo[j] = 0
                j += i
    return res

if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    print(solve(A))

Submission status: Wrong Answer

Solution code:
import math as mt
#import numpy as np

def ro(n):
  return mt.floor(mt.sqrt(n))
def ya():
  print("Yes")
  return
def na():
  print("No")
  return


#x,n=map(int,input().split())
n=int(input())
lis=list(map(int,input().split()))
#s=input()

lis.sort(reverse=True)
ans=0
for i in range(n):
  for j in range(i+1,n):
    #print("{} {}".format(lis[i],lis[j]))
    if lis[i]%lis[j]==0:
      break
  else:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

    a.sort()
    r = 0
    for i1 in range(n):
        for i2 in range(i1):
            if a[i2] > a[i1]//2 + 1:
                continue
            else:
                r += a[i1] % a[i2] == 0
    print(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()

dat={i:False for i in range(20**5+1)}

ans=0
for ele in A:
    if dat[ele]:
        pass
    else:
        ans+=1
        for i in range(ele,20**5+1,ele):
            dat[i]=True

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()
    A.sort()

    F = [True] * (A[-1] + 1)
    for i in range(N - 1):
        if A[i] == A[i + 1]:
            F[A[i]] = False

    res = 0
    for a in A:
        if not F[a]:
            continue
        
        res += 1
        for b in range(a, len(F), a):
            print(a, b)
            F[b] = False

    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()
    aa.sort()
    if aa[0]==aa[-1]:
        print(0)
        exit()
    dd=set()
    for a in aa:
        for d in dd:
            if a%d==0:break
        else:
            dd.add(a)
    print(len(dd))

main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys

N,*A = map(int, sys.stdin.buffer.read().split())

A = sorted(A)
setA = set(A)

def yakusu(x):
  if x==1:
    return []
  result = [1]
  y = 2
  while y**2<=x:
    if x%y==0:
      result.append(y)
      result.append(x//y)
    y += 1
  return result

count = N
for i in range(N):
  a = A[i]
  if i>0 and a==A[i-1]:
    count -= 1
    break
  if i<N-1 and a==A[i+1]:
    count -= 1
    break
  for y in yakusu(a):
    if y in setA:
      count -= 1
      break

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != N-1:
        if a == A[i+1]:
            continue
    flag = True
    for j in range(i):
        if a % A[j] == 0:
            flag = False
        elif a < 2 * A[j]:
            break
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
is_ok = [True for _ in range(n)]

def make_divisors(n):
   lower_divisors , upper_divisors = [], []
   i = 1
   while i*i <= n:
      if n % i == 0:
         lower_divisors.append(i)
         if i != n // i:
            upper_divisors.append(n//i)
      i += 1
   return lower_divisors + upper_divisors[::-1]

divisor = [set() for _ in range(max(a)+1)]

for i, v in enumerate(a):
   if len(divisor[v]) > 0:
      for w in divisor[v]:
         is_ok[w] = False

   divs = make_divisors(v)
   for div in divs:
      divisor[div].add(i)

ans = sum(is_ok)
if ans == 1:
   ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
alist=list(map(int,input().split()))
aset=set(alist)
if len(aset)==1:
  print(0)
  sys.exit(0)

alist.sort()
#print(alist)

pset=set()
for i in range(N):
  for p in pset:
    if alist[i]%p==0:
      break
  else:
    pset.add(alist[i])
    
#print(pset)
print(len(pset))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    A.sort()
    use=[0]*N
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    ans=0
    for i in range(N):
        dd[A[i]]+=1
        if use[i]==0:
            f1=1
            for j in range(i+1,N):
                if A[j]%A[i]==0:
                    use[j]=1
                    f1=0
                    
    
    ans=N-sum(use)
    
    for k,v in dd.items():
        if v>=2:
            ans-=1
            
    print(ans)
                
    


main()

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
s=0
N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  c=L[i]
  if len(set(L)&set(make_divisors(c)))==1:
    s+=1
print(s)

Submission status: Wrong Answer

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

al.sort()
table = [False]*1000001
table2 = [False]*1000001

for a in al:
    if table2[a]:
        table[a]=True
    if not table[a]:
        table2[a] = True
        for i in range(a+a,1000000,a):
            table[i]=True
    

cnt=0
for a in al:
    if not table[a]:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=n
for i in range(1,n):
  for j in range(0,i):
    if a[i]%a[j]==0:
      ans=ans-1
      break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = sorted(li())

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

for i, num in enumerate(A):
    if not flag[num] and A[i]!=num:
        cnt += 1
    x = num
    while x + num < 10**6+1:
        flag[x] = 1
        x += num

print(cnt)

Submission status: Wrong Answer

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

A.sort()
from collections import Counter
L = dict(Counter(A))

Xs = list(L.keys())
NX = len(Xs)
Ys = [1]*NX

if NX!=1:
    cnt = 0
    while True:
        now = Xs[0]
        cnt += L[now]
        S = []
        for X in Xs:
            if X%now!=0 and X!=now:
                S.append(X)
        if len(S)==0:
            break
        Xs = S[:]
    print(cnt)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in a:
    p=0
    for j in b:
        if j%i==0:
            b.remove(j)
        if i%j==0:
            p=1
    if not p:
        b+=[i]
print(len(b))

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = set(A)
    nums = dict()
    for i, a in enumerate(A):
        if a in nums: nums[a] += 1
        else: nums[a] = 1
    
    ans = 0
    for k in nums:
        if nums[k] > 1: continue
        else:
            flag = True
            for i in range(2, k):
                if i ** 2 > k: break
                if k % i == 0:
                    if i in B or k // i in B:
                        flag = False
                        break
            if flag: ans += 1
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

from collections import defaultdict
dic = defaultdict(int)

for a in al:
    dic[a] += 1
al = sorted(al)
from math import sqrt
M = 10**6+1
p = [1]*(M+1)
p[0] = p[1] = 0
ans = 0
for x in al:
    if p[x]:
        if dic[x] == 1:
            ans += 1
        for y in range(x, M+1, x):
            p[y] = 0

print(ans)

Submission status: Wrong Answer

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

A.sort()

L = [False]*(10**6+1)
for i,a in enumerate(A):
    if A[i-1] == a:
        L[a] = True
        continue
    if L[a]: continue
    for i in range(2,10**6+1):
        if a*i > 10**6: break
        L[a*i] = True

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

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
b = set(a)
if len(b) != len(a):
  print(0)
  sys.exit()
else:
  lim = pow(10, 6)+1
  judge = [False]*(lim)
  a.sort()
  key = 1
  ans = 0
  for i in range(lim):
    if judge[i] == True:
      continue
    else:
      if i not in b:
        continue
      ans += 1
      for j in range(i, lim, i):
        judge[j] = True
  print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
from collections import Counter
D=dict(Counter(a))
E=[]
for key in D.keys():
    if D[key]==1:
        E.append(key)
E.sort()
F=E.copy()
E=set(E)

for d in F:
    for j in range(2,max(F)//d+3):
        if j*d in E:
            E.remove(j*d)
print(len(E))