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

A_array.sort()

set_a = set(A_array)

ans = 0

if A_array[0] == 1:
    if N >= 2 and A_array[1] != 1:
        print(1)
    else:
        print(0)
    exit()
for i in range(N):
    a = A_array[i]
    if i != 0:
        if A_array[i] == A_array[i - 1]:
            continue
    if i != N - 1:
        if A_array[i] == A_array[i + 1]:
            continue
    for j in range(2, int(math.sqrt(a)) + 1):
        if a % j == 0:
            if j in set_a or ( a // j ) in set_a:
                break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n = int(input())
orga = list(map(int, input().split()))

if n==1:
    print(1)
    exit()
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)

aset=set(a)

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
N=int(input())
alist=list(map(int,input().split()))

adic=defaultdict(int)
for a in alist:
  adic[a]+=1


aset=set()
max_a=0
for a,v in adic.items():
  if v==1:
    aset.add(a)
    max_a=max(max_a,a)
  
if not aset:
  print(0)
  sys.exit(0)
  
tlist=[False]*(max_a+1)
for a in aset:
  tlist[a]=True
#print(tlist)

for i in range(1,len(tlist)):
  if not tlist[i]:
    continue
  else:
    for j in range(2*i,len(tlist),i):
      tlist[j]=False
      
#print(tlist)
answer=0
for t in tlist:
  if t:
    answer+=1
    
print(answer)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split()]
dic = collections.defaultdict(int)
for i in range(n):
    dic[a[i]] += 1
a = [i for i in dic.keys() if dic[i] == 1]
a.sort()

def get_sieve_of_eratosthenes_new(n_,ls,t):
    import math

    ans = []
    limit = t // 2
    data = ls
    while True:
        #print(ans)
        try:
            p = data[0]
            if limit <= p:
                return len(ans + data)
            ans.append(p)
            data = [e for e in data if e % p != 0]
        except:
            return len(ans + data)

if len(a):
    print(get_sieve_of_eratosthenes_new(n,a,a[-1]))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
def main():
  n = int(input())
  a = LI()
  ans = 0
  a.sort()
  for i in range(1,n):
    flag = True
    if i != n-1 and a[i] == a[i+1]: continue
    for j in range(i):
      if a[i] % a[j] == 0:
        flag = False
        break
    if flag: ans += 1

  if ans != 0: print(ans+1)
  else: print(0)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int , input().split()))
sa = set(a)
if len(sa) == 1:
    print(0)
    exit()

a.sort()
#print(a)
i = 0
while i < len(a):
    #print(len(a))
    ai = a[i]
    for j in reversed(range(i+1, len(a))):
        if a[j] % ai == 0:
            del a[j]
    #print(a)
    i += 1
print(len(a))

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])
if l[0]==1: print(1);exit()
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:
n = int(input())
A = list(map(int,input().split()))

a = sorted(A,reverse=True)
flag = [True]*n
for i in range(n):
  j = i+1
  while j<n:
    if a[i]%a[j] == 0:
      flag[i] = False
      break
    j += 1
    
print(flag.count(True))

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 c in range(a, 100001, a):
            if c in cand:
                cand.remove(c)
print(ans)

Submission status: Wrong Answer

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

N = len(A)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    A = kwargs["A"]
    A = sorted(A)
    res = n

    j = 1
    while j < n:
        if A[0] % A[j] == 0:
            res -= 1
            break

        j += 1

    for i in range(n):
        j = 0

        while j < i:
            if A[i] % A[j] == 0:
                res -= 1
                break

            j += 1

    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["n"] = [int(i) for i in cin][0]
    cin = input().split()
    kwargs["A"] = [int(i) for i in cin]

    cout = main(kwargs)
    print(cout)

Submission status: Wrong Answer

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

a = sorted(a)

cnt = 0

for i in a:
 
  for j in a:
    if i / 2 < j:
      continue
    else:
      if i % j == 0:
        cnt += 1
        break
        
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int , input().split()))
A = list(set(A))
A.sort(reverse=True)
count = 0
for i in range(0,len(A)-1):
    for j in range(i+1,len(A)):
        if A[i] % A[j] == 0:
            count += 1
            break
