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 numpy as np
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * n
for i, num in enumerate(a):
    if flag[i]:
        for j in range(i+1, n):
            if a[j]%num == 0:
                flag[j] = False
print(int(np.count_nonzero(flag)))

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
cnt = 0
ANS = [0] * (10**6+1)
for i in A:
    ANS[i-1] = 1
if A[0] == 1:
    print(1)
    exit()
for i in range(n-1):
    if ANS[A[i]-1] == 0:
        continue
    else:
        for j in range(i+1,n):
            if A[j]%A[i] == 0:
                ANS[A[j]-1] = 0
#print(ANS)
from collections import Counter
dic = Counter(A)
#print(dic)
for k,v in dic.items():
    if v >= 2:
        ANS[k-1] = 0
print(sum(ANS))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
fl = 0
ans = 0
for i in range(1,n):
    for j in range(i+1,n):
        if (a[i]*1000)%a[j] != 0:
            #print(i+1,j+1,a[i])
            ans += 1
            fl = 1
            break
            
if fl == 0:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

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

A.sort()
count = 0
last_num = 0
flag = True
now_num = 0

count_flag = False
for i in range(N):
    count_flag = True
    now_num = A[i]

    if now_num == last_num:
        if flag:
            count -= 1
            flag = False
    else:
        if not flag:
            flag = True
        for j in range(0, i):
            if now_num % A[j] == 0:
                count_flag = False
                break
        if count_flag:
            count += 1
        last_num = A[i]
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

def divisor(n): #nの約数を全て求める
  i = 1
  table = []
  while i * i <= n:
    if n%i == 0:
      table.append(i)
      table.append(n//i)
    i += 1
  table = list(set(table))
  return table

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

for a in A:
  if a == 0:
    print(0)
    exit()
B = []
for a in A:
  B += [divisor(a)]

s = set()
ans = 0
"""
for i in range(N):
  if i == 0:
    s |= set(B[i])
  else:
    if len(set(B[i]) & s) == 1:
      ans += 1
    s.add(A[i])
"""
for i in range(N):
  s = set(A[:i]+A[i+1:]) 
  if len(s) == 0:
    continue
  if len(set(B[i]) & s) == 0:
    ans += 1
"""
c = set()
for i in range(1, N):
  c.add(A[i])
if len(c & set(B[0])) == 0:
  ans += 1
"""
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    arr = list(map(int, input().split(" ")))
    arr_sorted = sorted(arr)
    if len(arr_sorted) == 1:
        return 0
    else:
        if arr_sorted[0] == arr_sorted[1]:
            count = 0
        else:
            count = 1

    for n in range(1, N):
        target = arr_sorted[n]
        sub_arr = arr_sorted[:n]
        flag = False
        for a in sub_arr:
            if target % a == 0:
                flag = True
                break
        if not flag:
            count += 1
    print(count)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter 
import sys

def divisors(n):#without itselfs
    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)

    return divisors

def main():

    n = int(input())

    inp = sys.stdin.readline
    a = inp().split()
    a.pop()
    a = list([int(t)for t in a])
    a_set = set(a)
    c = Counter(a)

    ans = 0

    for a_i in a:
        divs = set(divisors(a_i))
        t = divs.intersection(a_set)
        if len(t)==0 and c[a_i]==1:
            ans+=1

    print(ans)
            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
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

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

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]


# ここから書き始める
n = int(input())
a = sorted(list(map(int, input().split())))
cnt = 0
cnt1 = a.count(1)
if cnt1 > 1:
    print(0)
    sys.exit()
elif cnt1 == 1:
    print(1)
    sys.exit()
for i in range(n):
    d = make_divisors(a[i])[:-1]
    # print(d)
    if len(d) == 1:
        if i == 0 and a[i] != a[i + 1]:
            cnt += 1
        if i == n - 1 and a[i - 1] != a[i]:
            cnt += 1
        if i not in [0, n - 1] and a[i - 1] != a[i] and a[i] != a[i + 1]:
            cnt += 1
        continue
    for j in d:
        if a[bisect_left(a, j)] == j:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=set()
def divisor_enu(N):
   temp=[]
   for i in range(2,int(N**0.5)+1):
      if N%i==0:
         while N%i==0:
            N//=i
         if i in X or N in X:
            return None
         else:
            temp.append(i)
   if N != 1:
      X.add(N)
   for k in temp:
      X.add(k)
S=list(map(int,input().split()))
if set(S) == 1:
   print(0)
   exit()
S.sort()
for j in S:
   divisor_enu(j)
print(len(X))

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = set(map(int,input().split()))
if len(A)==1:
  print(0)
  sys.exit()
divisible = int()
for i in A:
  rest = A - set([i])
  for r in rest:
    if i % r == 0:
      divisible += 1
      break
