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())
As = sorted(list(map(int,input().split())))
# print(As)
cnt = 0
for i in range(N):
  for j in range(-1,i):
    if j == -1:
      if As[i] % As[(i+1)%N] == 0:
        # print(j,As[i],As[(i+1)%N])
        break
    elif As[i] % As[j] == 0:
      # print("break",i,j,As[i],As[j])
      break
  else:
    # print("cnt",As[i])
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:


n=int(input())
a=list(map(int,input().split()))
if len(list(set(a)))==1:
    print(0)
else:
    t=0
    a.sort()
    b={}
    for i in range(len(a)):
        for j in range(i+1,len(a)):

            if a[j] not in b and a[j]%a[i]==0:
                t+=1
                b[a[j]]=1
    print(n-t)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from bisect import bisect_right
from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = set(a)
m = len(b)
ans = 0
#print(a)
#print(b)

for i in b:
    if bisect_right(a, i) - bisect_left(a, i) > 1:
        pass
    else:
        for j in range(2, min(1000, int(i**0.5 + 1))):
            if (i/j in b) or ((i/j)%1==0 and (j in b)):
                break
        else:
            ans += 1
            #print(i)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(set(sorted(a)))
if len(b)==1:
    print(0)
else:
    total = 0
    while len(b) >0:
        for j in range(1,len(b)):
            if b[j]%b[0] == 0:
                b[j] = 0
            else:
                pass
        b = [s for s in b if s != 0]
        del b[0]
        total +=1
    print(total)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split(" "))))
for i in range(0, n):
    if len(a) <= i:
        break
    t = a[i]
    a = list(filter(lambda x: x % t != 0, a)) + [t]

if len(a) == 1:
    print(0)
else:
    print(len(a))

Submission status: Wrong Answer

Solution code:

def solve():
    memo = [1]*n
    cnt = 0
    for i in range(n):
        for j in range(2,n+1):
            #print(a[i])
#            print(a[i]%j)
            if a[i] % j == 0 and a[i] > n:
                memo[i] = 0
                #cnt += 1
    for i in range(n):    
        if memo[i] == 0:
            cnt += 1

#    print(memo)
    print(cnt)

if __name__=="__main__":
    n = int(input())
    a = list(map(int, input().split()))

    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    A = np.array(A, dtype=np.int64)

    if np.all(A == A[0]):
        print(0)
        exit()
    #print(A)

    cnt = np.any(A[1:] == A[0])
    memo = [1] * n
    for i in range(n - 1):
        for j in range(i + 1, n):
            if memo[j] == 0:
                break
            if A[j] % A[i] == 0:
                memo[j] = 0
                cnt += 1

    print(n - cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ns = list(map(int, input().split()))
ans = 0
from collections import Counter
c = Counter(ns)
dubbles = set([key for key, value in c.items() if value >= 2])
ns = sorted(ns)

for i in range(n):
    if i >= len(ns):
        break
    if ns[i] in dubbles:
        continue
    ans += 1
    j = i+1
    while j < len(ns):
        if ns[j] % ns[i] == 0:
            ns.pop(j)
        else:
            j += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from typing import List
from bisect import bisect


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

    ans = len(B)
    for b in B:
        i = bisect(A, b, 0, len(B))
        if i < len(A) and A[i] == b:
            ans -= 1
    return ans


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
a_list = [int(x) for x in input().split()]
dic = defaultdict(int)
for a in a_list:
    dic[a] += 1
d_list = sorted(dic.keys())
ans = 0
for d in d_list:
    if dic[d] > 1:
        continue
    stop = int(d ** 0.5) + 1
    for i in range(2, stop):
        q, mod = divmod(d, i)
        if mod == 0 and ((i in dic) or (q in dic)):
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import numpy as np

if os.path.exists('input.txt'):
    test_mode = True
else:
    test_mode = False

if test_mode:
    f = open('input.txt')
    
def get_input():
    if test_mode:
        return f.readline().rstrip()
    else:
        return input().rstrip()

def int_list(l):
    for i in range(len(l)):
        l[i] = int(l[i])


N = int(get_input())
A = get_input().split()
int_list(A)
A.sort()
ans = 0

for i in range(0, N):
    wareta = False
    for j in range(0, i):
        if A[i] % A[j] == 0:
            wareta = True
            break
    if not wareta:
        ans += 1
print(ans)
    
if test_mode:
    f.close()

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n==1:
        return False
    for k in range(2,int(n**0.5)+1):
        if n%k==0:
            return False
    return True

from collections import Counter
N=int(input())
A=sorted(list(map(int,input().split())))
c=Counter(A)
ans=0
for i in range(N):
    if c[A[i]]>1:
        continue
    if is_prime(A[i]):
        ans+=1
        continue
    for j in range(N):
        if A[i]/2<A[j]:
            ans+=1
            break
        if A[i]%A[j]==0:
            break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
visited=[False]*(10**6+1)

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

if N>=2 and A[1]==1:
  print(0)
  exit()
if A[0]==1 or N == 1:
  print(1)
  exit()
ans=0
for i in range(N):
  if visited[A[i]]:
    continue
  if i < N-1 and A[i]==A[i+1]:
    visited[A[i]]=True
    continue
  ans+=1
  index=1
  while A[i]*index<=10**6:
    visited[A[i]*index]=True
    index+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n!=1 and min(a)>max(a)//2:
  print(0)
  exit()
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

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


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(i) for i in input().split()])
if len(set(a)) == 1:
    print(0)