if max(A) == min(A):
    print(0)
else:
    print(max(0,len(A)-count))

Submission status: Wrong Answer

Solution code:
from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(0)
            exit()

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

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>MAX//2:
        break
print(len(Ps)+cnt)

Submission status: Wrong Answer

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

not_divisible = 0
for Ai in As:
    for Aj in As:
        if Ai==Aj:
            continue
        if Ai%Aj == 0:
            break
    else:
        not_divisible += 1
print(not_divisible)

Submission status: Wrong Answer

Solution code:
import math,sys
n=int(sys.stdin.readline())
a=list(map(int, sys.stdin.readline().split()))
d=dict()
for i in range(n):
    if d.get(a[i],None)==None:
        d[a[i]]=0
    d[a[i]]+=1 
ans=0
s=d.keys()
if 1 in s:
    if d[1]>1:
        print(0)
    else:
        print(1)
    sys.exit(0)
for i in range(n):
    if d[a[i]]>1 or (1 in s):
        continue 
    flag=True
    # print(a[i],end='    s\n')
    for ii in range(2,math.ceil(a[i]**(1/2))+1):
        if (a[i]%ii)==0:
            aa,bb=ii,a[i]//ii
            if aa in s:
                # print(aa)
                # print('aa')
                flag=False
                break
            if bb in s:
                # print('bb')
                # print(bb)
                flag=False
                break
    if(flag):
        # print(a[i])
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

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


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*i != n:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


setA = set(A)
countA = Counter(A)
count = 0
for num in A:
    if countA[num] >= 2:
        continue
    divisors = make_divisors(num)
    if all([e not in setA for e in divisors]):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(n):
        tmp = []
        for k in range(i):
            tmp.append(a[k])
            if a[k] > 0.5 * a[i]:
                break

        for j in range(1, int(a[i] ** 0.5) + 1):
            if a[i] % j == 0:
                if j in tmp or (a[i] // j) in tmp:
                    break
        else:
            if not (n > 1 and i < n - 1 and a[i] == a[i + 1]):
                ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
an=sorted(list(map(int,input().split())),reverse=True)
if not len(set(an))==len(an):
    print(0)
    exit()
c=0
for i,a in enumerate(an):
    for b in an[i+1:]:
        if a%b==0:
            c-=1
            break
    c+=1
print(c)

Submission status: Wrong Answer

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

a.sort()
cnt = 0
for i in range(1, n):
    flg = True
    for j in range(i):
        if a[i] % a[j] == 0:
            flg = False
            break
    if flg is True:
        cnt += 1
print(cnt+1)

Submission status: Wrong Answer

Solution code:
def calc():
    n, *a = map(int, open(0).read().split())
    r = set(a)
    count = 0
    for x in a:
        s = r & divs(x)
        if s:
            count += 1
    return count

def divs(x):
    ds = set()
    for i in range(2, x):
        if x % i == 0:
            ds.add(i)
    return ds

print(calc())

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
result = 0
B = sorted(A, reverse=True)

for a in range(N-1):
    
    for b in range(a+1,N):
        
        if B[a] % B[b] == 0:
            result+=1
            break

A.remove(B[N-1])
if B[N-1] in A:
    result+=1

print(N - result)

Submission status: Wrong Answer

Solution code:
def prime_factor(n,A):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    cnt = 0
    for i in range(N):
        if i > 0 and A[i] == A[i-1]:
            continue
        flag = False
        for j in range(N-1,i,-1):
            if A[i] % A[j] == 0:
                break
            if A[i] / 2 < A[j]:
                flag = True
                break
        else:
            flag = True
        if flag:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
b = []
import collections
c = collections.Counter(a)
for i in range(n):
    if c[a[i]] >= 2:
        pass
    else:
        b.append(a[i])
a = b
n = len(a)
ans = 0
for i in range(n):
    sw = 1
    for j in range(n-i,n):
        if a[i]%a[j] == 0:
            sw = 0
            break
    if sw == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))
newA = []
dic = Counter(A)
for key, val in dic.items():
    if val == 1:
        newA.append(key)

oks = []