print(N - divisible)

Submission status: Wrong Answer

Solution code:
from numba import njit, int32, int64
from numba.typed import Dict

@njit
def solve(B):
    A = Dict.empty(
        key_type=int64,
        value_type=int64)
    for b in B:
      A[b] = A.get(b, 0) + 1
    r = 0
    for a, v in A.items():
        if v > 1:
            continue
        if 1 in A:
            continue
        i = 2
        while i * i <= a:
            if a % i == 0:
                if i in A:
                    break
                if a // i in A:
                    break
            i += 1
        else:
            r += 1
    return r

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

print(main())

Submission status: Wrong Answer

Solution code:
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(" ")))
g=0

for i in range(n):
  if is_prime(n):
    for j in range(n):
      if i!=j:
        if A[i]%A[j]==0:
          g=g+1
          break
print(n-g)

Submission status: Wrong Answer

Solution code:
N = int(input())

def divisor(n): #nの約数を全て求める
  i = 1
  table = []
  while i * i <= n:
    if n%i == 0:
      table.append(i)
      table.append(n//i)
    i += 1
  table = list(set(table))
  return table

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

for a in A:
  if a == 0:
    print(0)
    exit()
B = []
for a in A:
  B += [divisor(a)]

s = set()
ans = 0

for i in range(N):
  s = set(A[:i]+A[i+1:]) 
  if len(s) == 0:
    continue
  if len(set(B[i]) & s) == 0:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=1)
B=[]
while A:
    x=A.pop()
    if A:
        if x!=A[-1]:
            B.append(x)
        else:
            while A:
                y=A.pop()
                if y!=x:
                    A.append(y)
                    break
    else:
        B.append(x)


ans=0
for x in B:
    for y in B:
        if y>=x:
            ans+=1
            break
        if x%y==0:
            break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7


def get_divisors(n):
    divs = []
    for i in range(2, int(n**0.5)+1):
        c = 0
        while n % i == 0:
            n = n // i
            c += 1
        if c > 0:
            divs.append((i, c))
    if n > 1:
        divs.append((n, 1))
    return divs

N = ri()
A = rl()

import collections

cnt = collections.Counter(A)
A = []
for k, v in cnt.items():
	if v > 1: continue
	A.append(k)
N = len(A)

H = collections.defaultdict(set)
D = []
for i, a in enumerate(A):
	divs = get_divisors(a)
	D.append(divs)
	for d, c in divs:
		for j in range(1, c+1):
			k = pow(d, j)
			H[k].add(i)

del_list = set()
Ns = range(N)
for i, divs in enumerate(D):
	if i in del_list: continue
	s = set(Ns)
	for d, c in divs:
		for j in range(1, c+1):
			k = pow(d, j)
			s &= H[k]
	del_list |= s - set([i])
print(N-len(del_list))

Submission status: Wrong Answer

Solution code:
from bisect import bisect, bisect_left
N = int(input())
A = sorted(list(map(int, input().split())))
A_ = sorted(list(set(A)))
L = len(A_)
ans = 0
i = 0
while i < L:
  j = 0
  isOK = True
  while j < L and A_[j]*2 <= A_[i] and isOK:
    if A_[i]%A_[j] == 0:
      isOK = False
      break
    j += 1
  if bisect(A, A[i])-bisect_left(A, A[i]) == 1 and isOK:
    ans += 1
  i += 1
print(ans)

Submission status: Wrong Answer

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

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)
    return divisors


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

if 1 in A:
    print(A.count(1))
    exit()

D = {}

for i in range(1, A[-1]+1):
    D[i] = 0

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


ret = 0
for a in A:
    if D[a] != 1: continue
    f = make_divisors(a)
    flag = True
    if len(f) == 2 and D[f[1]] == 1:
        ret += 1
    else:
        flag = True
        for f2 in f[2:]:
            if D[f2] == 0: continue
            else: flag = False
        if flag: ret += 1


print(ret)

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    A.sort(reverse=True)
    A = np.array(A, dtype=np.int64)

    #print(A)
    count = 0
    for i, a in enumerate(A):
        #print(a % A[i+1:] != 0)
        if all(a % A[i+1:] != 0):
            count += 1
    if len(A) > 2 and A[-1] == A[-2]:
        count -= 1

    print(count)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
Ain=list(map(int,input().split())) 
ans=0
A=set(Ain)
A=list(A)
A.sort()
A2=list(t for t in A)

for i in range(1,len(A)):
    for div in A2:
        if div<A[i] and A[i]%div==0:
            A2.remove(A[i])
            break
        elif div==A[i]:
            ans+=1

if Ain.count(A[0])==1:
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import deque
list=[0 for i in range(10**6+1)]
for i in A:
  list[i]+=1

