Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

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

if n>1:
    if li[0]==li[1]:
        ans -= 1

import math
import bisect
while len(li)>0:
    ba = li.pop(-1)
    s_ba = math.ceil(math.sqrt(ba))
    index = bisect.bisect_left(li, s_ba)
    tmp_li = li[:index+1]
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter 

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())

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

    ans = 0

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()
flag = [True for i in range(10**6+1)]
a.sort()
for i in range(n):
    if flag[a[i]] == False:
        continue
    if i >= 1:
        if a[i] == a[i-1]:
            continue
    for j in range(2,(10**6)//a[i]+1):
        flag[a[i]*j] = False
ans = 0
for i in range(n):
    if flag[a[i]]:
        if i >= 1:
            if a[i] == a[i-1]:
                continue
        if i == 0:
            if a[i] == a[i+1]:
                continue
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(0)
    exit()

Ss = sorted(As)
primes = set()
cnt = 0
d = defaultdict(int)
for s in Ss:
    d[s] += 1
# print(Ss)
for s in Ss:
    if d[s] > 1:
        continue
    flg = False
    for p in primes:
        if s % p == 0: 
            flg = True
            break
    if not flg:
        if s <= 1000:
            primes.add(s)
        cnt += 1
print(cnt)

"""
10
33 18 45 28 8 19 57 86 2 4
"""

Submission status: Wrong Answer

Solution code:
def sieve(n, A):
    data = A
    prime = []
    while True:
        if len(data) == 0:
            return prime
        p = data[0]
        prime.append(p)
        data = [e for e in data if e % p != 0]


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

if 1 in A:
    print(0)
    exit()

if all(a == A[0] for a in A):
    print(0)
    exit()

n = max(A)
A.sort()
print(len(sieve(n, A)))

Submission status: Wrong Answer

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

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

Ali.sort()

if len(set(Ali))==1:
    print(0)
    sys.exit()


for index_i,i in enumerate(Ali):
    for j in Ali[index_i+1:]:
        if j%i == 0:
            Ali.remove(j)

print(len(Ali))

Submission status: Wrong Answer

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

cnt=0

for i in range(n):
  for j in range(n):
    if i!=j:
      x=a[i]/a[j]
      if x==int(x):
        break
      if j==(n-1):
        cnt+=1
  

print(cnt)

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 heapq

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

heapq.heapify(A)
if len(set(A)) == 1:
    print(0)
    exit()
count = 0
divisor_list = []
for _ in range(N):
    ans = True
    item = heapq.heappop(A)
    for j in divisor_list:
        if item % j == 0:
            ans = False
            break
    if ans == True:
        count += 1
    divisor_list.append(item)

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = set(i for i in range(n))
ans = [0]*n
warizai_index = set()

for i in range(n):
    for wari in warizai_index:
        if a[i]%a[wari] == 0 and i != wari:
            ans[i] = 1
            b.remove(i)
            break
    if ans[i] == 1:
        continue
    
    for j in b:
        if i == j:
            continue
        if a[i]%a[j] == 0:
            ans[i] = 1
            b.remove(i)
            warizai_index.add(j)
            break

print(ans.count(0))

Submission status: Wrong Answer

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

A.sort()

if min(A) == max(A):
    print(0)
    exit()
f = [True] * N

for i,a in enumerate(A):
    if f[i]:
        for j in range(i+1,N):
            f[j] &= not (A[j] % a == 0)

print(sum(f))

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])

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:
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()
for a,v in adic.items():
  if v==1:
    aset.add(a)
  
if not aset:
  print(0)
  sys.exit(0)
  
tlist=[False]*(max(aset)+1)
for a in aset:
  tlist[a]=True
#print(tlist)

