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:
# coding: utf-8


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

    return sorted(ans)


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

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

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

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

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

    ans = 0
    for i in range(N):
        is_ans = True
        if int(A[i]**0.5) + 1 < i:
            # print("way-1")
            ys = yakusu(A[i])
            for j in range(len(ys)-1):
                b = ys[j]
                if is_in_A_flag[b] > 0:
                    is_ans = False
                    break

            if is_ans:
                if is_in_A_flag[ys[-1]] > 1:
                    is_ans = False

            if is_ans:
                ans += 1
        else:
            # print("way-2")
            for j in range(i):
                if A[i] % A[j] == 0:
                    is_ans = False
                    break

            if is_ans:
                ans += 1

    return ans


print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split())) 
p = 0
q = 0
if (1 <= N <= 2*10**5) and (1 <= len(A) <= 10**6):
    
    for i in range(N):
        for j in range(N):
            if A[i] % A[j] != 0:
                p += 1
                if p == N:
                    q += 1
                    p = 0
                    break
            elif  A[i] % A[j] != 0:
                p = 0
                break

    print(q)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
input()
_A = list(set([int(i) for i in input().split()]))
A = sorted(_A,reverse=True)
N = len(A)
if N == 1:
  print(0)
else:
  c = 1
  for i in range(N-1):
    b = A[i]
    for y in range(i+1,N):
      if b % A[y] == 0:
        break
    else:
      c += 1
  else:
    print(c)

Submission status: Wrong Answer

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

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

heapq.heapify(A)

ans = []
while A:
    place = []
    d = heapq.heappop(A)
    ans.append(d)
    while A:
        tmp = heapq.heappop(A)
        if tmp % d != 0:
            place.append(tmp)
    else:
        for p in place:
            heapq.heappush(A, p)
print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
res = 0
for i in range(N):
    if i + 1 < N:
        if A[i] == A[i+1]:
            continue
    elif i - 1 >= 0:
        if A[i] == A[i-1]:
            continue 
    a = A[i]
    sra = int(a ** 0.5) + 1
    for j in range(0, i):
        b = A[j]
        if a % b == 0:
            break
        if b > sra:
            res += 1
            break
    else:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    if n == 1:
        print(1)
    else:
        A.sort()
        if A[0] == 1:
            if A[1] == 1:
                print(0)
            else:
                print(1)
        elif len(list(set(A))) == 1:
            print(0)
        else:
            # cnt = 0
            # for i in range(n):
            #     flag = False
            #     for j in range(n-i-1):
            #         if A[n-1-i] % A[j] == 0:
            #             flag = True
            #             break
            #     if flag == False:
            #         cnt += 1
            # print(cnt)
            for i in range(n):
                lentemp = len(A)
                for j in range(lentemp-1-i):
                    if A[lentemp-1-j] % A[i] == 0:
                        del A[lentemp-1-j]

                if i+2 >= len(A):
                    break
            print(len(A))

resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if 1 in A:
    print(1)
    exit()
if max(A) == min(A):
    print(0)
    exit()

count = N
A = sorted(A, reverse=True)
for i in range(N-1):
    now = A[i]
    for j in range(N-1, i, -1):
        if now % A[j] == 0:
            count -= 1
            break

print(count)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n = inp()
x = ip()
if len(set(x)) == 1:
    print(0)
else:
    if len(x) == 1:
        print(1)
    else:
        x.sort(reverse= True)
        ct = 1
        for i in reversed(range(n-1)):
            flag = 1
            for j in range(i+1,n):
                if x[i]%x[j] == 0:
                    flag = 0
                    break
            if flag:
                ct += 1
        print(ct)

Submission status: Wrong Answer

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

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

if N >= 2 and A[0] == A[1]:
    res -= 1

print(res)

Submission status: Wrong Answer

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


a=sorted(a,reverse=True)

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

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int,input().split()))
li.sort()
if li[0] == 1:
    print(1)
    exit()
if len(set(li)) == 1:
    print(0)
    exit()
for i in range(10^5):
    li.append(1122887)
count = 0
for i in range(n):
    if li[i] == 1122887:
        break
    j = i + 1
    while True:
        if li[j] == 1122887:
            break
        if li[j] % li[i] == 0:
            li.remove(li[j])
            count += 1
        else:
            j += 1
print(n - count)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
from collections import defaultdict
d = defaultdict(int)
ans = 0
for i in range(N):
    d[a[i]] += 1