for i in range(len(list)):
  if list[i]!=0:
    for j in range(2*i,10**6,i):
      list[j]=0
ans=0
for i in range(len(list)):
  if list[i]==1:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# 一番小さい数はかならず条件を満たす(同じ数があるときはだめ)
# i!=j の任意のjで割り切れない → N-i!=jで一つでも割り切れるものがある数

'''
エラトステネスの篩の数列版じゃない？
1  2  3  4  5  6  7  8  9  10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

小さい方から倍数を取ってけば良いかな
'''


N = read_a_int()
A = read_ints()
if N == 1:
    print(0)
    exit()
cnt = Counter(A)
A = []
for k, v in cnt.items():
    if v == 1:
        A.append(k)

A.sort()
AMAX = 10**6 + 10
cnt = 0  # なにでも割り切れないときのcnt
is_first = [True] * (AMAX + 1)
for a in A:
    if is_first[a]:
        cnt += 1
        for j in range(a, AMAX + 1, a):
            # print(j)
            is_first[j] = False
print(cnt)

Submission status: Wrong Answer

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

n=int(input())
a=sorted(list(map(int,input().split())), reverse=True)
cnt=0
for i in a:
    l=make_divisors(i)
    if len((set(a)-{i}))!=0 and len((set(a)-{i}) & set(l))==0:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
if n==1:
  pass
elif a[0] != a[1]:
  ans+=1
for i in range(1,n):
  for j in range(i):
    if a[i]%a[j]==0:
      break
    elif a[j]*2>a[i] or j==i-1:
      ans+=1
      break
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = set()
M = A[-1]
c = 0
X = collections.Counter(A)
for i, j in X.items():
    if j != 1:
        B.add(i)
for a in A:
    Z = True
    for b in B:
        if a % b == 0:
            Z = False
            break
    if Z:
        c += 1
        if a <= 10 ** 3:
            B.add(a)
print(c)

Submission status: Wrong Answer

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

l.sort()

i = 0
while i < len(l):
    if l.count(l[i]) != 1:
        k = l[i]
        while k in l:
            l.remove(k)
        i += 1
    else:
        l = l[:i+1] + [j for j in l[i+1:] if j % l[i] != 0]
        i += 1

print(len(l))

Submission status: Wrong Answer

Solution code:
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


import sys
# x,y = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
cnt = 0
kiti = []

for ix,i in enumerate(a):
    flag = False
    tyouhuku = False
    if ix < len(a)-1:
        if i == a[ix+1]:
            tyouhuku = True
            kiti.append(i)
    yousos = factorization(i)
    for youso in yousos:
        for beki in range(youso[1]+1):
            val = pow(youso[0],beki)
            if val in kiti:
                flag = True
                break
        else:
            continue
        break
    if flag == False:
        cnt += 1
    if tyouhuku == False:
        kiti.append(i)

print(cnt)

Submission status: Wrong Answer

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

import math
import bisect

ans = [True] * N
A.sort()

A_cnt = {}
for i, Ai in enumerate(A):
    A_cnt.setdefault(str(Ai), 0)
    A_cnt[str(Ai)] += 1

for i, Ai in enumerate(A):
    if A_cnt[str(Ai)] > 1: ans[i] = False