for i in range(2,len(tlist)//2+1):
  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:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
na = []
for i in range(n):
    if i != n-1 and a[i] == a[i+1]: continue
    if i != 0 and a[i] == a[i-1]: continue
    na.append(a[i])
# print(na)
flag = [(0,0)]*(10**6+1)


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

ans = 0
l = len(na)
for i in range(l): flag[na[i]] = (1,i)
for i in range(l):
    for j in divisor(na[i]):
        if flag[j][0] and i != flag[j][1]: break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    A.sort()
    ans = []
    if N == 1:
        ans.append(A[0])
    elif A[0] != A[1]:
        ans.append(A[0])

    for i in range(N-1):
        for a in A[:i+1]:
            if A[i+1] % a == 0:
                break
        else:
            ans.append(A[i+1])

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [ int(i) for i in input().strip().split(' ')]
B = [0] * N

for i in range(N):
    if B[i] != 0:
        continue
    for j in range(i+1, N):
        if A[i] == A[j]:
            B[i] = 1
            B[j] = 1
            break
        elif A[i] % A[j] == 0:
            B[i] = 1
            break
        elif A[j] % A[i] == 0:
            B[j] = 1
            
print(N - sum(B))

Submission status: Wrong Answer

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

result = 0
n_list.sort(reverse=True)

print(n_list)

#比較していく（最後の一つだけ比較無しで条件を満たすとされる）
for i in range(n):
    d_flag = 0
    for j in range(i+1, n):
        if n_list[i] % n_list[j] == 0:
            d_flag = 1
            break
    if d_flag == 0:
        result += 1

#最後の一つだけ一つ手前と一致しないかどうかを確認
if n_list[n-1] == n_list[n-2]:
    result -= 1

print(result)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import gcd
import sys
MX = 10**6
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    S = set(A)
    C = Counter(A)
    ans = 0
    for a in A:
        if C[a] >= 2: continue
        for d in dv(a):
            if d in S:
                break
        else:
            ans += 1
    print(ans)

def dv(x):
    res = set()
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            res.add(i)
            res.add(x // i)
    return res

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import Counter

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()

div = set(A)
cnt = Counter(A)
ans = 0


def divisors(n):
    if 1 in div or cnt[n] >= 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            if i in div:
                return False
            if i != n // i:
                if n//i in div:
                    return False
    return True


for a in A:
    if divisors(a):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n=int(input())
A=Counter(sorted(list(map(int,input().split()))))
number=[True for i in range(10**6+1)]

cnt=0
for v,m in A.items():
    if m!=1:
        for i in range(v,10**6,v):
            number[i]=False
    else:
        if number[v]==True:
            cnt +=1
            for i in range(v,10**6,v):
                number[i]=False
print(cnt)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

ans = 0
res = deepcopy(A)

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    MAX = (10 ** 6) + 5
    prime = [True] * MAX
    ans = 0
    for i in range(1, N):
        if A[i] == A[i - 1]:
            prime[A[i]] = False
    for i in range(N):
        now = A[i]
        if prime[now]:
            ans += 1
            for j in range(now * 2, MAX, now):
                prime[j] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def check(s, a, next):
    if a==next:
        return False
    if a in s:
        return False
    x = 2
    while a>=x*x:
        if a%x==0:
            if x in s:
                return False
            if a//x in s:
                return False
        x += 1
    return True

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

s = set()
res = 0
for i in range(n):
    a = al[i]
    next = -1
    if i<n-1:
        next = al[i+1]
    if check(s,a,next):
        res += 1
    s.add(a)
print(res)

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 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:
M = int(input())
A=list(map(int,input().split()))
A=list(set(A))
A.sort()
k=0
if len(A)==1:
    print(0)
else:
    while True:
        if k==len(A):
            break
        for i in range(k,len(A)):
            delite=[]
            judge=0
            for j in range(i+1,len(A)):
                if A[j]%A[i]==0:
                    delite.append(j)
                    judge=1
            if judge==1:
                delite.reverse()
                for d in delite:
                    A.pop(d)
        k+=1
                
            
    print(len(A))

Submission status: Wrong Answer

Solution code:
def resolve():
    nn = int(input())
    a = {}
    exists = set()
    for i,aa in enumerate(map(int, input().split())):
        if aa not in a:
            a[aa] = i
        else:
            exists.add(aa)
    tt = 0
    for n in a.keys():
        for div in range(1, int(n**0.5)+1):
            if n % div == 0:
                dd = n // div
                if div in a or (dd != n and dd in a):
                    break
        else:
            tt += 1

    print(tt - len(exists))

if __name__ == "__main__":
    resolve()

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]
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A.sort()


if (N == 1):
    print(0)
    exit(0)

if (1 in A):
    print(1)
    exit(0)

count = 0

for i in range(0, N):
    flag = True
    a = A[i]
    for j in range(0, min(i + 2, N)):
        if (i != j and a % A[j] == 0):
            flag = False
            break

    if (flag):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
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

fact = set()

A.sort()
ans = 0
for i in A:
    div = set(make_divisors(i))
    if len(fact & div) != 0:
        fact.add(i)
        
    else:
        ans += 1
        fact.add(i)
        
print(ans)

Submission status: Wrong Answer

Solution code:

from collections import Counter

def prime_decomposition(n):
    i = 2
    tank = []
    while i * i <= n:
        while n%i == 0:
            n /= i
            tank.append(i)
        i += 1
    if n > 1:
        tank.append(int(n))
    return tank

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

n = int(input())
A = list(map(int,input().split()))
A = sorted(A)
c = Counter(A)
lst = []
for k,v in c.items():
    if v==1:
        lst.append(k)

if len(lst)==0:
    print(0)
    
else:
    cnt = 0
    prime = set()
    for x in lst:
        tmp = divisor(x)
        if len(prime & set(tmp))==0:
            cnt += 1
            prime = prime.union(set([x]))
    print(cnt)

Submission status: Wrong Answer

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

for k in range(1, N):
    if k<N-1:
        if A[k] == A[k+1]:
            continue
    for j in range(k):
        if A[k]%A[j] ==0:
            break
    else:
        count +=1
        #print(A[k])
if N>1:
    if A[0]%A[1] >0:
        count+=1
    

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = 0
B = []
n = 0
n_cnt = 0
for i in range(N):
    if A[i] == n:
        n_cnt = 1
        continue
    else:
        cnt -= n_cnt
        n_cnt = 0
        n = A[i]
        state = 1
        for b in B:
            if n % b == 0:
                state = 0
                break
        if state == 1:
            cnt += 1
            B.append(n)
        else:
            continue
cnt -= n_cnt
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n = int(input())
a = list(map(int, input().split()))
a.sort()
print(a)
for i in range(n):
    wa = a[i]
    if a[i] == -1:
        continue
    if a[i] in a[i+1:]:
        a[i] = -1

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

Submission status: Wrong Answer

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

# 全部の数が同じ場合
check = a[0]
same_flag = True
for i in range(1, n):
    if a[i] != check:
        same_flag = False
        break

if same_flag:
    print(0)
    exit(0)

a_sorted = sorted(a, reverse=True)
cnt = 1
for i in range(n-1):
    cnt_flag = True
    for j in range(i+1,n):
        #print(F'{a_sorted[i]} {a_sorted[j]}')
        if a_sorted[i] % a_sorted[j] == 0:
            cnt_flag = False
            break
    if cnt_flag:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = LI()
    A = LI()

    y = [0] * (10**6 + 1)
    for i in A:
        y[i] += 1

    ans = 0
    for i in A:
        for j in range(1,int(math.sqrt(i)) + 1):
            if j == 1:
                if y[1]: break
                if y[i] > 1 : break
            else:
                if j == i and y[i] <= 1: continue
                if i % j == 0 and (y[j] or y[i//j]):
                    break
        else:
            ans += 1

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

Submission status: Wrong Answer

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

ans = 0
for i in range(N):
  is_divide = False
  for j in range(i):
    if A[i] % A[j] == 0:
      is_divide = True
      break
  if is_divide == False:
    ans += 1

if A[0] in A[1:]:
  ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    ma=max(A)
    
    l=[0]*(ma+1)
    A.sort()
    count=0
    pa=0
    f=0
    for a in A:
        if pa==a:
            if f:
                count-=1
                f=0
            continue
        if not l[a]:
            count+=1
            f=1
            for i in range(a,ma+1,a):
                l[i]=1
        pa=a
    print(count)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

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

a.sort(reverse=True)
cnt = n

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
f = 0
c = 0
for i in a:
    for j in a:
        if i == j:
            if a.index(j) == n - 1:
                c += 1
            continue
        if i % j == 0:
            break
        if a.index(j) == n - 1:
            c += 1
print(c)

Submission status: Wrong Answer

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

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


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

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:
    f = make_divisors(a)
    flag = True
    if D[a] != 1: continue
    elif len(f) == 0: ret += 1
    else:
        flag = True
        for f2 in f:
            if D[f2] == 0: continue
            else: flag = False
        if flag: ret += 1


print(ret)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
counter = Counter(A)
s = sorted(set(A))
if len(A) == 1:
    print(1)
else:
    lst = []
    ans = 0
    for i in range(len(s)):
        m = s[i]**0.5 + 1
        flg = True
        for p in lst:
            if s[i]%p == 0:
                flg = False
                break
            elif m < p:
                break
        if flg:
            lst.append(s[i])
            if counter[s[i]] == 1:
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline


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

    A.sort()
    c = Counter(A)
    keys = list(c.keys())
    if len(keys) == 1:
        ans = 0
    else:
        ans = 0
        for i, (k, v) in enumerate(c.items()):
            ans += v * all(k % key != 0 for key in keys[:i])

    print(ans)


if __name__ == "__main__":
    main()

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)
for i in A:
    ANS[i-1] = 1
if A[0] == 1:
    print(0)
    exit()
for i in range(n-1):
    if ANS[A[i]-1] == 0:
        pass
    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)
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 = [int(i) for i in input().split()]
ans = 0
for i in a:
    for j in a:
        if i == j:
            continue
        if i % j == 0:
            break
        elif j == a[-1]:
            ans += 1
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
from numba import jit
x=dict()
ans=0
for i in range(N):
    val=A[i]
    if val in x:
        x[val]+=1
    else:
        x[val]=1
L=[]
for idx in x:
    if x[idx]==1:
        L.append(idx)
if len(L)==0:
    print(0)
    exit()
L.sort()
#print(L)
R=[]
for i in range(len(L)):
    val=L[i]
    flag=False
    for j in range(len(R)):
        if val%R[j]==0:
            flag=True
            break
    if flag:
        continue
    ans+=1
    R.append(val)

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=list(map(int,input().split()))
s=0
k=0
L=sorted(L)
for i in range(N):
  c=L[i]
  for j in range(i):
    if c%L[j]==0:
      s+=1
  if s==0:
    k+=1
  s=0
print(k)

Submission status: Wrong Answer

Solution code:
import sys
import math as mt
input=sys.stdin.buffer.readline  
#t=int(input())
mod=10**9+7
t=1
for __ in range(t):
    
    #x,n=map(int,input().split())
    l=[0]*(10**6+1)
    n=int(input())
    #a=[[0 for j in range(m)] for i in range(n)]
    a=list(map(int,input().split()))
    a.sort()
    ans=0
    for i in range(n):
        cnt=0
        for j in range(i):
            if a[i]%a[j]!=0:
                cnt+=1
            else:
                break
        if cnt==i:
            ans+=1
    cnt=0
    for i in range(1,n):
        if a[0]%a[j]!=0:
            cnt+=1
        else:
            break
    if cnt!=n-1:
        ans-=1
        
        
    print(ans)

Submission status: Wrong Answer

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

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



N=one_int()

As = many_int()

same = -1 if len(set(As))==1 else 0

same

As = sorted(As)

count=0
for i, a in enumerate(As):
    
    flg=True
    for b in As[:i]:
        if a%b==0:
            flg=False
    if flg:
        count+=1

print(count + same)

Submission status: Wrong Answer

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

    from collections import Counter

    n = int(readline())
    a = list(map(int, readline().split()))
    check = Counter(a).items()
    memo = [True] * (2 * 10 ** 6 + 1)
    a = []
    for k, v in check:
        if v == 1:
            a.append(k)
        else:
            memo[k] = False
    ans = 0
    a.sort()
    for aa in a:
        if memo[aa]:
            ans += 1
            for i in range(1, 10 ** 6 + 1):
                if 10 ** 6 + 1 < i * aa:
                    break
                memo[i * aa] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:


import collections

def factorization(n):
    pf_cnt = {1:1}
    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
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt



def main():
    n = int(input())
    al = list(map(int, input().split()))
    al_not_multi = []
    cnt = collections.Counter(al)
    for i,v in cnt.items():
        if v == 1:
            al_not_multi.append(i)
    al_not_multi.sort()

    al_n = al_not_multi[:]
    ans = 0
    while al_n:
        new_al_n = []
        start = al_n[0]
        for a in al_n[1:]:
            if a%start!=0:
                new_al_n.append(a)
        al_n = new_al_n[:]
        ans += 1
    print(ans)




if __name__ == "__main__":
    main()