for i in range(1,1001):
    if d[i] == 1:
        ans += 1
        for j in range(2,2+10**6//i):
            d[j*i] = 0
    elif d[i] >= 2:
        for j in range(2,1+10**6//i):
            d[j*i] = 0
for i in range(1001,1000000):
    if d[i] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def using_sqrt(k):  
    factor = 0
        
    # 2以外の偶数は素数ではないので無視する
    if k % 2 == 0 and k != 2:
        return False
        
    # 繰り返しの上限を対象の平方根にする
    for divisor in range(2, math.floor(math.sqrt(k))+1):
        if k % divisor == 0:
            factor += 1
                
    if factor == 0:
        return True
    else:
        return False
            

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
so = []
for i in range(n):
  if using_sqrt(a[i]):
    temp = a[i]
    so.append(temp)
    a[i]=0
    ans += 1
    if i != n-1:
      if temp == a[i+1]:
        ans -= 1
        if i == n-2:
          break
        
        
for i in range(len(so)):
  a = list(filter(lambda x: x % so[i] != 0, a))

while len(a) >= 1:
  ans += 1
  temp=a.pop(0)
  if len(a) >= 1:
    if a[0] == temp:
      ans -= 1
    a = list(filter(lambda x: x % temp != 0, a))
  
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
i=0
chohuku=len([x for x in set(A) if A.count(x) > 1])
B=list(set(A))
B.reverse()
n=len(B)

for _ in range(n):
    x=B.pop(0)
    if not any(x%b==0 for b in B):
        i+=1

print(i-chohuku)

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
    q = a[i] ** 0.5
    for tmp in arr:
        if a[i] % tmp == 0:
            break
        if tmp > q:
            arr.append(a[i])
            break
    else:
        arr.append(a[i])
    t = a[i]

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = list(map(int,input().split()))
a.sort()
d = deque(a)
e = deque(a)
print(d)
for i in range(len(e)):
  for j in range(i+1,len(e)):
    if e[j] % e[i] == 0 and e[j] in d:
      d.remove(e[j])
      #print(d)
print(len(d))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
readline = sys.stdin.readline
a = [int(i) for i in readline().split()]
#a = list(map(int, input().split()))

a = list(set(a))
n = len(a)
a.sort()

ans = 0

for i in range(n):
    
    x = a[i]

    l = -1; r = n # 二分探索時は探索範囲は取り得る値+-1しておく

    while l+1 < r:
        c = (l+r)//2
        if a[c] <= x//2:
            l = c
        else:
            r = c
    
    if n != c+1:
        for j in range(c+1):
            if i != j and x%a[j] == 0:
                break
        else:
            ans += 1

print(ans)

Submission status: Wrong Answer

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


for i in range(N):
  for j in range(N):
    if i == j:
      break
    if num_list[i] % num_list[j]==0:
      count = count + 1
      break

print(N-count)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = list(map(int, input().split()))[0]
A = np.array(list(((map(int, input().split())))))
idx = np.argsort(A)
A = np.sort(A)
Z = np.zeros(N)

def get_result():
    result = 0
    for i in range(N):
        flag = True
        if i < N - 1 and A[i] == A[i + 1]:
            flag = False
        for j in range(i):
            if Z[j] != 0:
                continue
            d, m = divmod(A[i], A[j])
            if m == 0:
                flag = False
                Z[i] = 1
                break
            if d < 2:
                break
        if flag:
            result += 1
    return result

print(get_result())

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
A=list(sorted(set(list(map(int,input().split())))))
ans=0
N=len(A)
for i in range(N):
    B=A.copy()
    t=B[i]
    j=max(bisect.bisect_left(B,t*0.5),i)
#     print(t,j)
    del B[j:]
    arr=[]
#     print(B)
    if all(list(map(lambda x: t%x!=0, B))):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#D
import collections
n=int(input())
a_list=list(map(int,input().split()))
a_list.sort()
b_list=collections.Counter(a_list)
b_list=b_list.keys()
j_list=[a_list[0]]
if len(b_list)==1:
    ans=0
else:
    ans=1
    for i in a_list:
        for j in j_list:
            if i%j ==0:
                break
        else:
            ans+=1
            j_list.append(i)
            #print(i)
print(ans)

Submission status: Wrong Answer

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

N=int(input())
A=list(map(int,input().split()))
A.sort()
count=0
key=0
for i in range(1,len(A)):
    if key==0 and A[i-1]==A[i]:
        count-=1
        key=1
    if key==1 and A[i-1]!=A[i]:
        key=0
A=list(set(A))
A.sort(reverse=True)
while len(A)>0:
    x=A.pop()
    A=[i for i in A if i%x != 0]
    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = (list(map(int, input().split(' '))))
D = [0]*(pow(10,6)+1)
ans = 0
for i in set(A):
    D[i] += 1
for i in A:
    flg = True
    if D[i] > 1:
        continue
    for j in range(1,int(pow(i,0.5))+2):
        if not i%j:
            if D[j] and i != j:
                flg = False
                break
            if j != i//j and D[i//j] and i//j != i:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
MAX = max(A) #Aの中の最大値
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  Flag = True
  temp = A[j]
  if Adic[temp] >= 2:
    if temp in Aset:
      Aset.remove(temp)
    continue
  fmax = MAX//temp
  #print(fmax,temp)
  for i in range(2,fmax+1): #fmaxまで見る
    now = temp*i
    if now in Aset:
      Aset.remove(now)
#print(Aset)
print(len(Aset))

Submission status: Wrong Answer

Solution code:
import sys 

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
A.sort()
# print(A)

ans = 0 
invalid = set()
for i in range(N):
    if A[i] in invalid:
        continue

    for j in range(i+1, N):
        if A[j] in invalid:
            continue
        
        # print(A[i], A[j])
        if A[j] % A[i] == 0:
            invalid.add(A[j])
        if A[i] == A[j]:
            # print("break")
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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]

def main():
    n = int(input())
    #x,n = map( int, input().split())
    a = list(map( int, input().split()))
    a.sort()
    ans = 1
    for i in range(1,len(a)):
        l = a[:i]
        if len(list(set(l)&set(make_divisors(a[i]))))==0:
            ans+=1
    print(ans)

        
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans_list=[]
for i in range(N):
  for j in range(i+1,N):
    if A[i]/A[j]-int(A[i]/A[j])==0:
      ans_list.append(i)
    if A[j]/A[i]-int(A[j]/A[i])==0:
      ans_list.append(j)  
      break
      

print(N-len(set(ans_list)))
#print(gcd_list)

Submission status: Wrong Answer

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

anss = 0
for i in range(n):
    keep = 0
    for j in range(i + 1, n):
        if aa[j] % aa[i] == 0:
            anss += 1
print(anss)

Submission status: Wrong Answer

Solution code:
def prime_factorize_k(n):
    p = []
    while n % 2 == 0:
        if 2 not in p:
            p.append(2)
        n //= 2
    # 偶数はこれからは試さなくてよくなる
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in p:
                p.append(f)
            n //= f
        else:
            f += 2
    if n != 1 and n not in p:
        p.append(n)
    return p


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

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

spl_list = []
cnt = 0
for i in a:
    spl = prime_factorize_k(i)
    same = set(spl_list) & set(spl)
    # print(spl, spl_list, spl, same)
    if len(same) >= 1:
        continue

    if len(spl) == 1:
        spl_list.append(spl[0])

    # print(spl, spl_list)
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 170: D - Not Divisible
https://atcoder.jp/contests/abc170/tasks/abc170_d
"""


prime_cache = {}


def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    for p in range(2, n):
        if n % p == 0:
            return False
    return True


def main():
    global prime_cache
    N = int(input())
    As = list(map(int, input().split()))

    ans = set()
    for i in range(N):
        is_divisible = False
        if As[i] in prime_cache:
            continue
        if As.count(As[i]) == 1 and is_prime(As[i]):
            prime_cache[As[i]] = True
            ans.add(i + 1)
            continue

        for j in range(N):
            if i != j and As[i] % As[j] == 0:
                is_divisible = True
                break
        # print('i({}):{}, j({}):{}'.format(i, As[i], j, As[j]))
        if not is_divisible:
            ans.add(i + 1)

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

counter = 0

A.sort()

if N >= 2:
  if A[0] == [1]:
    counter += 1

i = 0
flag = 0

while i < len(A):
  flag = 0
  for j in range(i):
    if A[i]%A[j] == 0:
      counter += 1
      A.pop(i)
      flag = 1
      break
  if flag == 0:
    i += 1

      
print(N-counter)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    A.sort()
    if A[0] == 1:
        print(1)
        return
    arr = [0] * (A[-1] + 1) # 1-indexed
    for a in A:
        arr[a] += 1

    count = 0
    for i in range(1, A[-1] + 1):
        if arr[i] == 0:
            continue
        elif arr[i] == 1:
            count += 1
        j = 2
        while i * j <= A[-1]:
            arr[i * j] = 0
            j += 1
    print(count)


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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())
A = [int(x) for x in input().split()]

K = 10**6+1
num = [0] * K
for i in range(N):
    num[A[i]]+=1

l = [True] * K

for i in range(2, K):
    if num[i]>0:
        if num[i]>1:
            l[i] = False
        j = 2
        while i*j < K:
            l[i*j] = False
            j += 1

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

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

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=list(map(int,input().split()))
c = collections.Counter(a_list)

ans=0
div=[]
for num in sorted(c.keys()):
  count=c[num]
  if count==1 and is_prime(num):
    ans+=1
    div.append(num)
  elif count==1:
    check=False
    for d in div:
      if num%d==0:
        check=True
    if check:
      div.append(num)
      continue
    ans+=1
  div.append(num)
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(Auniq, Ai):
  for x in Auniq:
    if Ai % x == 0:
      return False
  return True

def main():
  N = int(input())
  A = list(map(int, input().split()))
  Auniq = set(A)
  res = 0
  for i, Ai in enumerate(A):
    Aeq = list(filter(lambda x: x == Ai, Auniq))
    if len(Aeq) == 0:
      Aless = list(filter(lambda x: x < Ai, Auniq))
      if len(Aless) == 0:
        res += 1
      else:
        res += solve(set(Aless), Ai)
  return res

print(main())

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
A.sort()
# print(A)
a = [0]*((10**6)+1)
c = collections.Counter(A)

ans = 0
for i in range(N):
    # print(i)
    if a[A[i]] == 0:
        ans += 1
        k = 1
        while k <= A[-1]//A[i]:
            a[A[i] * k] += 1
            k += 1
            # print("k=",k)
        
    # print(ans)
for i in range(A[-1]+1):
    ans -= c[i] >= 2
    
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
count_a=0
a.sort(reverse=True)
for i in range(n-1):
    count_b=0
    for j in range(n-i-1):
        k=j+i+1
        if a[i]%a[n-k]==0:
            count_b+=1
            break
        else:
            pass
    if count_b==0:
        count_a+=1
if a[n-1]!=a[n-2]:
    count_a+=1
print(count_a)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
ans = 0
while A:
    tmp = A[0]
    if tmp > 10**3:
        ans += len(A)
        break
    if len(A) > 1:
        if tmp not in A[1:]:
            ans += 1
        A = [a for a in A[1:] if a % tmp != 0]
    else:
        ans += 1
        break
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
a=sorted(A)
total=0
c=True
t=0
for i in range(N):
    if c==True:
        t=0
        for j in range(1,len(a)):
            if len(a)==0:
                c=False
                break
            try:
                if a[j-t]%a[0]==0:
                    del a[j-t]
                    t+=1
            except:
                break
        try:
            del a[0]
        except:
            break
        if c==True:
            total+=1
    else:
        break
print(total)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N = i()
A = l()
A.sort(reverse=True)
A = deque(A)
ans = 0
num = 0
def dv(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
for i in range(N):
    a = A[0]
    divs = dv(a)
    A.popleft()
    if a in A:
        ans += 1
        continue
    if divs:
        for d in divs:
            if d in A:
                num = 1
        if num :
            ans += 1
        num = 0
print(N-ans)

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  tf=[1]*n
  n=n-1
#r=[]
#print(n)
#print(a)
  #notdiv=True
  #firstyn=0
  for i in range(n,-1,-1):
  #print(i)
  #notdiv=True
    if tf[i] ==0:
      continue
    for j in range(i):
    #print(a[j])
      if a[i]%a[j] == 0:
        tf[i]=0
      break
  print(sum(tf))
main()

Submission status: Wrong Answer

Solution code:
# abc170_d.py
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
cnt = 0
for i in range(N):
    can_devide = False
    for j in range(i+1,N):
        if A[i] % A[j] == 0 and i != j:
            # print(A[i] , A[j])
            can_devide = True
            break
    if not can_devide:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
  n, = list(map(int, input().split()))
  cc = Counter(map(int, input().split()))
  aa = sorted(cc.keys())
  
  for i in range(0, len(aa)):
    x = aa[i]
    if cc[x] != 1:
      continue
    for j in range(i+1, len(aa)):
      aa[j] = aa[j] if aa[j] % x else 0
  print(sum(1 for a in aa if a > 0 and cc[a] == 1))
    
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

ans = 0

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

# エラトステネスの篩っぽく処理
search_list = deepcopy(A)
ans = 0

tmp = min(search_list)

while search_list:
    ans += 1
    search_list = [i for i in search_list if i % tmp != 0]
    if len(search_list) == 0:
        break
    else:
        tmp = min(search_list)
        if tmp > max(search_list)/2:
            ans += len(search_list)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
def _main(n, a_list):
    a_list.sort()
    count = 0
    one_cnt = 0
    need_check = True
    for i in range(n):
        i_value = a_list[i]

        if need_check:
            if i_value == 1:
                one_cnt += 1
                if 2 <= one_cnt:
                    print(0)
                    return
            elif one_cnt == 1:
                print(1)
                return
            else:
                need_check = False

        fail = False
        for j in range(0, min(i + 2, n)):
            if i == j:
                continue
            j_value = a_list[j]
            mod = i_value % j_value
            if mod == 0:
                fail = True
                break
            elif i_value / j_value <= 2.0:
                break
        if not fail:
            count += 1

    print(count)


if __name__ == "__main__":
    n_a = int(input())
    a_list_a = list(map(int, input().split()))
    _main(n_a, a_list_a)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N) : 
    B = list(map(lambda x: A[i] % x , A))
    print(B)
    if B.count(0) == 1 :
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
aL = sorted(list(map(int, input().split(" "))))

ans = n
for i in range(n - 1, -1, -1):
    for j in range(i):
        if aL[i] == aL[j]:
            break
        if aL[j] * 2 > aL[i]:
            break
        if aL[i] % aL[j] == 0:
            ans -= 1
            break

d = set()
for a in aL:
    d.add(a)
if len(d) == 1 and n != 1:
    print(0)
    exit()

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
x=[0 for i in range(N)]
ikiteru=list(range(N))
#print(ikiteru)
lis=[]
for i in range(N):
  if(i in ikiteru):
    if(i<N-1):
      if(A[i+1]!=A[i]):
        ans+=1
    for j in ikiteru:
      #print(j)
      if(A[j]%A[i]==0):
        lis.append(j)
    for k in lis:
      ikiteru.remove(k)
    lis=[]
  #print(ikiteru)
print(ans)
#print(x)

Submission status: Wrong Answer

Solution code:
# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()
N = int(input())
A = list(map(int, input().split()))
l = []
A.sort()
for i in range(0,N):
  for j in range(0,i+1):
    if i != j:
      if A[i] % A[j] == 0:
        break
    else:
      try:
        if A[i] == A[j+1]:
          break
        if A[i] == A[j-1]:
          break
      except:
        l.append(A[i])
        break

print(len(l))

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

N = int(input())
A = [int(a) for a in input().split()]

def get_prime_table(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            prime += data
            prime_table = [False] * (n + 1)
            prime_table[1] = True
            for p in prime:
                prime_table[p] = True

            return prime_table
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime_table = get_prime_table(10**6)
# print(prime_table)

# print("start")
# test = [i for i in range(10**6)]
# sorted(test, reverse=True)
# print("end")

A = Counter(A)
A = sorted(A.items(), key=lambda x: x[0])
# print(A)

ans = 0
divs = []
for i, n in A:
    flg = False
    if n > 1:
        continue
    if prime_table[i]:
        pass
    else:
        for j in divs:
            if i % j == 0:
                flg = True
    if flg:
        pass
    else:
        divs.append(i)
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    import copy
    n= int(input())
    inlis = list(map(int, input().split()))
    inlis.sort()
    counter = Counter(inlis).most_common()
    inset = set()

    for countset in counter:
        if countset[1] == 1:
            inset.add(countset[0])
    inset2 = copy.deepcopy(inset)
    
    for num in inset:
        new = [e for e in inset2 if e % num == 0]
        new.sort()
        #print(new, inset, inset2)
        if len(new) > 1:
            if new[0] != new[1]:
                for i in range(1, len(new)):
                    inset2.remove(new[i])
            else:
                for i in range(0, len(new)):
                    inset2.remove(new[i])
                

    print(len(inset2))



    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()
A.sort()

cc = collections.Counter(A)
a = []
for key in cc.keys():
    if cc[key] > 1:
        continue
    else:
        a.append(key)
a.sort()
chosen = []
# a = collections.deque(a)
# print(a)
cnt = 0
while len(a) > 0:
    # print(a)
    chosen = a[0]
    cnt += 1
    for a_i in a[0:]:
        if a_i % chosen == 0:
            a.remove(a_i)
    
print(cnt)