for a in newA:
    for div in oks:
        if a % div == 0:
            break
    else:
        oks.append(a)
print(len(oks))

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    def is_p(v):
        i = 2
        while i * i <= v:
            if v % i == 0:
                return False
            i += 1
        return True
    primes = []
    for i in range(2, 1001):
        if is_p(i):
            primes.append(i)
    #print(primes)

    A.sort()
    ret = 0
    tmp = set()
    tmp2 = []
    for idx, v in enumerate(A):
        ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
        for p in primes:
            if ok or p * p > v:
                break
            if v % p == 0 and (p in tmp or v // p in tmp):
                ok = True
        #print(v, ok)
        if not ok:
            for t in tmp2:
                if ok or t * t > v:
                    break
                if v % t == 0:
                    ok = True
        if ok:
            pass
        else:
            tmp.add(v)
            tmp2.append(v)
            ret += 1
    print(ret)
    #tmp = []
    #for idx, v in enumerate(A):
    #    l = len(tmp)
    #    i = 0
    #    ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
    #    while not ok and i < l and tmp[i] * tmp[i] <= v:
    #        if v % tmp[i] == 0:
    #            ok = True
    #            break
    #        i += 1
    #    if ok:
    #        pass
    #    else:
    #        print(v)
    #        ret += 1
    #        tmp.append(v)
    #print(ret)
    #return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=map(int, input().split())
*a,=map(int, input().split())
sa=Counter(a)
sa1={ai for ai in sa if sa[ai]==1}
sa2={ai for ai in sa if sa[ai]>1}
# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    ad=True

    for i in range(1,min(int(ai**(1/2)+7),ai)):
        if ai%i==0:
            if (i in sa1 or i in sa2) and i!=ai:
                ad=False
                break
            if i>1 and (ai//i in sa1 or ai//i in sa2):
                ad=False
                break
    if ad:
        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):
    for j in reversed(range(i + 1, n)):
        if a[i] % a[j] == 0:
            break
        elif a[i] < 2 * a[j] or j == i + 1:
            ans += 1
            break

if a[n - 2] != a[n - 1]:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    group = []
    for i, a in enumerate(A):
        if i == 0:
            group.append(a)
        else:
            flag = 1
            for g in group:
                if a % g == 0:
                    flag = 0
                    break
            if flag:
                group.append(a)

    if len(group) != 1:
        print(len(group))
    else:
        print(0)
    
resolve()

Submission status: Wrong Answer

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

A.sort()
checked = []
ans = 0
before = 0
for i in A:
    if before == i and first:
        ans -= 1
        first = False
        break
    else:
        first = True
    flag = True
    for l in checked:
        if i % l == 0:
            flag = False
            break
    if flag:
        checked.append(i)
        ans += 1
    before = i

print(ans)

Submission status: Wrong Answer

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

n = int(input())
a = lmp()
a.sort()
p = set()
cnt = 0
for i in range(n):
    flag = True
    for j in range(i+1):
        if i == j:
            continue
        elif a[i] % a[j] == 0:
            flag = False
    if flag:
        cnt += 1
for i in range(1, n):
    if a[0] % a[i] == 0:
        cnt -= 1
        break
print(cnt)

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,10**6+1,k):
        print(k,i)
        if i in l:
            ng.add(i)
            
            

print(ans-len(ng))

Submission status: Wrong Answer

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
#mod = np.array([[-1 for i in range(N)] for i 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]
    
count = 0
for i in range(N):
    buf = make_divisors(A[i])
    if len(set(A) - set(buf)) == N-1:
        count += 1

#count = 0
#for i in range(N):
#        mod[i] = np.mod(A,A[i])
#for i in range(N):
#    c = list(mod[:,i]).count(0)
#    if c == 1:
#        count += 1
#        
print(count)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A = list(set(A))
    
    ans = 0
    
    if len(A) == 1:
        print(0)
    else:
        for i in range(len(A)):
            now = A[i]
            for j in range(0,i):
                if now/A[j] == now//A[j]:
                    break
            else:
                ans += 1
        
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,collections
input=sys.stdin.readline
sn=int(input())
l=list(map(int,input().split()))
c = collections.Counter(l)
if 1 in c:
  if c[1]==1:
    print(1)
    quit()
  else:
    print(0)
    quit()
