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:
from collections import Counter

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

c = Counter(a)
nu = {k for k, v in c.items() if v > 1}

s = set()
for aa in a:
    m = 2
    if aa in s or aa in nu:
        continue
    while aa*m <= 10**6:
        s.add(aa*m)
        m += 1

o = 0
for aa in a:
    if aa in s or aa in nu:
        continue
    o += 1

print(o)

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
dbl = len([i[0] for i in c.items() if i[1] >= 2])

A = list(set(A))
A.sort()
N = len(A)
ans = 0
B = [0] * N
for i, a in enumerate(A):
    if B[i] == 1:
        continue
    else:
        ans += 1
    for j in range(i+1, N):
        if A[j]%a == 0:
            B[j] = 1

print(ans-dbl)

Submission status: Wrong Answer

Solution code:
n=int(input())
As = list(map(int, input().split()))
i=0
j=0
count =0
for a in As:
    for b in As:
        if i!=j:
            if a%b==0:
                break
            elif j==n-1:
                count+=1
        j+=1
    i+=1
    j=0

print(count)

Submission status: Wrong Answer

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

if 1 in A:
  print(0)
else:
  for a in A:
    A = np.delete(A,np.where((A!=a) & (A%a==0)))
  print(len(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans = 0

if len(a_list) == 1:
    print(0)
else:
    if a_list[0] != a_list[1]:
        ans += 1
    for i in range(1, n):
        for j in range(i):
            if a_list[i] % a_list[j] == 0:
                break;
            if j == i - 1:
                ans += 1
                
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from numba import jit

@jit
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

N=int(input())
A=list(range(800000,1000000))

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

s=set(A)

ans=0
for i in range(N):
    if A[i] in ng:
        continue
    s.remove(A[i])
    arr=factor(A[i])
    ok=True
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
    s.add(A[i])
print(ans)

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

    d = dict()
    for x in A:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    A = set(A)

    ans = -len([x for x in d if d[x] > 1])

    while(A):
        ans += 1
        x = min(A)
        next = set()
        for y in A:
            if y % x != 0:
                next.add(y)
        A = set()
        A |= next

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    l = [int(x) for x in input().split()]
    
    count=0
    l = sorted(l,reverse=True)
    for i in range(N-1):
        for j in range(i+1,N):
            n=0
            if l[i]%l[j]==0:
                break
        else:
            count+=1
    if l[N-1]!=l[N-2]:
        count+=1
    print(count)
    
main()

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    if A[0]==A[N-1]:
        print(0)
        sys.exit()
    for x in A:
        B=[y for y in A if y%x != 0 or y==x]
        A=B
    print(len(A))

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(set([a for a in map(int,input().split())])), reverse=True)

ans = 0
for a in A:
    for b in A[(A.index(a)+1):]:
        if a%b == 0:
            ans += 1
            break
print(ans)

Submission status: Wrong Answer

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


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]


B = []
for i, n in Counter(A).items():
    if n == 1:
        B.append(i)
B.sort()
ans = set([])
for b in B:
    p = make_divisors(b)
    if len(ans & set(p)) == 0:
        ans.add(b)