else:
    dict_a = dict()
    for ai in a:
        flag = True
        for da in dict_a.keys():
            if ai % da == 0:
                flag = False
        if flag:
            dict_a[ai] = 1
    print(len(dict_a))

Submission status: Wrong Answer

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

n = int(input())
A = list(map(int, input().split()))
A.sort()
cnts = defaultdict(lambda: 0)
for a in A:
   cnts[a] += 1

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

   upper_divisors.reverse()
   return set(lower_divisors + upper_divisors)

is_ok = defaultdict(lambda: True)
divs = defaultdict(lambda: None)
cnt = 0
for a in A:
   if is_ok[a] == False or cnts[a] > 1:
      continue
   if divs[a] == None:
      divs[a] = make_divisors(a)
   f = True
   for div in divs[a]:
      if not is_ok[div]:
         f = False
   if f:
      cnt += 1
   is_ok[a] = False
print(cnt)

Submission status: Wrong Answer

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

import sys
from math import gcd
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *A = map(int, read().split())
A = np.array(sorted(A))

cnt = 0
while len(A) > 0:
    acc = A[0]
    idxs = (A == acc)
    if sum(idxs) >= 2:
        A = A[~idxs]
    if len(A) == 0:
        break
    idxs = (A % A[0] != 0)
    idxs[0] = True
    A = A[idxs][1:]
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import math
import sys
 
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True


n=int(input())
As = list(map(int, input().split()))
i=0
j=0
count =0
if As.count(1)==1:
    print(1)
    sys.exit()
if As.count(1)>=2:
    print(0)
    sys.exit()
for a in As:
    for b in As:
        if As.count(a)>=2:
            break
        elif isPrime(a):
            count+=1
            break
        if i!=j:
            if a%b==0:
                break
            elif j==n-1:
                count+=1
        j+=1
    i+=1
    j=0