x=[y for y in c if c[y]==1]
x.sort()
def div(n):
    ass = set([n])
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ass.add(i)
            ass.add(n//i)
    return ass 
ans=1
if len(x)==0:
  print(0)
else:
  s=set([x[0]])
  for y in x[1:]:
    memo=0
    if s.isdisjoint(div(y)):
        ans+=1
    s.add(y)
  print(ans)

Submission status: Wrong Answer

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

    N = int(input())
    A = tuple(map(int, input().split()))
    counter_A = Counter(A)
    
    count = 0
    for i in counter_A.keys():
        if counter_A[i] > 1:
            continue
        flag = True
        j = 2
        while j*j <= i:
            if i % j != 0 :
                j += 1
                continue
            if j in counter_A :
                flag = False
                break
            j += 1

        if flag:
            count += 1

    print(count)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

if __name__ == '__main__':
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    ans = 0
    # aa = np.argsort(a)

    odds = [i for i in a if i % 2 == 1]
    arg_sorted_odds = np.argsort(odds)
    evens = [i for i in a if i % 2 == 0]
    arg_sorted_evens = np.argsort(evens)


    for a, aa in zip([odds, evens], [arg_sorted_odds, arg_sorted_evens]):
        for i in range(0, len(a)):
            if not a[i] in a[:i] + a[i + 1:]:
                flag = 0
                for j in range(0, i):
                    if a[aa[i]] % a[aa[j]] == 0:
                        flag = 1
                        break
                if flag == 0:
                    ans += 1

    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

num = 0
A.sort(reverse = True)
for i in range(N-1):
    if i >= 1:
        if A[i] % A[i-1] == 0:
            continue
    for j in range(i+1, N):
        if A[i] % A[j] == 0:
            break
    else:
        num += 1

if not (A[N-1] == A[N-2]):
    num += 1
print(num)

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)

    # divisors.sort()　#小さい順位欲しいとき
    return divisors

n=int(input())
a=sorted(list(map(int,input().split())))
dic={}
for k in a:
    if k in dic:
        dic[k]=0
        continue
    f=1
    x=make_divisors(k)
    for i in x:
        if i in dic:
            f=0
            break
    if f:
        dic[k]=1
print(sum(dic.values()))

Submission status: Wrong Answer

Solution code:
n = int(input())

from collections import deque

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

aa = deque(sorted(a))

count = 0

def op(count, aa):
    newaa = deque()
    piv = aa.popleft()
    if len(aa) == 0 or piv != aa[-1]:
        count += 1
#         print(f'count{aa=}, {piv=}, {count=}')
#     else:
#         print(f'not count{aa=}, {piv=}, {count=}')
    while len(aa):
        trans = aa.popleft()
        if trans % piv:
            newaa.append(trans)
    aa = newaa
    return count, aa

def ans(count, aa):
    if len(aa) ==1:
#         print('cond1')
        return 1
    if aa[0] == aa[1] == 1:
#         print('cond2')
        return 0
    if aa[0] == 1:
#         print('cond3')
        return 1
    while len(aa):
#         print('cond4')
        count, aa = op(count, aa)
    return count


print(ans(count, aa))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input().split()
A = [int(s) for s in A]
list.sort(A, reverse=True)

count = 0

for i in range(N):
    flag = 0
    for j in reversed(range(i+1, N)):
        if A[i]%A[j] == 0:
            flag = 1
            break
    if A[N-1] == A[N-2]:
        flag = 1
    if flag == 1:
        count += 1

print(N-count)

Submission status: Wrong Answer

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

cnt = 0

while cnt < len(A):
  div = A[cnt]
  delete_index = []
  for k in range(cnt+1, len(A)):
    amari = A[k] % div
    if amari == 0:
      delete_index.append(k)
  for j in sorted(delete_index, reverse=True):
    A.pop(j)
  cnt += 1

if len(A)==1 and A[0]==first:
  print(0)