A_set = set(A)
for i, Ai in enumerate(A):
    for p in range(1, int(math.sqrt(Ai)) + 1):
        if Ai % p == 0:
            if p in A_set:
                ans[i] = False
                break
            if p == 1: continue
            elif (Ai // p) in A_set:
                ans[i] = False
                break

ans = ans.count(True)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

upper_bound = 200001

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

dup = [key for key, value in Counter(nums).items() if value >= 2]

out = set()
for d in dup:
	if d not in out:
		out = out | set([d * i for i in range(1, 2 + upper_bound // d)])

nums = sorted([x for x in nums if x not in dup])

cnt = 0
for x in nums:
	if x not in out:
		cnt += 1
		out = out | set([x * i for i in range(1, 2 + upper_bound // x)])

print(cnt)

Submission status: Wrong Answer

Solution code:
n, *A = map(int, open(0).read().split())
c = 0
A = sorted(list(set(A)))[::-1]
if len(A)==1:exit(print(0))
for i, a in enumerate(A):
    c += all(a%j for j in A[i+1:])
print(c)

Submission status: Wrong Answer

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

import math

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


def is_prime(n):
  for i in range(2, math.ceil(math.sqrt(n)+1)):
    if n%i==0:
      return False
  return True

sa = set(a)

ans=0

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

print(ans)

Submission status: Wrong Answer

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

cnt = N
for i in range(N//2):
    for j in range(i+1, N):
        if i != j and A[i] % A[j] == 0:
            cnt -= 1
            if A[j] % A[i] == 0:
                cnt -= 1
            break
        if i != j and A[j] % A[i] == 0:
            cnt -= 1
            break

print(cnt)

Submission status: Wrong Answer

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

ct = Counter(As)
L = 10**6+1
flags = [True] * L
ans = 0
for k in sorted(ct.keys()):
    c = ct[k]
    if c > 1 or not flags[k]:
        continue
    ans += 1
    flags[2*k::k] = [False] * ((L-k-1) // k)
print(ans)

Submission status: Wrong Answer

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

    A.sort()

    count = 0
    for idx,i in enumerate(A):
        if i == A[idx -1]:
            continue
        if idx != N-1 and i == A[idx +1]:
            B.discard(i)

        deleted =set()
        for j in B:
            if i!=j and j % i ==0:
                deleted.add(j)
        B.difference_update(deleted)

        if i in B:
            count +=1
        



    print(count)

resolve()

Submission status: Wrong Answer

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

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

cnt = 0
for i in A:
    p = make_divisors(i)[1:]
    b = len(p)
    p.extend(A)
    p = set(p)
    if len(p) == b + len(A) -1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
K = {}
A.sort()
before = -1
for i in A:
    c = 2
    if before == i:
        K[i] = 1
    while(True):
        if i*c > 2*(10**5):
            break
        K[i*c] = 1
        c += 1
    before = i
t = 0
for i in A:
    if i in K:
        t += 1
print(N-t)

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

counter = 0
for num in numlist:
    Flag = True
    for i in numlist:
        if i == num:
            continue
        if i%num != 0:
            Flag = False
            break
    if Flag:
        counter += 1

if len(set(numlist)) == 1:
    print(0)
else:
    print(counter)

Submission status: Wrong Answer

Solution code:
def prime(n):
  i = 2
  while i ** 2 <= n:
    if n % i == 0:
      return False
    i += 1
    
  return True


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

alist.sort()

count = 0

for i in range(0, N):
  
  a = alist[i]
  flag = 0
  
  if i != N - 1:
    if alist[i + 1] == a:
      continue
      
  if i != 0:
    if alist[i - 1] == a:
      continue
      
  if prime(a):
    count += 1
    continue

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

AListsort = sorted(AList)

ResultList = []

tmp = 0

if N > 1:
    if AListsort[0] != AListsort[1]:
        ResultList.append(AListsort[0])
else:
    ResultList.append(AListsort[0])


for p in range(1, N - 1):
    tmp = 0
    if AListsort[p - 1] != AListsort[p] and AListsort[p] != AListsort[p + 1]:
        for q in ResultList:
            if AListsort[p] % q == 0:
                tmp = 1
                break
        if tmp == 0:
            ResultList.append(AListsort[p])
    else:
        continue

tmp = 0
if N > 1:
    if AListsort[N - 2] != AListsort[N - 1]:
        for q in ResultList:
            if AListsort[N - 1] % q == 0:
                tmp = 1
                break
        if tmp == 0:
            ResultList.append(AListsort[N - 1])

print(len(ResultList))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
tmp = sorted(a)
a.sort()
itr = 0
while True:
    if len(tmp) == itr:
        break
    tmp = tmp[: itr + 1] + [j for j in tmp[itr+1:] if j % a[itr] != 0]
    itr += 1

if a.count(a[0]) == n:
    print(0)
else:
    print(len(tmp))

Submission status: Wrong Answer

Solution code:
'''
Author : Shubhanshu Jain;
'''

import math
import random;
from collections import defaultdict 
mod =1000000007
r1 = lambda : int(input());
rm = lambda : map(int,input().split());
rms = lambda : map(str,input().split());
rls = lambda : list(rm())

def solve():
    n = r1();
    ls = rls();
    ans = 0;
    ls.sort();
    k = -1;
    for i in range(n):
        flag = True;
        for j in range(i-1,-1,-1):
            if(ls[i]%ls[j]==0):
                flag = False;
        if flag :
            ans+=1;
            
                
            
    print(ans)
            
        





def def_value(): 
	return "nan"
	
solve();

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
arr = []
du = set()
t = 0

for i in range(n):
    if a[i] == t:
        du.add(a[i])
        break
    for tmp in arr:
        if a[i] % tmp == 0:
            break
    else:
        arr.append(a[i])
    t = a[i]

print(len(arr) - len(du))

Submission status: Wrong Answer

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

maxer = max(a)
for i in range(1, maxer + 1):
    m[i] = 1
    d[i] = 1

for i in a:
    if m[i] != 0 and d[i] != 0:
        d[i] = 0
        k = 2
        while True: 
            t = i * k
            if t <= maxer:
                m[t] = 0
                k += 1
            else:
                break

res = 0
for i in a:
    if m[i] == 1:
        res += 1

print(res)