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 sys import stdin


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


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    A_arr = list(map(int, _in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    A_div = [[] for i in range(N)]
    for i, A in enumerate(A_arr):
        _ = make_divisors(A)
        _.remove(1)
        A_div[i] = set(_)

    ans = 0
    for i, A_d in enumerate(A_div):
        for j, A in enumerate(A_arr):
            if i != j and A in A_d:
                break
        else:
            ans += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    answer = n
    chk = [0 for _ in range(a[-1] + 1)]
    for aa in a:
        chk[aa] += 1
    for i in range(a[-1] + 1):
        if chk[i] == 1:
            for j in range(2 * i, a[-1] + 1, i):
                answer -= chk[j]
                chk[j] = 0
        else:
            answer -= chk[i]
    answer = max(answer, 0)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [1]*(10**6+1)
for i in range(n):
    if (flag[a[i]]==1):
        for j in range(2*a[i],10**6+1,a[i]):
            
            flag[j] = 0
x = collections.Counter(a)
ans = 0
for i in a:
    if (flag[i]==1):
        ans += 1
        flag[i]=0
        if (x[i]>2):
            ans -=1
print(ans)

Submission status: Wrong Answer

Solution code:

import collections

def main():
  n = int(input())
  A = tuple(map(int, input().split()))
  D = collections.defaultdict(int)
  for a in A:
    D[a] += 1

  ans = n

  for i in range(n):
    a = A[i]
    for j in range(1, a // 2 + 1):
      if j not in D:
        continue

      if a == j and D[a] == 1:
        continue

      if a % j == 0:
        ans -= 1
        break

  print(ans)


main()

Submission status: Wrong Answer

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

for i in range(1,n):
    flag=True
    for j in range(i):
        if i != j:
            if a[i]%a[j]==0:
                flag=False
                break
    if flag:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from math import sqrt
from collections import Counter, deque
N = int(input())
As = list(mapint())
As.sort()
C = Counter(As)

MAX = As[-1]
Ps = deque(As)
cnt = 0
while Ps:
    p = Ps.popleft()
    Ps = deque([i for i in Ps if i%p!=0])
    if C[p]>=2:
        continue
    cnt += 1
    if p>sqrt(MAX):
        break
print(len(Ps)+cnt)

Submission status: Wrong Answer

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

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

    setA = set(As)

    def divisor(n):
        i = 1
        ans = []
        while i*i <= n:
            if n%i == 0 and i != n:
                ans.append(i)
                if i != n//i and n//i != n:
                    ans.append(n//i)
            i += 1
        return ans

    dic = {}
    duplicates = set()
    for a in As:
        if not a in dic:
            dic[a] = 0
        else:
            duplicates.add(a)
        dic[a] += 1


    ans = 0
    for a in As:
        is_ok = True
        for d in divisor(a):
            if d in setA:
                is_ok = False
                break

        if is_ok:
            ans += 1

    for x in duplicates:
        ans -= dic[x]

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

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

A = list(B)
A.sort()
#print(A)
ans = -1

for i in reversed(range(len(A))):
    jdg = 0
    a = A[i] // 2
    index = bisect.bisect_right(A,a)
    #print(index,a)
    for k in range(index-1):
        if A[i] % A[k] == 0:
            jdg += 1
            break
    if jdg == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    if n == 1:
        print(0)
        return
    nums.sort()
    #nums = list(reversed(nums))
    checkList = [True] * n
    if nums[0] == nums[1]:
        checkList[0] = False
    
    for i in range(n):
        for j in range(i + 1, n):
            #print(nums[j], nums[i])
            if not checkList[j]:
                break
            if nums[j] % nums[i] == 0:
                checkList[j] = False
        #print(nums)
        #print(checkList)
    print(sum(checkList))


    
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
# a = sorted(a)
a.sort()
check = True
ans = 0
double = []
for i in range(n):
    if not i == 0:
        if a[i-1] == a[i]:
            double.append(a[i])
    for j in range(0, i):
        if i == j:
            continue
        if a[i]%a[j] == 0:
            check = False
            break

    if check:
        ans += 1
        # print(i)
    check = True

ans -= len(set(double))
print(ans)

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*m in s:
        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:
n = int(input())
A = list(map(int, input().split()))
set_A = set(A)
if len(A) != len(set_A):
    print(0)
else:
    factors = {}
    for a in A:
        a_orig = a
        for i in range(2, int(a**(1/2))+1):
            cnt = 0
            while a % i == 0:
                a /= i
                cnt += 1
            if cnt > 0:
                factors[i] = cnt
        if a == a_orig:
            factors[a] = 1
    print(len(factors))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    import math
    from collections import Counter
    N=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))
    A.sort()

    A_counter=Counter(A)

    L=[]
    count=0
    for a in A:
        if a==0:
            continue
        flag=True
        for s in L:
            if s>math.sqrt(a):
                break
            if a%s==0:
                flag=False
                break
        if flag:
            L.append(a)
            if A_counter[a]==1:
                count+=1
    
    print(count)

main()

Submission status: Wrong Answer

Solution code:
# D

n = int(input())
a_list = [int(x) for x in input().split()]
f_list = [True]*n
a_list.sort(reverse=True)

for i in range(n):
    _q = a_list[i]
    if i > 1 and _q == a_list[i-1]:
        f_list[i] = False
        continue
    for j in range(i+1,n):
        if _q % a_list[j] == 0:
            f_list[i] = False
            break

ans = sum(x for x in f_list)
print(ans)

Submission status: Wrong Answer

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

ret = 0
for i in range(len(A)):
    cnt = 0
    for j in range(len(A)):
        if i == j:
            continue
        
        if A[i] % A[j] == 0:
            cnt += 1
            break
    if cnt > 0:
        ret += 1
        
print(N - ret)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(set(map(int, input().split())))
a.sort()

if len(a) == 1:
    print(0)
else:
    ans = 1
    for i in range(1, len(a)):
        check = a[i]
        ok = True
        for j in range(i):
            if check % a[j] == 0:
                ok = False
                break
        if ok:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
for a in A:
    for i in range(len(A)):
        if a % A[i] == 0 and a != A[i]:
            count += 1
            break
if(count != 0):
    print(N-count)
else:
    print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-06-14 21:22:25 +0900
# LastModified: 2020-06-14 21:41:02 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd


def main():
    n = int(input())
    a = list(map(int,input().split()))
    a.sort(reverse=True)
    count=0
    for i in range(0,n):
        for j in range(i+1,n):
            if a[i]%a[j]==0:
                count+=1
                break

    if n>1 and a[n-1]==a[n-2]:
        count+=1

    print(n-count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

cnt = Counter(A)
A.sort()
ans = 0
for j in range(len(A)):

    a = A[j]
    if cnt[a] > 1:
        continue
    if j==0:
        ans+=1
    i = bisect.bisect_left(A, pow(a,0.5))


    ok = True

    while(i>=0):
        if a % A[i]==0:
            #print (a,A[i])
            ok = False
            break
        i-=1
    if ok:
        #print(a)
        ans+=1
print (ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 21:14:26 2020

@author: NEC-PCuser
"""

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

A.sort()


li = []
before_value = 0
next_flg = False
for n in A:
    if len(li) == 0:
        li.append(n)
        next_flg = True
    if before_value == n:
        if li[len(li) - 1] == n:
            li.pop(len(li) - 1)
        next_flg = False
        before_value = n
        continue
    before_value = n
    if next_flg is True:
        next_flg = False
        continue
    for i in range(0, len(li)):
        if (n % li[i] == 0):
            break
        if (n < li[i] * 2):
            li.append(n)
            break
    else:
        li.append(n)

print(len(li))

Submission status: Wrong Answer

Solution code:
N = int(input())
x_list = sorted(list(map(int, input().split())), reverse=True)

count = 1
for i, xi in enumerate(x_list):
  for xj in x_list[i+1:]:
    if xi%xj == 0:
      break
    if xj == x_list[-1]:
      count += 1
print(count)

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()
D = list(B)
nn = len(D)
for s in B:
    C[s] = True
for iii, s in enumerate(B):
    if not C[s]:
        continue
    if A.count(s) == 1:
        ans += 1
    while iii <= nn-1:
        if D[iii] % s == 0:
            C[D[iii]] = False
        iii += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    
    N = II()
    A = LI()
    As = sorted(A, reverse=True)
    ans = N

    if len(set(A)) == 1:
        print(0)
    else:
        for i in range(N-1):
            k = N-1
            for j in range(N):
                if k == i:
                    break
                if As[i] % As[k] == 0:
                    ans -= 1
                    break

                k -= 1


        print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n= int(input())
a = list(map(int, input().split()))
q = [0]*n

for i in range(n):
    for j in range(i,n):
        if i == j:
            continue
        if a[i] % a[j] == 0:
            q[i] = 1
            break

print(n-sum(q)-1)

Submission status: Wrong Answer

Solution code:
from numba import jit


@jit
def solve(N, A):
    ans = 0
    for i in range(N):
        for j in range(N):
            if i != j:
                if A[i]%A[j] == 0:
                    break
                if j == N-1:
                    ans += 1
                if (i == N-1) and (j == N-2):
                    ans += 1
    return ans


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

ans = solve(N,A)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())

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

A.sort()

lis=[A[0]]

for i in range(1,n):
    c=0
    for j in lis:
        if A[i]%j==0:
            c+=1
            break
    if c==0:
        lis.append(A[i])

s=set()
for i in range(n-1):
    if A[i]==A[i+1]:
        s.add(A[i])

print(len(lis)-len(s))

Submission status: Wrong Answer

Solution code:
from collections import OrderedDict

n = int(input())
a = list(map(int, input().split()))
a.sort()
my_s = set()
dup = set()
for item in a:
    if item in my_s:
        dup.add(item)
    else:
        my_s.add(item)

ret = 0
cand = OrderedDict()

for i in range(n):
    is_ok = True
    if a[i] in dup:
        continue
    else:
        for key in cand.keys():
            if a[i] % key == 0:
                is_ok = False
                break
            else:
                continue
        if is_ok:
            ret += 1
            cand[a[i]] = 1

print(ret)

Submission status: Wrong Answer

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

a.sort()
b = []
c = 0
for i, v in enumerate(a):
    flag = True
    for j in b:          
        if v % j == 0:
            flag = False
            break
        elif v / 2 <= j:
            break
    if flag == True:
        b.append(v)
        if i+1 >= len(a):
            c += 1
        elif a[i+1] != v:
            c += 1

print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)
ans=0
if n==1:
    ans=1
else:
    for x in range(n-1):
        ch=0
        for y in range(n-x-1):
            if a[x]%a[-1-y]==0:
                ch=1
                break
            if a[-1-y]>a[x]/2:
                break
        if ch==0:
            ans+=1
    if a[-1]%a[-2]!=0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
from collections import Counter
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    A = list(geta(int))

    A.sort()
    S = set()

    ans = 0

    C = Counter(A)
    for k in C:
        if C[k] > 1:
            ans -= 1

    for a in A:
        ok = True
        for s in S:
            if a % s == 0:
                ok = False
                break
        if ok:
            ans += 1
            S.add(a)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# D 

from collections import deque
N=int(input())
A=list(map(int,input().split()))
A.sort()
B=deque(A)
#print(B)

cnt=0
tmp=[]
while B:
    i = B.popleft()
    for j in B:
        if j==i:
            break
        elif j%i==0:
            pass
        else:
            tmp.append(j)
    else:
        cnt += 1
        #print(i,tmp,cnt)
        B=deque(tmp)
        tmp=[]
        continue
    break
print(cnt)

Submission status: Wrong Answer

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

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 reversed(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()))
a.sort()
count=n
for i in range(n-1):
    if a[i]==a[i+1]:
        count-=1
a=set(a)
for i in a:
    a.remove(i)
    for j in a:
        if i%j==0:
            count-=1
            break
    a.add(i)
print(count)

Submission status: Wrong Answer

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

A.sort(reverse=True)
ans = 0
flag = True

while A:
  n = A.pop()
  b = A[:]
  # if n > max(A)**0.5+1:
  #   break
  for j in range(len(A)):
    if A[j] == n:
      flag = False
      b.remove(A[j])
    elif A[j]%n == 0:
      b.remove(A[j])
  if flag:
    ans += 1
    
  A=b


print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


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

    ans.append(n)

    return sorted(ans)


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

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

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

    for a in A:
        if a == 1:
            return 0
        is_in_A_flag[a] += 1

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        # for b in B[i][:-1]:
        for j in range(len(B[i])-1):
            b = B[i][j]
            if is_in_A_flag[b] > 0:
                is_ans = False
                break

        if is_ans:
            if is_in_A_flag[B[i][-1]] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
A.sort()
s = set()
ans = N

if len(set(A))==1:
    print(0)
else:
    for b in A:
        n = b
        for i in range(2, int(n**0.5)+1):
            while n%i==0:
                n //= i
                if n in s:
                    break
            if b//n in s or b in s:
                ans -= 1
                s.add(b)
                break
            if not n:
                break
        else:
            s.add(b)
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
 
## input
 
# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]

def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
 
N=int(input())
A=list(map(int, input().split()))


A.sort()
count = 0

for i in range(0,N):
    if A.count(A[i]) >= 2:
        continue
    elif is_prime(A[i]):
        count += 1
        continue
    else:
        for j in range(0,i+1):
            if A[i]%A[j]==0:
                break
            if j == i-1:
                count += 1

print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A.sort(reverse=True)
ans = N

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
checked = [True] * N
cnt = Counter(A)
ans = 0
for i, a in enumerate(A):
    if cnt[a] > 1 or not checked[i]: continue
    ans += 1
    for j in range(i+1, N):
        if A[j] % a == 0: checked[j] = False
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    answer = n
    chk = [0 for _ in range(a[-1] + 1)]
    for aa in a:
        chk[aa] += 1
    for i in range(a[-1] + 1):
        if chk[i] == 1:
            for j in range(2 * i, a[-1] + 1, i):
                answer -= chk[j]
                chk[j] = 0
        else:
            answer -= chk[i]
    if a[0] == 1:
        answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

a = set(a)
max = max(a)
ans = 0
if len(set(a))==1:
    print(0)
    exit()

while len(a) > 0:
    i = a.pop()
    ans+=1
    n = 1
    remove_set = set()
    while i != 1 and i*n <= max:
        remove_set.add(i*n)
        n+=1
    a = a - remove_set

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from math import sqrt
from collections import Counter, deque
N = int(input())
As = list(mapint())
As.sort()
C = Counter(As)

MAX = As[-1]
Ps = deque(As)
cnt = 0
while Ps:
    p = Ps.popleft()
    if C[p]>=2:
        continue
    Ps = deque([i for i in Ps if i%p!=0])
    cnt += 1
    if p>sqrt(MAX):
        break
print(len(Ps)+cnt)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
cA = collections.Counter([int(_) for _ in input().split()])
cand = set(range(1, 100001))
ans = 0
for a in sorted(cA.keys()):
    if a in cand:
        if cA[a] == 1:
            ans += 1
        for i in range(1, 1 + 99999 // a):
            if a * i in cand:
                cand.remove(a * i)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted([int(i) for i in input().split()])
l=[]
c=0
for i in range(n-1,-1,-1):
    if i in l:
        continue
    f=True
    for j in range(i):
        if a[i]%a[j]==0:
            l.append(i)
            f=False
    if f:
        c+=1
print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque
import collections

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

    c = collections.Counter(A)
    # 重複排除
    B = sorted([k for k, v in c.items() if v == 1])
    dq = deque()
    before = 0
    for b in B:
        dq.append(b)

    ans = 0
    while dq:
        a = dq.popleft()
        ans += 1
        dq2 = deque()
        while dq:
            a2 = dq.popleft()
            if a2 % a:
                dq2.append(a2)
        dq = dq2

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
if A[0]==A[N-1]:
    print(0)
else:
    ans=[]
    mini=A.pop(0)
    ans.append(mini)
    for n in range(len(A)):
        c=0
        for x in ans:
            if A[n]%x==0:
                c=1
                break
        if c==0:
            ans.append(A[n])
    print(len(ans))

Submission status: Wrong Answer

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

answers = ais[:]

for i in ais:
  for ans in answers:
    if (ans != i or (ais.count(i) != 1)) & (ans%i == 0):
      answers.remove(ans)

print(len(answers))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
A.sort()
ans = 0

cnd = []
for i, a in enumerate(A):
    if i != n - 1 and A[i + 1] == a or i != 0 and A[i - 1] == a:
        continue
    do_count = True
    for c in cnd:
        if a % c == 0:
            do_count = False
            break
    if do_count:
        cnd.append(a)
        ans += 1
print(ans)

Submission status: Wrong Answer

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

A.sort()

ans = 0

for i in range(N):
    flag = True
    for j in range(0, i+1):
        if i==j:
            if i == 0:
                flag = False
            continue
        if A[i] % A[j] == 0:
            flag = False
            break
    
    if flag:
        # print(i)
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


@lru_cache(maxsize=None)
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


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A.sort()

    ans = 0
    s = set()
    for a in A:
        divs = make_divisors(a)
        for div in divs:
            if div in s:
                break
        else:
            ans += 1
        s.add(a)

    c = collections.Counter(A)
    for x in c.most_common():
        if x[1] > 1:
            ans -= 1
        else:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def Sieve(N, AList):
    AList.sort()
    N_NotDivisible = 0
    while( len(AList) > 0 ):
        N_NotDivisible+= 1
        value = AList[0]
        AList.pop(0)
        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()

    Aset = set()
    for i in range(N):
        Aset.add( int(AList_str[i]) )
    AList = list(Aset)
    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)

Submission status: Wrong Answer

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

max_A = max(A)
table = [False]*(max_A+1)
for i in A:
    if table[i] == False:
        table[i] = True
    else:
        table[i] = -1
        
for i in A:
    if table[i] == -1:
        table[i] = False

for i in range(1, max_A):
    if table[i] == True:
        n = 2
        while i*n < max_A+1:
            table[i*n] = False
            n += 1
        
print(table.count(True))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def BinarySearch(num, List):
    if len(List) == 0:
        print("Erorr : list has no element")
        return
    left,right = 0,len(List)
    while left < right:
        mid  = (left+right)//2
        if num < List[mid]:#
            right = mid
        else:
            left = mid + 1
    return right


def main():
    nn = ni()
    a = sorted(list(set(na())))
    n = len(a)
    if n == 1:
        if nn == 1:
            print(1)
        else:
            print(0)
        return
    asub = [i for i in a]
    ans = 0
    for i in range(n):
        ai = a[i]
        if ai != -1:
            ans += 1
            cnt = 2
            right = 0
            while right != n:
                right = BinarySearch(ai*cnt, asub)
                if a[right-1] == ai*cnt:
                    a[right-1] = -1
                cnt += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = sorted(inpl())
check = [True] * n
ans = 0
for i in range(n):
    if i != n - 1 and a[i] == a[i + 1]:
        check[i + 1] = False
        continue
    if not check[i]:
        continue
    for j in range(i + 1, n):
        if not check[j]:
            continue
        if a[j] % a[i] == 0:
            check[j] = False
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())))
if 1 < len(a):
    c = 1 if a[0] == a[1] else 0
else:
    c =0
for i in range(n):
    x = a[i]
    for j in range(i):
        if x % a[j] == 0:
            break
    else:
        continue
    c+=1
print(n-c)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
r=0
import numpy as np
for ii in range(len(a)):
  for jj in np.arange(ii+1,len(a)):
    if a[ii]%a[jj]==0:
      break
    if jj==len(a)-1:
      r+=1
  if ii==len(a)-1:
    if a.count(a[ii])==1:
      r+=1
  #print(a[ii],r)
print(r)