else:
  print(len(A))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    if N==1:
        print(0)
        return
        
    A=lispin()
    B=sorted(A)
    #print(B)
    
    ans=0
    if B[0]<B[1]:ans+=1
    must_see=[]
    must_see.append(B[0])
    for cnt in range(1,10**7):
        if cnt>=N:break
        temp=B[cnt]
        cond=1
        for i in must_see:
            if temp%i==0:
                cond=0
                break
        if cond==1:
            ans+=1
            must_see.append(temp)
    print(ans)

            


#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

N,*A = map(int, open(0).read().split())
As = set(A)
Ac = [x for x in Counter(A).items() if x[1] > 1]
div = [make_divisors(x) for x in A]
ans = sum([-x[1] for x in Ac])
for x in div:
    for y in x:
        if y in As:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from typing import List


def not_divisible(A: List[int]) -> int:
    A = sorted(A)
    B = []
    for a in A:
        for b in B:
            # print("{} % {} = {}".format(a, b, a % b))
            if not (a % b):
                # print("break")
                break
        else:
            B.append(a)

    return len(B)


if __name__ == "__main__":
    _ = int(input())
    A = [int(a) for a in input().split()]
    ans = not_divisible(A)
    print(ans)

Submission status: Wrong Answer

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

if A.count(A[0])==N:
    print(0)
    exit(0)

flag = [0 for _ in range(N)]
for n in range(N):
    if flag[n] == 1: continue
    for i in range(n+1,N):
        if A[i]%A[n] == 0:
            flag[i] = 1

print(N-sum(flag))

Submission status: Wrong Answer

Solution code:

def div(arr, n):

    s = dict()
    max_ele = -10 ** 9
    for i in range(n):
        s[arr[i]] = 1

        max_ele = max(max_ele, arr[i])
    res = dict()
    for i in range(n):

        if (arr[i] != 0):

            for j in range(arr[i] * 2,
                           max_ele + 1, arr[i]):

                if (j in s.keys()):
                    res[j] = 1
    return len(res)

n=int(input())
a=list(map(int,input().split()))
if len(list(set(a)))==1:
    print(0)
else:
    print(n-div(a,n))

Submission status: Wrong Answer

Solution code:
import copy

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

aset = list(set(al))
aset.sort()

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

def rmlis(ase, i):
    aset_new = ase.copy()
    x = ase[i]
    rm_cnt = 0

    for j in range(i+1, len(ase)):
        if ase[j]%x == 0:
            aset_new.pop(j - rm_cnt)
            rm_cnt += 1
    return aset_new

flag = True
k = 0
lis = aset
while flag:
    lis = rmlis(lis, k)
    if k+1 >= len(lis):
        print(len(lis))
        exit()
    else:

        if lis[-1] < lis[k+1] *2:
            flag = False
            print(len(lis))
            exit()
        else:
            k += 1

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=sorted(a)
ct=0
for i in range(n):
    t=0
    d=0
    while d==0:
        if b[i]%b[t]==0 and i!=t:
            d+=1
            ct+=1
        elif b[t]>b[i]/2:
            d+=1
        else:
            t+=1
print(n-ct)

Submission status: Wrong Answer

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

if(len(set(a))==1 and len(a)>1):
    print(0)
    exit()
    
a.sort()
#print(a)
i=0
j=1
while(i<=n):
    j=i+1
    while(j<n):

        if(a[j]%a[i]==0):
            a.pop(j)
            n-=1
            continue
        j+=1

    i+=1
           
#print(a)

print(len(a))

Submission status: Wrong Answer

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

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

n = int(input())
a = [int(x) for x in input().split()]
a_set = set(a)

num = set()
for i in range(n):
    num.add(i)
a.sort()
for i in range(n):
    for j in range(i + 1, n):
        if a[j] % a[i] == 0:
            num.discard(j)
            
print(len(num))

Submission status: Wrong Answer

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

print(ans)

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+1):
    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
# Your code here!
num = int(input())
array = list(map(int,input().split()))
count = 0
res = 0
for i,j in enumerate(array):
    for m,n in enumerate(array):
        if i != m:
            if j % n != 0:
                #print(j,n)
                #print(j % n)
                count += 1
                #print(count)
                if count == num - 1:
                    res += 1
    count = 0
                    
print(res)