print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
from math import sqrt
from collections import Counter,defaultdict
def func(t):
    for i in range(1,int(sqrt(t))+1):
        if  t%i==0 and (i in s or (t//i!=t and t//i in s)):
            #print(i)
            return False
    return True
n = int(input())
a = list(map(int,input().split()))
s = Counter(a)
#d = defaultdict(int)
ans = 0
for i in s:
    if s[i]==1:
        ans+=func(i)
        #if func(i):
        #    #print(i)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections

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


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

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

                    k -= 1

        print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

if len(a_list) == 1:
    print(0)
else:
    if a_list[0] != a_list[1]:
        ans += 1
    for i in range(1, n):
        for j in range(i):
            if a_list[i] % a_list[j] == 0:
                break
            if a_list[j] > a_list[i] / 2:
                ans += 1
                break

print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in A:
    # print(i)
    if a[i] == 0:
        ans += 1
        k = 1
        while k <= A[-1]//i:
            a[i * k] += 1
            k += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
hitoketa=[]
count=0
A=list(map(int,input().split()))
A.sort()
for i in range(min(10,N)):
    if A[i]<10:
        hitoketa.append(A[i])
    else:
        break
for i in range(len(hitoketa)):
    for j in range(len(hitoketa)):
        if hitoketa[i]%hitoketa[j]==0 and hitoketa[i]!=hitoketa[j]:
            hitoketa[i]=10**6+1
#print(hitoketa)
for i in A:
    for j in hitoketa:
        if i != j and i%j==0:
            count+=1
            continue
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A=sorted(set(map(int,input().split())),reverse=True)
judge = True
count = 0
if len(A) > 1:
  for i in range(len(A)):
    judge = True
    for j in range(i+1, len(A)):
      if A[i]%A[j]==0:
        judge = False
        break
    if judge:
      count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = list(map(int, input().split()))
A.sort()
done = []
ans_set = set()
before = A[0]
done.append(before)
ans_set.add(before)

for a in A[1:]:
    if before == 1:
        break
    if before == a:
        if a in ans_set:
            ans_set.remove(a)
        continue
    flag = True
    for b in done:
        if a % b == 0:
            flag = False
            break
        if a < b*2:
            break
    if flag:
        done.append(a)
        ans_set.add(a)
    before = a

print(len(ans_set))

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    if len(A)==1:
        ans=0
    elif A[0]==A[1]:
        ans=0
    else:
        ans=1
    
    for i in range(1,N):
        for j in range(i):
            if A[i]%A[j]==0:
                break
            if A[j] > A[i]*0.5:
                ans+=1
                break
        else:
            ans+=1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#D
from collections import deque
n = int(input())
a = list(map(int,input().split()))
flgs = [False] * n
renban = False
flg = True

cnt = 0
a.sort(reverse=True)
# = deque(a)
#print(a)

for i in range(n):
    flg = True
    for j in a[:i:-1]:
        if j == a[i+1]:
            if j == a[i]:
                renban = True
        #print("j:",j)
        if a[i] % j == 0:
            flg = False
            break
    if flg:
        if not renban:
            cnt += 1
        
print(cnt)

Submission status: Wrong Answer

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

A.sort()
counter_ = 0
i = 0
while i < N - counter_:
    j = 0
    judge_ = True
    while j < i:
        if A[i] % A[j] == 0:
            counter_ += 1
            judge_ = False
            break
        j += 1
    if judge_: 
        i += 1
    else:
        del A[i]
print(N - counter_)

Submission status: Wrong Answer

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

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

    a = A[j]
    if cnt[a] > 1:
        continue
    if j==0:
        ans+=1

    i = bisect.bisect_right(A, pow(a,0.5))
    if i==len(A):
        i-=1
    #print(a,i)


    ok = True

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
nux = max(A)
B = set(A)
A.sort()
ans = 0
C = dict()
D = list(B)
nn = len(D)
for s in B:
    C[s] = True
for iii, s in enumerate(B):
    if not C[s]:
        continue
    if A.count(s) == 1:
        ans += 1
    if s > nux//2:
        continue
    while iii <= nn-1:
        if D[iii] % s == 0:
            C[D[iii]] = False
        iii += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#デフォルト
import itertools
from collections import defaultdict
import collections
import math
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

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

a.sort()
ans = 0
dic = defaultdict(int)
for i in range(n):
    dic[a[i]] += 1

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

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

print(ans)

Submission status: Wrong Answer

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

#O(nlogn)
A.sort()

#カウンタ
i=1

while len(A)>i:
  #iの先頭要素を取り出す
  a = A[i]
  #aはdividerになれるのか？
  max_soinsu=math.floor(a**(0.5))

  isDivider=True
  for divider in A[:i]:
    if a % divider == 0:
      #割り切れるようなやつはまとめて死
      A = [a_ for a_ in A if a_ != a]
      isDivider=False
      break
    if divider >= max_soinsu:
      break

  if isDivider:
    i += 1

print(len(A))

Submission status: Wrong Answer

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

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

def main(kwargs):
    n = kwargs["n"]
    A = kwargs["A"]
    A = collections.deque(sorted(A))
    B = collections.deque([])
    res = 0
    j = 1

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

        j += 1

    while len(A) > 0:
        now = A.popleft()
        flg = True

        for b in B:
            if now % b == 0:
                flg = False

        if flg:
            B.append(now)

    res += len(B)

    return res

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

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

    cout = main(kwargs)
    print(cout)

Submission status: Wrong Answer

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

a.sort()
b = False
if n > 1:
    if a[0] == a[1]:
        b = True
max = a[n - 1]
upper = math.sqrt(max)

for i in range(n):
    if a[i] != 0:
        for j in range(i + 1,n):
            if a[j] % a[i] == 0:
                a[j] = 0

if b:
    a[0] = 0

ans = n - a.count(0)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
a_list = [int(_) for _ in input().split()]

a_list = list(sorted(a_list))
c = Counter(a_list)
dup_list = [k for k, v in c.items() if v > 1]

b_list = a_list

ans = []

while b_list != []:
    x = b_list[0]
    if x in a_list:
        a_list = list(filter(lambda z: (z%x != 0 or z==x) and x not in dup_list, a_list))
    b_list.pop(0)

print(len(a_list))

Submission status: Wrong Answer

Solution code:


import collections
import math

def get_sieve_of_eratosthenes_new(data):
    prime = []
    # limit = math.sqrt(n)
    limit = max(data)
    # data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data


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)

    if not al_not_multi:
        print(0)
        return

    al_not_multi.sort()
    # ans = get_sieve_of_eratosthenes_new(al_not_multi)
    # print(len(ans))

    ans = 0
    while al_not_multi:
        p = al_not_multi[0]
        al_not_multi = [e for e in al_not_multi[1:] if e % p != 0]
        ans += 1


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

Submission status: Wrong Answer

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

a.sort()

MAXN = 10 ** 6


divisors = [False for _ in range(MAXN + 1)]
answer = 0
apast = None
for i, ai in enumerate(a):
    if ai == apast:
        is_good = False
    elif i < n - 1 and ai == a[i + 1]:
        is_good = False
    else:
        is_good = not divisors[ai]

        m = 1
        while ai * m <= MAXN:
            divisors[m * ai] = True
            m += 1

    if is_good:
        answer += 1

    apast = ai


print(answer)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    def eratos(n):
        flag = [True] * (n + 1)
        for i in range(2, int(n**0.5) + 1):
            if flag[i]:
                for j in range(2*i, n + 1, i):
                    flag[j] = False
        return [i for i, x in enumerate(flag) if x and i >= 2]
    n = int(input())
    A = sorted(list(map(int, input().split())))
    c = Counter(A)
    result = 0
    piyo = []
    prime = eratos(10**6)
    for k, v in c.items():
        if v > 1:
            piyo.append(k)
            for _ in range(v):
                A.remove(k)
    for a in A:
        flag = False
        if a in prime:
            piyo.append(a)
            result += 1
            continue
        for hoge in piyo:
            if a % hoge == 0:
                flag = True
                break
        if not flag:
            piyo.append(a)
            result += 1
    print(result)
main()

Submission status: Wrong Answer

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

i = 0
while i < len(A)-1:
    if A[i] == A[i+1]:
        a = A[i]
        while a in A:
            A.remove(a)
    i += 1

i = 0
while i < len(A):
    a = A[i]
    j = i + 1
    while j < len(A):
        if A[j] % a == 0:
            A.pop(j)
        else:
            j += 1
    i += 1

print(len(A))

Submission status: Wrong Answer

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

ans = 0
for i in range(N):
    if i == 0:
        if N != 1 and A[0] != A[1]:
            ans += 1
    else:
        if all(A[i] % A[i - j] != 0 for j in range(1, i + 1)):
            ans += 1
print(ans)

Submission status: Wrong Answer

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

N = int(input())

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

AList.sort()

ResultList = []

tmp = 0

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


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

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

print(len(ResultList))

Submission status: Wrong Answer

Solution code:
import numpy as np

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


def enum_devider(n):
  rn = int(np.sqrt(n))
  divider = []
  for i in range(1, rn):
    if n % i == 0:
      divider.append(i)
      divider.append(n // i)
  if n % rn == 0:
    divider.append(rn)
  return divider

positive = set([])
double = set([])
for a in A:
  ok = True
  if a in positive:
    double.add(a)
  for d in enum_devider(a):
    if d in positive:
      ok = False
      break
  if ok:
    positive.add(a)

print(len(positive) - len(double))

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())

alist = list(map(int, input().split()))
alist.sort()
EncountSosuu = [alist[0]]

# 同じ数のみならば0
if (len(list(set(alist))) == 1):
    print(0)
    sys.exit()


ans = 1

for i in range(1, n):
    isDivide = False
    for j in EncountSosuu:
        if (alist[i] % j == 0):  # 今迄にあった数で割り切れれば
            #print("divide", alist[i], j)
            isDivide = True
            break
    if(not(isDivide)):
        ans += 1
        EncountSosuu.append(alist[i])
        #print("append", alist[i])
    # print()
print(ans)

Submission status: Wrong Answer

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

a=sorted(a)

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


print(ans)

Submission status: Wrong Answer

Solution code:
def ok(p,q):
    for x in q:
        if p % x == 0:
            return False
    return True


n = int(input())
a = list(map(int,input().split()))
a.sort()
c = 1
for i in range(1,n):
    b = a[:i]
    if ok(a[i],b) == True:
        c += 1

if c == 1:
    if ok(a[0],a) == False:
        c -= 1
print(c)

Submission status: Wrong Answer

Solution code:
from numba import jit


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


N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
ans = solve(N,A)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    def eratos(n):
        flag = [True] * (n + 1)
        for i in range(2, int(n**0.5) + 1):
            if flag[i]:
                for j in range(2*i, n + 1, i):
                    flag[j] = False
        return [i for i, x in enumerate(flag) if x and i >= 2]
    n = int(input())
    A = sorted(list(map(int, input().split())))
    c = Counter(A)
    result = 0
    piyo = []
    prime = eratos(10**6)
    print(prime)
    for k, v in c.items():
        if v > 1:
            piyo.append(k)
            for _ in range(v):
                A.remove(k)
    for a in A:
        flag = False
        if a in prime:
            piyo.append(a)
            result += 1
            continue
        for hoge in piyo:
            if a % hoge == 0:
                flag = True
                break
        if not flag:
            piyo.append(a)
            result += 1
    print(result)
main()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
a.sort()
b = []
ans = n

for i in a:
    for p in range(len(b)):
        j,k = b[p]
        if j > i/2:
            break
        if i%j == 0:
            ans -= 1
            if i == j and k == 0:
                ans -= 1
                b[p] = (j,1)
            break
    else:
        b.append((i,0))

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n!=1 and min(a)>max(a)//2:
  print(n)
  exit()
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
c = 0
b = 0
for i in range(n):
    if i > 0 and a[i] != a[i - 1]:
        b = 0
    elif i > 0 and b == 0 and a[i] == a[i - 1]:
        c -= 1
        b = 1
    for j in range(i):
        if a[i] % a[j] == 0:
            break
    else:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
def _main(n, a_list):
    a_list.sort()
    count = 0
    one_cnt = 0
    for i in range(n):
        i_value = a_list[i]
        if i_value == 1:
            one_cnt += 1
            if 2 <= one_cnt:
                print(n)
                return
        elif one_cnt == 1:
            print(n - 1)
            return

        fail = False
        for j in range(0, min(i + 2, n)):
            if i == j:
                continue
            j_value = a_list[j]
            q, mod = divmod(i_value, j_value)
            if mod == 0:
                fail = True
                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())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
for i in range(len(p)):
    for j in reversed(range(i+1,len(p))):
        if p[i]%p[j] ==0:
            break
        if j == i+1:
            count +=1
if count >=1:
    print(count+1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
ans = []
prev_val = A[0]
while len(A) > 0:
    tmp = A[0]
    A = A[1:]
    A_tmp = []
    if len(A) == 0:
        if prev_val != tmp:
            ans.append(tmp)
        break
    if tmp == A[0]:
        continue
    for a in A:
        if a % tmp != 0:
            A_tmp.append(a)
    A = A_tmp
    ans.append(tmp)
    prev_val = tmp
print(len(ans))