print(len(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
for i in range(len(p)):
    for j in range(i+1,len(p)):
        if p[i]%p[j] ==0:
            break
        if j == len(p)-1:
            count +=1



if count >=1:
    print(count+1)
else:
    print(count)

Submission status: Wrong Answer

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

if sum(a) == a[0]*n or a.count(1) >= 2:
    print("0")
elif a.count(1) == 1 or n==1:
    print("1")
else:
    a.sort()
    c = 0
    for i in range(n-1, 0, -1):
        for j in range(i-1, -1, -1):
            if a[i]%a[j] == 0:
                break
            if j == 0:
                c += 1
    print(c+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
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
    index = bisect_left(a, min_a * 2)
    m_i = max(index, 1)
    for i in range(m_i, len(a)):
        if a[i] % min_a != 0:
            b.append(a[i])
    a = a[1:index] + b 
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import decimal
import math
import collections
import sys
input = sys.stdin.readline

N=int(input())

ListA=list(map(int,input().split()))
ListA.sort(reverse=True)

ans=N
for i in range(N):
    for j in range(i+1,N):
        if(ListA[i]%ListA[j]==0):
            ans-=1
            break
if(N>=2):
    if(ListA[N-1]%ListA[N-2]==0):
        ans-=1

print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)

cnt=0
for i in range(0, N-1):
    flag=0

    val_L = A[i]
    for j in range(i+1, N):
        val_R = A[j]


        if val_L % val_R == 0:
            flag = 1
            break
    
    if flag==0:
        cnt+=1

if A[N-2] != A[N-1]:
    cnt+=1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque


def resolve():
    _ = int(input())
    targets = list(map(int, input().split()))

    targets = [x for x in set(targets) if targets.count(x) == 1]
    if len(targets) == 0:
        print(0)
        return
    targets.sort()
    targets = deque(targets)

    ans = []

    while len(targets) > 0:
        target = targets.popleft()
        ans.append(target)
        removeList = []
        for x in targets:
            if x % target == 0:
                removeList.append(x)
        for x in removeList:
            targets.remove(x)

    print(len(ans))

resolve()

Submission status: Wrong Answer

Solution code:
from collections import Counter 

def divisors(n):#without itselfs and 1
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

def main():
    n = int(input())

    a = list([int(t)for t in input().split()])
    a_set = set(a)
    c = Counter(a)

    ans = 0

    for a_i in a:
        divs = set(divisors(a_i))
        for d in divs:
            if (not d in a_set) and c[a_i]==1:
                ans+=1
                break
    print(ans)
            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N==1:
  print(1)
else:
  A.sort()
  import numpy as np

  l = np.array([0] * (10**6 + 10))
  for i in range(1,N):
    if A[i-1]!=A[i]:
      l[A[i]] += 1

  if A[0]!=A[1]:
    l[A[0]] += 1

  ans = 0
  length = len(l)
  for i in range(length):
    if l[i]==1:
      ans += 1
      l[i::i] = 0

  print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def Sieve(N, AList):
    AList.sort()
    N_NotDivisible = 0
    Mins = []
    while( len(AList) > 0 ):
        if( len(AList)>1 and AList[0] == AList[1]):
            while( len(AList)>1 and AList[0] == AList[1] ):
                AList.pop(1)
            AList.pop(0)
        if( len(AList) > 0 ):
            N_NotDivisible+= 1
            value = AList[0]
            AList.pop(0)
            Mins.append(value)
            AList = [ i for i in AList if i % value != 0 ]
    #print(Mins)
    return N_NotDivisible

if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()

    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a.sort()
num = 10**6+10
input_list = defaultdict(int)
sqrt = math.sqrt(num)

for serial in a:

    if serial >= sqrt:continue

    for s in range(serial, num, serial): 
        input_list[s] +=1
ans =0
for i in a:
    # print(i,input_list[i])
    ans +=(input_list[i]>1)
print(n - ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

Fs = [0]*N

As.sort()
if N == 1:
  print(1)
  exit()
elif As[0] < As[1]:
  rlt = 1
else:
  rlt = 0
  
for i in range(1,N):
  for j in range(i):
    flag = 0
    if Fs[j] == 1:
      continue
    else:
      if As[i] < 2*As[j]:
        break
      if As[i]%As[j] == 0:
        Fs[i] = 1
        flag = 1
        break
  if flag == 0:
    rlt += 1
        
print(rlt)

Submission status: Wrong Answer

Solution code:
N = int(input())
As = sorted(list(map(int,input().split())))
cnt = 0
for i in range(N):
  for j in range(i+1,-1,-1):
    if j == i: continue
    if As[i] % As[j%N] == 0:
      # print("break",As[i],As[j%N])
      break
  else:
    # print("cnt",As[i])
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
li = [1]*(10**6+5)
a.sort()
ans = 1

for i in range(a[0], len(li), a[0]):
  li[i] = [0]

flag = False
for i in range(1, len(a)):
  if a[i-1] == a[i]:
    flag = True
    continue
  else:
    flag = False
    ans -= 1
  if li[a[i]] == 1:
    ans += 1
    for j in range(a[i], len(li), a[i]):
      li[j] = 0
if flag:
  ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
A = sorted(A)

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table
  
is_prime, _ = sieve(10**6)  


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


s = set()
for a in A:
  if is_prime[a-1]:
    s.add(a)
  else:
    dv = divisors(a)
    for d in dv:
      if d in s:
        break
    else:
      s.add(a)

ans = 0
C = Counter(A)
for si in s:
  if C[si]==1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=input()
a0=a.split()
al=list()
k=0
for i in range(n):
    al.append(int(a0[i]))
al.sort(reverse=True)
for i in range(n):
    f=0
    for j in range(i+1,n):
        if i!=j and al[i]%al[j]==0:
            f=1
            break
    if f==0:
        k=k+1
print(k)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    n, *a = map(int, open(0).read().split())
    x = Counter(a)
    y = [k for k, v in x.items() if v == 1]
    if len(y) == 0:
        print(0)
        exit()

    z = sorted(y)

    if z[0] == 1:
        print(1)
        exit()

    cnt = 0
    while z:
        cnt += 1
        i = z[0]
        *z, = filter(lambda j: j % i != 0, z)

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
from collections import Counter as co
l=co(list(map(int,input().split())))
ans=len(l)
ng=set()
for k in l:
    if l[k]>=2:ng.add(k)
    for i in range(2*k,2*10**5+1,k):
        if i in l:
            ng.add(i)
            
            
            

print(ans-len(ng))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def ip():
    return sys.stdin.readline()


def ipl():
    return sys.stdin.readline().split()


def solve():
    ip()
    li = list(map(int, ipl()))
    freq = defaultdict(int)
    for i in li:
        freq[i] += 1
    cnt = 0
    for i in li:
        f = 1
        for j in range(1, int(i ** 0.5) + 1):
            if i % j == 0:
                if freq[j] == 1:
                    f = 0
                    break
                if freq[i // j]:
                    if i // j == i:
                        if freq[i] > 1:
                            f = 0
                            break
                    else:
                        f = 0
                        break
        cnt += f
    print(cnt)


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def examD():
    def make_divisors(n):
        divisors = [1]
        for i in range(2, 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 = I()
    A = LI()
    C = set()
    D = set()
    ans = 0
    for a in A:
        if a in D:
            C.discard(a)
            continue
        D.add(a)
        C.add(a)

    for a in C:
        flag = 2
        cur = make_divisors(a)
        for c in cur:
            if c in D:
                flag -= 1
            if flag==0:
                break
        if flag>0:
            ans += 1
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
l=list(mi())
l=sorted(l)
ans=[l[0]]
c=set()
for i in range(1,a):
  t=True
  for j in ans:
    if l[i]<2*j:
      if l[i]!=j:
        break
      else:
        c.add(j)
        t=False
        break
    elif l[i]%j==0:
      t=False
      break
  if t:
    ans.append(l[i])
print(len(ans)-len(c))

Submission status: Wrong Answer

Solution code:

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
sys.setrecursionlimit(10 ** 7)
import bisect
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


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

D = defaultdict(int)
for a in A:
    D[a] += 1

L = []
for k, v in D.items():
    if v > 1:
        continue
    L.append(k)

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

L.sort()

ans = set()
for n in L:
    if is_prime(n):
        ans.add(n)
    flg = True
    for s in ans:
        if n % s == 0:
            flg = False
            break
    if flg is False:
        continue
    ans.add(n)

print(len(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
s=[]
ans = 1
if n==1:
    print(ans)
    exit()
if n>=2 and a[0]==a[1]:
    ans=0
s.append(a[0])
for i in range(1,n):
    c=0
    for j in s:
        if a[i]%j==0:
            c=1
            break
    if c==0:
        ans+=1
        s.append(a[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
li = np.zeros(10**6)
a = np.array(list(map(int, input().split())))
a.sort()
for item in a:
  li[item-1] = 1
#print(li[:100])

for item in a[::-1]:
  li[item-1::item] = 0
  li[item-1] = 1

#print(li[:100])

print(int(li.sum()))

Submission status: Wrong Answer

Solution code:
import sys

def lcm(a, b):
    a, b = max(a, b), min(a, b)
    c = a * b
    while a % b > 0:
        a, b = b, a % b
    return c // b

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    if N == 1: 
        print(1)
        return 0
    #lcmA = lcm(A[0], A[1])
    #for i in range(2, N): lcmA = lcm(lcmA, A[i])

    B = [False] * (max(A) + 1)
    nums = dict()
    for a in A:
        B[a] = True
        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(1, k):
                if i ** 2 > k: break
                if k % i == 0:
                    if B[i] or B[k//i]:
                        flag = False
                        break
            if flag: ans += 1
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import Counter

n=int(input())
l=list(map(int,input().split()))
c=Counter(l)
l=sorted([x for x in c])
sm=0
if len(l)==1: print(0);exit()
for i in range(1,len(l)):
    for j in range(i):
        if l[i]%l[j]==0:
            break
    else:sm+=c[l[i]]
print(sm+1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
li = [True for _ in range(0, 10**6 + 1)]
A = list(map(int, input().split()))
A.sort()
used = {}
for i in range(N):
    if A[i] not in used.keys():
        used[A[i]] = 1
    else:
        used[A[i]] += 1
ans = 0
for i in range(N):
    if A[i] in used.keys() and used[A[i]] > 1:
        continue
    if li[A[i]]:
        ans += 1
    else:
        continue
    for j in range(A[i], 10**6 + 1, A[i]):
        li[j] = False
# ans -= len(A) - len(set(A))
if N == 1:
    ans = 0
print(max(0, ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
m=max(a)
x=[1 for i in range(m+1)]
for i in range(n):
    p=a[i]
    if 2*p<=m:
        for k in range(2,m//p+1):
            x[p*k]=-1

ans=0
dic=defaultdict(int)
for i in a:
    dic[i]+=1

for p in a:
    if x[p]==1 and dic[i]==1: ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
MAXA = 10**6+1
N = int(input())
A = list(map(int,input().split()))
A.append(MAXA)
A.sort()
hurui = [0]*(MAXA+1)
ans = 0
for j in range(N):
    a = A[j]
    if hurui[a] == 0 and A[j+1] != a:
        ans += 1
    for i in range(a,MAXA+1,a):
        if hurui[i] != 0:
            break
        hurui[i] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(set(list(map(int, input().split()))))
l = [1]*len(a)

for i in a:
    for j in range(len(a)):
        if i != a[j]:
            if a[j]%i == 0:
                l[j] = 0

if len(a) == 1:
    print(0)
    exit()

print(sum(l))

Submission status: Wrong Answer

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

def is_prime(m):
    for i in range(2,int(m**0.5)+1):
        if m%i==0:
            return False
    return True

def bunkai(m):
    pf={}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:
        pf[m]=1

p=set([])
double=set([])
for i in range(n):
    if A[i] in p:
        double|=set([A[i]])
    if is_prime(A[i]):
        p|=set([A[i]])
        continue
    flg=False
    for j in p:
        if A[i]%j==0:
            flg=True
            break
    if flg:
        continue
    else:
        p|=set([A[i]])
print(len(p)-len(double))

Submission status: Wrong Answer

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

A = sorted(A)
di = {}
count = 0

for i, a in enumerate(A):
    judge = True
    if a > 3:
        for j in di.keys():
            if a % j == 0:
                judge = False
                if a == j:
                    count -= di[j]
                    di[a] = 0
                break

        if judge:
            count += 1
            di[a] = 1
    else:
        if a not in di.keys():
            di[a] = 1
            count += 1
        else:
            count -= di[a]
            di[a] = 0

print(count)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

readline = sys.stdin.readline

n = int(input())
a = np.array(readline().split(), dtype=np.int64)
a.sort()
ans = 0
while len(a):
    if np.any(a[1::]==a[0]):
        a = a[a != a[0]]
        continue
    ans += 1
    a = a[a % a[0] != 0]
print(ans)

Submission status: Wrong Answer

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

a=sorted(a)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = []
ans = 0
while A:
    a = A.pop(0)
    f = 0
    for p in d:
        if a % p == 0:
            f = 1
            break
    if f == 0:
        d.append(a)
        if len(A) == 0:
            break
        if a == A[0]:
            t = 1
            while t == 1:
                if len(A) == 0:
                    t = 1
                    break
                if a == A[0]:
                    A.pop(0)
                else:
                    t = 0
        else:
            ans += 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
counter = Counter(A)
s = sorted(set(A))
A.sort()
if len(A) == 1:
    print(1)
else:
    lst = []
    ans = 0
    for a in s:
        lst.append(a)
        if counter[a] == 1:
            ans = 1
            break

    for i in range(1,len(s)):
        m = s[i]**0.5 + 1
        flg = True
        for p in lst:
            if s[i]%p == 0:
                flg = False
                break
            elif m < p:
                break
        if flg:
            lst.append(s[i])
            if counter[s[i]] == 1:
                ans += 1
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(map(int, input().split()))
S.sort()
ans = 0
if N > 1:
    if S[0] < S[1]:
        ans += 1
else:
    ans = 1
for i in range(N-1, 0, -1):
    num = S[i]
    M = int(num**0.5)+1
    flg = True
    for j in range(i):
        if num%S[j] == 0:
            flg = False
            break
        elif S[j] > M:
            break
    if num%S[i-1] == 0:
        flg = False
    elif i < N-1:
        if num%S[i+1] == 0:
            flg = False
    if flg:
        ans += 1
print(ans)

Submission status: Wrong Answer

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


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]


count = 0
for x in a:
    check = a.copy()
    check.remove(x)
    yaku = make_divisors(x)
    count_flag = True
    for y in yaku:
        if y != 1 and y in check:
            count_flag = False
            break

    if count_flag:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
a=list(map(int,input().split()))
a.sort()
s=10**6
s+=100
sosu_flag=[True for i in range(s)]
#素数であるかどうかの前計算
#素数をn倍していき倍数をどんどん塗りつぶしていくイメージ
ans=0
for i in a:
    if not sosu_flag[i]:
        continue
    ans+=1
    for j in range(i,s,i):
        sosu_flag[j]=False

c=Counter(a)
for key in c.keys():
    if c[key]>1:
        ans-=1
print(ans)

Submission status: Wrong Answer

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

w = []
cnt = 0

lc = list(c.keys())
lc.sort()
for i in lc:
  if c[i] != 1:
    continue
  else:
    res = 0
    for j in w:
      if i%j == 0:
        res = 1
        break
    if res == 0:    
      w.append(i)
      cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
M = int(input())
A=list(map(int,input().split()))
A=list(set(A))
A.sort()
k=0
if len(A)==1:
    print(0)


else:
    while True:
        
        if k==len(A):
            break
        for i in range(k,len(A)):
            delite=[]
            judge=0
            for j in range(i+1,len(A)):
                if A[j]%A[i]==0:
                    delite.append(j)
                    judge=1
            if judge==1:
                delite.reverse()
                for d in delite:
                    A.pop(d)
        k+=1
                
            
print(len(A))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

ans = 0
res = deepcopy(A)

if len(res) == 1:
    print(0)
    exit()

while res:
    ans += 1
    tmp = res.pop(0)
    res = [x for x in res if x % tmp != 0]

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
while A:
    B=[]
    a=A.pop(0)
    if len(A)>1:
        if a==A[0]:
            continue
    elif len(A)==1:
        if a==A[0]:
            break
    for i in range(len(A)):
        if A[i]%a!=0:
            B.append(A[i])
    A=B
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = set(A)
A.sort()
max = 10**6
ans = 0
C = dict()
for s in B:
    C[s] = True
for s in B:
    if not C[s]:
        continue
    if A.count(s) == 1:
        ans += 1
        i = 1
        while s*i <= max:
            C[s*i] = False
            i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
results = []
while(A):
  a = A.pop(0)
  oldnA = len(A)
  A = [i for i in A if i%a!=0]
  results.append(oldnA-len(A))
print(N-sum(results))

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
d = list(map(int, input().strip().split()))

# 重複しているやつは削除
counts = collections.Counter(d)
d = []
for a, c in counts.items():
    if c == 1:
        d.append(a)

d = sorted(d)
count = 0

while True:
    if len(d) == 0:
        break

    divisor = d[0]
    d = d[1:]
    count += 1
    d1 = []
    for a in d:
        if a % divisor != 0:
            d1.append(a)

    d = d1

print(count)