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

setA = set(A)
from collections import defaultdict
cnt = defaultdict(int)

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


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]

score = 0
for a in A:
    if cnt[a] > 1:
        print("cont", a)
        continue
    
    divisors = make_divisors(a)

    ng = False
    for d in divisors:
        if d==a: continue
        if d in setA:
            ng = True
            
    if not ng:
        score += 1
    # print(a, divisors)
print(score)

Submission status: Wrong Answer

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

setA = set(A)
from collections import defaultdict
cnt = defaultdict(int)

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


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]

score = 0
for a in A:
    if cnt[a] > 1:
        print("cont", a)
        continue
    
    divisors = make_divisors(a)

    ng = False
    for d in divisors:
        if d==a: continue
        if d in setA:
            ng = True
            print("ng", a, d)
    if not ng:
        score += 1
    # print(a, divisors)
print(score)

Submission status: Wrong Answer

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

setA = set(A)
from collections import defaultdict
cnt = defaultdict(int)

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


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]

score = 0
for a in A:
    if cnt[a] > 1:
        continue
    divisors = make_divisors(a)
    ng = False
    for d in divisors:
        if d in setA:
            ng = True
    if not ng:
        score += 1
    # print(a, divisors)
print(score)

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        print(j)
        tf[j]=True
      if a_i < a[i+1]:
        #print(a_i)
        r+=1
  if tf[-1] ==False:
    r+=1
  print(r)
main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
#a = list(set(a))
a.sort(reverse=True)
print(a)
counter = 0
for i in range(n):
  start = 0
  if a[i] == 0:
    continue
  for j in range(n-1,i,-1):
    if a[i] == a[j]:
      a[j]=0
      start = 1 
    if a[j] != 0:
      if a[i] % a[j] == 0:
        start = 1
        break
  if start == 0:
    counter+=1
print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
counter = 0
for i in range(n-1):
  start = 0
  if a[i] == 0:
    continue
  for j in range(n-1,i,-1):
    if a[i] == a[j]:
      a[j]=0
      start = 1 
    if a[j] != 0:
      if a[i] % a[j] == 0:
        start = 1
        break
  if start == 0:
    counter+=1
print(counter)

Submission status: Wrong Answer

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

is_valid = [True] * n
for i in range(n-1):
    if not is_valid[i]:
        continue
    for j in range(i+1, n):
        if not is_valid[j]:
            continue
        if A[j] % A[i] == 0:
            is_valid[j] = False

for i in range(1, n):
    if A[0] % A[j] == 0:
        is_valid[0] = False
        break

print(sum(is_valid))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
cnt = 0
cnt2 = 0
for i in A:
    for j in A:
        if i != j:
            if i%j == 0:
                cnt += 1
    if i != j:
        if cnt == 0:
            cnt2 += 1
    cnt = 0
print(cnt2)

Submission status: Wrong Answer

Solution code:
def prime(data):
    data=list(set(data))
    data.sort()
    if len(data)==1:
        return []
    ans_list=data.copy()
    for i in range(0,len(data)-1):
        for j in range(i+1,len(data)):
            if data[i]!=data[j] and data[j]%data[i] == 0:
                if data[j] in ans_list:
                    ans_list.remove(data[j])
    return ans_list

N=int(input())
A=list(map(int,input().split()))
ans=len(list(prime(A)))
print(ans)

Submission status: Wrong Answer

Solution code:
def prime(data):
    data=list(set(data))
    data.sort()
    ans_list=data.copy()
    for i in range(0,len(data)-1):
        for j in range(i+1,len(data)):
            if data[i]!=data[j] and data[j]%data[i] == 0:
                if data[j] in ans_list:
                    ans_list.remove(data[j])
    return ans_list

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

Submission status: Wrong Answer

Solution code:
def eratosthenes(A):
    data = A
    for d in data:
        for i in data:
            if i!=d and i%d == 0:
                data.remove(i)
    return data

N=int(input())
A=list(map(int,input().split()))
ans=list(eratosthenes(A))
print(len(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.uint64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
      d[a::a] += 1
    else:
      d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
print(main())

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[False]*(10**6+1)
for i in a:
  dp[i]=True
for i in range(10**6+1):
  if dp[i]:
    for  j in range(2*i,10**6+1,i):
      dp[j]=False
print(dp.count(1))

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
l=list(map(int,input().split()))
c=collections.Counter(l)
def j(n):
  judge=1
  for k  in c.keys():
      if n%k==0:
        if n!=k:
          judge=0
          break
  return judge
count=0
if len(list(c.keys()))==1:
       print(count)
else:
  for k in c.keys():
    if j(k)==1:
      count+=1
  print(count)

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
l=list(map(int,input().split()))
c=collections.Counter(l)
def j(n):
  judge=1
  for k  in c.keys():
      if n%k==0:
        if n!=k:
          judge=0
          break
  return judge
count=0
for k in c.keys():
  if j(k)==1:
    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
l=list(map(int,input().split()))
c=collections.Counter(l)
def j(n):
  j=1
  for k  in c.keys():
      if n%k==0:
        if n!=k:
          j=0
          break
count=0
for i in c.keys():
  if j(i)==1:
    count+=1
print(count)

Submission status: Wrong Answer

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

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

else:
    A = sorted(A)
    count = 1
    for i in range(1, len(A)):
      flag = 0
      for j in range(0, i):
        if A[i] % A[j] == 0:
          flag = 1
      if flag == 0:
        count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
def aline_mintomax(arr, N):
    for i in reversed(range(1,N)):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

N = int(input()) # 【1行】1数字
num_list = list(map(int, input().split())) 
ind_list = [i for i in range(N)]
num_list = aline_mintomax(num_list, N)
for i in range(N-1):
    if num_list[i+1] == num_list[i]:
        ind_list[i] = -1
        continue
    for j in range(i):
        if num_list[i] % num_list[j] == 0 :
            ind_list[i] = -1
            break
for i in range(N-1):
    if num_list[N-1] % num_list[i] == 0 :
        ind_list[N-1] = -1
        break
print(ind_list.count(-1))

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
def aline_mintomax(arr, N):
    for i in reversed(range(1,N)):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

N = int(input()) # 【1行】1数字
num_list = list(map(int, input().split())) 
ind_list = [i for i in range(N)]
num_list = aline_mintomax(num_list, N)
for i in range(N-1):
    if num_list[i+1] == num_list[i]:
        ind_list[i] = -1
        continue
    for j in range(i):
        if num_list[i] % num_list[j] == 0 :
            ind_list[i] = -1
            break
for i in range(N-1):
    if num_list[N-1] % num_list[i] == 0 :
        ind_list[i] = -1
        break
print(ind_list.count(-1))

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
def aline_mintomax(arr, N):
    for i in reversed(range(1,N)):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

N = int(input()) # 【1行】1数字
num_list = list(map(int, input().split())) 
ind_list = [i for i in range(N)]
num_list = aline_mintomax(num_list, N)

for i in range(N-1):
    if num_list[i+1] % num_list[i] == 0 :
        ind_list.remove(i)
        continue
    for j in range(i):
        if num_list[i] % num_list[j] == 0 :
            ind_list.remove(i)
            break
for i in range(N-1):
    if num_list[N-1] % num_list[i] == 0 :
        ind_list.remove(N-1)
        break
print(len(ind_list))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
MAX = a[-1]
l = [0]*(MAX+1)
for i in range(n):
    l[a[i]] += 1

ans=0
for i in range(n):
    if l[a[i]]==1:
        ans+=1
        for g in range(a[i],MAX+1,a[i]):
            l[g] = 10
        
print(ans)

Submission status: Wrong Answer

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

b=[]


while True:    
    if len(a) == 0:
        break
    i = a.pop(0)
    a = [x for x in a if x%i != 0]
    b.append(i)

    
print(len(b))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
N = int(input())
As = list(map(int,input().split()))
ct = Counter(As)
As =sorted(As)
max_dp = As[-1] +1
dp = [True] * max_dp
for key,count in ct.items():
	if count > 1:
		dp[key] = False
for A in As:
	if dp[A] == True:
		i = 2
		while A*i < max_dp:
			dp[A*i] = False
			i+=1

ans = 0
# print(len(dp))
for A in As:
	# print(A)
	if dp[A]:
		ans+=1
print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)
ans = 0

for i in range(n-1):
    for j in range(i+1, n):
        if A[i] % A[j] == 0:
            break
    else:
        ans += 1
if n >= 2 and A[-2] != A[-1]:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def append_factors(n, f, p):
    num_factors = 0
    while n % p == 0:
        num_factors += 1
        n //= p
    if num_factors != 0:
        f[p] = num_factors
    return n

def factors(n):
    ret = {}
    n = append_factors(n, ret, 2)
    n = append_factors(n, ret, 3)
    i = 6
    while i*i <= n + 1:
        n = append_factors(n, ret, i - 1)
        n = append_factors(n, ret, i + 1)
        i += 6
    if n != 1:
        ret[n] = 1

    return ret

def solve(A, fs, i, l, r):
    if l == r and l == i:
        return False

    f = {}
    for key in fs[i]:
        v = fs[i][key]
        if i != 0 and key in fs[i - 1]:
            v -= fs[i - 1][key]
        if v != 0:
            f[key] = v
    g = {}
    for key in fs[r]:
        v = fs[r][key]
        if l != 0 and key in fs[l - 1]:
            v -= fs[l - 1][key]
        if v != 0:
            g[key] = v

    # print('f={}'.format(f))
    # print('g={}'.format(g))
    # g|f
    found = False
    divisible = True
    for key in g:
        if key in f:
            found = True
        else:
            divisible = False
        if key in f and g[key] > f[key]:
            divisible = False
            break
    # if not found:
    #     # f|g
    #     found = True
    #     for key in f:
    #         if key not in g:
    #             found = False
    #             break
    #         if f[key] > g[key]:
    #             found = False
    #             break
    if found:
        if l == r:
            return divisible
        c = (r + l)//2
        found = solve(A, fs, i, l, c)
        if found:
            return True
        found = solve(A, fs, i, c + 1, r)

    return found

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # print(N, A)
    fs = []
    ans = 0
    for a in A:
        found = False
        f = factors(a)
        if len(fs) != 0:
            tmp_f = fs[-1]
            for i in tmp_f:
                if i not in f:
                    f[i] = 0
                f[i] += tmp_f[i]
        fs.append(f)
    # print(fs)
    for i in range(N):
        # if i != N - 1:
        #     continue
        found = False
        if i != 0:
            found = solve(A, fs, i, 0, i - 1)
        # if found:
        #     print('{} found left'.format(i))
        if not found and i != N - 1:
            found = solve(A, fs, i, i + 1, N-1)
            # if found:
            #     print('{} found right'.format(i))
        if found:
            ans += 1

    print(N - ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
dp=["True"]*(max(a)+1)
dp[0]="False"
a.sort()
seen=set()
pre=0
for x in a:
    if x==pre:
        if x in seen:
            seen.remove(x)
        continue
    if dp[x]=="True":
        seen.add(x)
    pre=x
    i=1
    while x*i<=max(a):
        if dp[x*i]=="True":
            dp[x*i]=="False"
        i+=1
print(len(seen))

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
dp=["True"]*(max(a)+1)
dp[0]="False"
a.sort()
seen=set()
for x in a:
    if dp[x]=="True":
        seen.add(x)
        pre=x
    if x in seen:
        seen.remove(x)
        continue
    i=1
    while x*i<=max(a):
        dp[x*i]="False"
        i+=1
print(len(seen))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

N = int(input())
A = list(map(int, input().split()))
A = list(set(A))
A.sort()                  #エラトステネスの篩にかけるためソート

Amax = A[-1]              #最大値
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る
ans = 0
# print(A)
if len(A)!=1:
    for i in range(len(A)):
      p = A[i]
      if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
        
        for q in range(Amax//p+1):
          dp[p*q] = 0         #A[i]の倍数をすべて0にする
        # print(dp)
      else:
          ans+=1
        #   print(A[i])
    #     if A[i] != A[i+1]: 
    #       ans += 1            #A[i]が重複していなければカウント
    #     print(ans)
    # if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
    #   ans += 1
    print(len(A)-ans)
else:
    print(0)

Submission status: Wrong Answer

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

a.sort()
array = []
for _ in range(n):
  array.append(True)
  
for i in range(n):
  if (array[i]):
    if i < n-1 and a[i] == a[i+1]:
      array[i] = False
      array[i+1] = False
      
    else:
      for j in range(i):
        if (array[j] and a[i] % a[j] == 0):
          array[i] = False
          break
print(array.count(True))

Submission status: Wrong Answer

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

a.sort(reverse=True)

count = 0
# i<n-1
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        if all([a[i] % a[j] != 0 for j in range(i + 1, n)]):
            count += 1
# i==n-1
if a[n-2] != a[n-1]:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

N = int(input())
A = list(map(int, input().split()))
A.sort()                  #エラトステネスの篩にかけるためソート
Amax = A[-1]              #最大値
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る
ans = 0
# print(A)
for i in range(len(A)):
  p = A[i]
  if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
    
    for q in range(Amax//p+1):
      dp[p*q] = 0         #A[i]の倍数をすべて0にする
    # print(dp)
  else:
      ans+=1
    #   print(A[i])
#     if A[i] != A[i+1]: 
#       ans += 1            #A[i]が重複していなければカウント
#     print(ans)
# if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
#   ans += 1
print(len(A)-ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
Alis = list(map(int, input().split()))
Alis.sort()
Alis = [a for a in Alis if Alis.count(a) == 1]
n = len(Alis)
dp = [True]*n
for i in range(n):
    if dp[i]:
        for j in range(i, n):
            if dp[j]:
                if Alis[j] % Alis[j]:
                    dp[j] = False
print(dp.count(True))

Submission status: Wrong Answer

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

a.sort(reverse=True)

count = 0
# i<n-1
for i in range(n-1):
    if all([a[i] % a[j] != 0 for j in range(i + 1, n)]):
        count += 1
# i==n-1
if any([a[0] != a[i] for i in range(n)]):
    count += 1
    
print(count)

Submission status: Wrong Answer

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

# エラトステネスの篩
is_ans = [True] * (10**6 + 1)
s = list(set(As))
for x in s:
  t = x * 2
  while t < 10**6:
    is_ans[t] = False
    t += x

cnt = 0
for x in s:
  if c[x] == 1 and is_ans[x] == True:
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_right, bisect_left

class SegmentTree:

    def __init__(self, N):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.data1 = [0] * (2*self.N)
        self.data2 = [0] * (2*self.N)

    # [a, b) に x を加算する
    def add(self, a, b, x, k = 0, l = 0, r = -1):
        if r == -1: r = self.N
        if r <= a or b <= l: return
        if a <= l and r <= b:
            self.data1[k] += x
        else:
            self.add(a, b, x, k*2+1, l, (l+r)//2)
            self.add(a, b, x, k*2+2, (l+r)//2, r)
            self.data2[k] = max(self.data1[k*2+1]+self.data2[k*2+1], self.data1[k*2+2]+self.data2[k*2+2])

    # [a, b) の和を計算する
    def sum(self, a, b, k = 0, l = 0, r = -1):
        if r == -1: r = self.N
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.data1[k]+self.data2[k]
        vl = self.sum(a, b, k*2+1, l, (l+r)//2)
        vr = self.sum(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr) + self.data1[k]

N = int(input())
A = list(map(int, input().split()))
A.sort()
if A[0] == 1:
    print(0)
    exit()
seg = SegmentTree(N+1)
for i in range(N):
    l = bisect_left(A, A[i])
    r = bisect_right(A, A[i])
    if r-l > 1:
        seg.add(l, r, 1)
    j = 2
    while A[i]*j <= A[-1]:
        l = bisect_left(A, A[i]*j)
        r = bisect_right(A, A[i]*j)
        if l < r:
            seg.add(l, r, 1)
        j += 1
ans = 0
for i in range(N):
    if seg.sum(i, i+1) == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

a.sort(reverse=True)

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    dp = [0 for i in range(n)]
    dp[0] = 1
    w = [a[0]]
    for i in range(1,n):
        if a[i]==a[i-1]:
            dp[i] = max(0,dp[i-1]-1)
        else:
            if a[i]%a[i-1]==0:
                dp[i] = dp[i-1]
            else:
                flg = 0
                for j in range(len(w)):
                    if a[i]%w[j]==0:
                        flg = 1
                        dp[i] = dp[i-1]
                        break
                if flg == 0:
                    dp[i] = dp[i-1] + 1
                    w.append(a[i])
    print(dp[n-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    c = Counter(A)

    for a in set(A):
        if c[a] > 1:
            continue
        v = 2*a
        while v <= 10**6:
            c[v] += 1
            v += a

    ans = 0
    for a in A:
        if c[a] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

n = int(input())

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

au = sorted(list(set(a)))

c = [0] * (10**6+1)
for i in a:
    if i not in c:
        c[i] += 1

uni = []

for i in au:
    if c[i] == 1:
        uni.append(i)

b = [0 for _ in range(10**6+1)]

for i in au:
    for j in range(i*2, 10**6+1, i):
        b[j] = 1

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))
A_c = Counter(A)
A_max = A[-1]

dp = [True] * (A_max + 1)
counter = 0
for i in range(len(A) - 1):
    p = A[i]
    if dp[p] == False:
        continue
    else:
        for q in range(A_max // p + 1):
            dp[p * q] = False
        if p != A[i+1]:
            counter += 1
    if dp[A_max] == 1:
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(i) for i in input().split()])
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(cnt_d.count(1))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
A.sort()
count = 0
for i in range(N):
    for j in range(i+1):
        if A[i] % A[j] == 0 and i != j:
            count += 1
            break
print(N-count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
A.sort()
count = 0
for i in range(N):
    for j in range(i):
        if A[i] % A[j] == 0 and i != j:
            count += 1
            break
print(N-count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
A.sort()
count = 0
for i in range(N):
    for j in range(i,N):
        if A[i] % A[j] == 0 and i != j:
            count += 1
            break
print(N-count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
count = 0
B = list(set(A))
B.sort()
if len(B) != N:
    count = N - len(B) + 1
for i in range(len(B)):
    for j in range(len(B)):
        if B[i] % B[j] == 0 and i != j:
            count += 1
            break
print(N-count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
#A.sort()
count = 0
B = list(set(A))
if len(B) != N:
    count = N - len(B) + 1
for i in range(len(B)):
    for j in range(len(B)):
        if B[i] % B[j] == 0 and i != j:
            count += 1
            break
print(N-count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(i) for i in input().split()])
max_a = max(a)
cnt_d = [0] * (max_a + 1)
cnt_nd = 0
for ai in a:
    if cnt_d[ai] >= 1:
        continue
    else:
        cnt_d[ai] += 1
        cnt_nd += 1
    multi = 2
    while ai*multi <= max_a:
        cnt_d[ai*multi] += 1
        multi += 1
print(cnt_nd)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
count = 0
for i in range(len(A)):
    for j in range(len(A)):
        if A[i] % A[j] == 0 and i != j:
            count += 1            
print(len(A)-count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

prime = [True for i in range(10**6)]

for a in A:
    if(prime[a-1]):
        for j in range(a*2, 10**6, a):
            prime[j-1] = False

cnt = 0
for i in A:
    if(prime[i-1]):
        cnt += 1
        
c = Counter(A)
cc = sorted(c.items(), key=lambda x:x[1], reverse=True)

if(N == len(cc)):        
    print(cnt)
else:
    print(cnt-(N-len(cc)-1))

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(x) for x in input().split()]

set_l = set(l)
set_l = sorted(set_l)
limit = 10**6+1
mp = [0]*(limit)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    for y in range(x,limit,x):
        mp[y] += 1
        

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(x) for x in input().split()]

set_l = set(l)
set_l = sorted(set_l)
limit = 10**6
mp = [0]*(limit+1)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    num = x
    for y in range(num,limit+1,num):
        mp[y] += 1
        

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
r=0
f=set(a)
for i in a:
  ff=0
  for j in range(1,int(pow(i,0.5))+1):
    if(i%j==0):
      if(j in f or i//j  in f):
        ff=1
  if(ff==0):
    r+=1
print(r)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(x) for x in input().split()]

set_l = set(l)
set_l = sorted(set_l)
limit = 10**6
mp = [0]*(limit+1)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

cnt = 0
for x in set_l:
    num = x
    while(x <= limit):
        mp[x] += 1
        x += num
    if(mp[num]==1):
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = sorted(list(map(int, input().split())))
count_arr = [0]*arr[-1]

ans = 0
for i in arr:
    if count_arr[i-1] == 0:
        ans += 1
    for j in range(1,(arr[-1]//i)+1):
        count_arr[(i*j)-1] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
r=0
f=set()
for i in a:
  ff=0
  for j in range(1,int(pow(i,0.5))+1):
    if(i%j==0):
      if(j in f or i//j  in f):
        ff=1
  if(ff==0):
    r+=1
  f.add(i)
print(r)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
r=0
f=set()
for i in a:
  f1=set()
  ff=0
  for j in range(1,int(pow(i,0.5))+1):
    if(i%j==0):
      f1.add(j)
      f1.add(i//j)
      if(j in f or i//j  in f):
        ff=1
  if(ff==0):
    r+=1
  for j in f1:
    f.add(j)
print(r)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
r=0
f=set()
for i in a:
  f1=set()
  ff=0
  for j in range(1,int(pow(i,0.5))+1):
    if(i%j==0):
      f1.add(j)
      f1.add(i//j)
      if(i in f or i//j  in f):
        ff=1
  if(ff==0):
    r+=1
  for j in f1:
    f.add(j)
print(r)

Submission status: Wrong Answer

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


A.sort()


ans=0

for i in range(N):
	check=True
	for j in range(0,i):
		if A[i] == A[j]:
			continue
		if ( A[i]%A[j] == 0 ):
			check=False

	if check == True:
		ans+=1
      
print(ans)

Submission status: Wrong Answer

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


ans=0

for i in range(N):
	check=True
	for j in range(N):
		if  i == j :
			continue
		if A[i] == A[j]:
			continue
		if ( A[i]%A[j] == 0 ):
			check=False

	if check == True:
		ans+=1
      
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
i = 0
a,c=np.unique(a,return_counts=True)
if 1 in a:
    print(0)
    exit()
a = a[c==1]
if len(a)==0:
    print(0)
    exit()
m = a[-1]+0
while a[0] < m//2:
    i+=1
    a = a[a%a[0] != 0]
    if len(a) == 0:
        break
print(i+len(a))

Submission status: Wrong Answer

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
i = 0
a,c=np.unique(a,return_counts=True)
a = a[c==1]
if len(a)==0:
    print(0)
    exit()
m = a[-1]+0
while a[0] < m//2:
    i+=1
    a = a[a%a[0] != 0]
    if len(a) == 0:
        break
print(i+len(a))

Submission status: Wrong Answer

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
a=np.array(sorted(a))
i = 0
m = a[-1] + 0
while a[0] < m//2:
    try:
        if a[0] != a[1]:
            i+=1
    except:
      i+=1
    a = a[a%a[0] != 0]
    if len(a) == 0:
        break
print(i+len(a))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
n = int(input())
a = list(map(int, input().split()))
dp = [True]*(max(a)+1)
ans=0
b = []

for i in a:
    c = 2
    if i in b:
        continue
    b.append(i)
    while i*c < len(dp):
        dp[i*c] = False
        c+=1
        
for i in a:
    if dp[i]==True:
        ans+=1

print(ans - len([i for i in a if a.count(i)!=1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = list(map(int,input().split()))
dct = {}
for i in lst:
    dct[i] = dct.get(i, 0) + 1
ans = 0
for i in dct:
    ans += (dct[i] == 1)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a= list(map(int,input().split()))
count=set()
for i in range(n):
  for j in range(n):
    if i!=j:
      if a[i]%a[j]:
         count.add(j)
print(len(count))

Submission status: Wrong Answer

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
a,c=np.unique(a,return_counts=True)
a = a[c==1]
if len(a) ==0:
  print(0)
  exit()
m = a[-1]
dp = np.array([True]*len(a))
for i in range(len(a)):
    if dp[i]:
        for j in range(1,m//a[i]):
            if a[i]*(j+1) in a[a>a[i] & dp]:
                dp = np.where(a==a[i]*(j+1), False, dp)
print(sum(dp))

Submission status: Wrong Answer

Solution code:
import numpy as np
_,*a=map(int,open(0).read().split())
a,c=np.unique(a,return_counts=True)
i = - len(c[c>1])
while len(a):
    i+=1
    a = a[a%a[0] != 0]
print(i)

Submission status: Wrong Answer

Solution code:
import numpy as np
_,*a=map(int,open(0).read().split())
a,c=np.unique(a,return_counts=True)
i = len(c[c>1])
while len(a):
    i+=1
    a = a[a%a[0] != 0]
print(i)