Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    n = int(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    As = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    As.sort(reverse=True)
    l = []
    l.append(As.pop())

    for i in range(1,n):
        t = As.pop()
        # seki *= t
        u = len(l)
        flag = False
        for j in range(u):
            if t%l[j] == 0:
                flag=True
        if flag==False:
            l.append(t)
    print(len(l))






main()

Submission status: Wrong Answer

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

a.sort()
b = list(a)

count = 0
rmcnt = 0
for i in range(n):
    flg = True
    for j in range(len(b)):
        if i == (j + rmcnt):
            continue
        if a[i] < b[j]:
            break
        if a[i] % b[j] == 0:
            flg = False
            b.remove(a[i])
            rmcnt += 1
            break
    if flg:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from math import floor

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

m = 10**6
n_map = {}
v_a = []
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
v_a = [k for k, v in n_map.items() if v == 1]

v_a.sort()
vv_a = []
nn_map = {}
for i in v_a:
    if i in nn_map:
        continue
    vv_a.append(i)
    for j in range(floor(m/i)+1):
        nn_map[i*j] = True
print(len(vv_a))

Submission status: Wrong Answer

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

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

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

    if now_num == last_num:
        if flag:
            count -= 1
            flag = False
    else:

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

Submission status: Wrong Answer

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

if a.count(1) == 1 or n == 1:
    print("1")
elif len(set(a)) == 1 or a.count(1) >= 2:
    print("0")
else:
    a.sort()
    c = 0
    for i in range(n-1, 0, -1):
        for j in range(i-1, -1, -1):
            if a[i]/2 in a or a[i]/3 in a or a[i]/4 in a or a[i]/5 in a or a[i]/6 in a or a[i]/7 in a or a[i]/8 in a or a[i]/9 in a or a[i]/10 in a or a[i]/11 in a or a[i]/12 in a or a[i]/13 in a:
                break
            elif a[i]%a[j] == 0:
                break
            if j == 0:
                c += 1
    print(c+1)

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    def is_p(v):
        i = 2
        while i * i <= v:
            if v % i == 0:
                return False
            i += 1
        return True
    primes = []
    for i in range(2, 1001):
        if is_p(i):
            primes.append(i)
    #print(primes)

    A.sort()
    ret = 0
    tmp = set(A)
    tmp2 = []
    for idx, v in enumerate(A):
        ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
        for p in primes:
            if ok or p * p > v:
                break
            if v % p == 0 and (p in tmp or v // p in tmp):
                ok = True
        #print(v, ok)
        if not ok:
            for t in A:
                if t == v:
                    continue
                if ok or t * t > v:
                    break
                if v % t == 0:
                    ok = True
        if ok:
            pass
        else:
            #tmp.add(v)
            #tmp2.append(v)
            ret += 1
    print(ret)
    #tmp = []
    #for idx, v in enumerate(A):
    #    l = len(tmp)
    #    i = 0
    #    ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
    #    while not ok and i < l and tmp[i] * tmp[i] <= v:
    #        if v % tmp[i] == 0:
    #            ok = True
    #            break
    #        i += 1
    #    if ok:
    #        pass
    #    else:
    #        print(v)
    #        ret += 1
    #        tmp.append(v)
    #print(ret)
    #return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  a.sort()
  ans=n
  if a[0]==a[-1]:
    print(0)
    exit()
  
  for i in range(n):
    for j in range(i):
      if not a[i]%a[j]>0:
        ans-=1
        break
      if a[j]>pow(a[i],0.5):
        break
        
  print(ans)
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

    divisors.sort()
    return divisors

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

listA.sort()
map = {}
count = 0
for a in listA:
    l = make_divisors(a)
    flag = 1
    for v in l:
        if v in map:
            flag = 0
            break
    if a in map:
        flag = 0
    if flag:
        map[a] = 1
        count+=1
if count == 1:
    count = 0
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

cnt = 0

for i in num_list:
  for j in num_list:
    if i == j:
      continue
    if i % j != 0:
      
      cnt+=1
      break
if cnt:
  cnt = N - cnt //2
  print(cnt)
else:
  print(cnt)

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


N=int(input())
a=list(map(int, input().split()))
A=list(set(a))
c=len(A)
if len(A) ==1:
    c=0
for i in range(len(A)):
    arr = factorization(A[i])
    # print(arr)
    A_ = A[:i]+A[i+1:]
    # print(A_)
    for j in range(len(arr)):
        for k in range(arr[j][1]):
            # print(pow(arr[j][0],k+1))
            if A_.count(pow(arr[j][0],k+1))>0:
                c-=1
                break
        else:
            continue
        break

print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ans = 0
tmp = np.array([0]*n)
for i in range(n):
    tmp = np.array(a[i]*n)
    tmp = tmp % a
    #print(tmp)
    if n - np.count_nonzero(tmp) == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

A = sorted(A)


maxA = max(A)
if all([a == maxA for a in A]):
    print(0)
else:
    F = [1 for _ in range(N)]
    for i, a in enumerate(A):
    #    print()
    #    print(i, a)
        for j in range(i+1, N):
            if A[j]%a == 0:
                F[j] *= 0
    #        print(A[j], A[j]%a)
    #    print(F)
    print(F.count(1))

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
A.sort(reverse=True)

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

print(ans)

Submission status: Wrong Answer

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

ju = [True for _ in range(N)]

for i in range(N-1):
    n = i+1
    if not ju[n] or not ju[i]:
        continue
    while n < N:
        if A[n]:
            if A[n]%A[i] == 0:
                ju[n] = 0
        n += 1
    if A[i] == A[i+1]:
        ju[i] = 0
print(sum(ju))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
if a.count(a[0])==n: print(0)
else:
    a.sort()
    ans = 1
    div = set()
    div.add(a[0])
    for i in range(1,n):
        fl = 0
        for j in div:
            if a[i]%j==0:
                fl = 1
                break
        if fl==0:
            div.add(a[i])
            ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
import collections

#N = int(input())
#A_list = [int(e) for e in input().split()]

import random
N = 2 * 10**5
A_list = [random.randrange(1,10**6) for _ in range(N+1)]

A_counter = collections.Counter(A_list)

max_A = max(A_list)

A_list.sort(reverse=False)
OK_set = set(A_list)

ans = list()

#入力のうち、小さい方から倍数を生成。その倍数に引っかかったらアウト

for i in range(0,N):
    A = A_list[i]

    if A*2 <= max_A:
        multiple_set = {A*j for j in range(2,1+max_A//A)}
        #print(multiple_set)
        OK_set -= multiple_set

    if A_counter[A] != 1:
        OK_set -= {A}
    
    #print(OK_set)

print(len(OK_set))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

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

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

D = [A[0]]
E = []

for i, x in enumerate(A):
  Flag = True
  
  if i >= 1:

    if is_prime(x):
      D.append(x)
      continue
    
    for j in D:
      if x%j == 0:
        Flag = False
        if x == j:
          E.append(x)
        break
    
    if Flag:
      D.append(x)

print(len(set(D)-set(E)))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
if a[0] == a[-1]:
  print(0)
  exit()

s = set()
ans = 0
s.add(a[0])
for i in a[1:]:
  p = True
  for j in s:
    if i%j == 0:
      ans += 1
      p = False
      break
  if p:
    s.add(j)

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[j-1] == a[j]:
            break
        if a[i]%a[j] == 0:
            break
    else:
        ans += 1

if n > 1:
    if a[n-2] != a[n-1]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    if n==1:
        print(0)
        return

    arr.sort()
    #print(arr)
    ans=0
    for i in range(n):
        flg=0
        if i==0:
            if arr[i]!=arr[i+1]:
                ans+=1
            continue
        h=int(arr[i]**(1/2))+1
        for j in range(0,i):
            if arr[i]%arr[j]==0:
                flg=1
                break
            if arr[j] > h:
                break
        if flg==0:
            ans+=1
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

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

answer = []

for i1,v1 in enumerate(A):
    for i2,v2 in enumerate(A):
        if i1 != i2 and v1 != v2 and v1 % v2 != 0:
            print(v1,"%",v2,"=",v1 % v2)
            answer.append(v1)

print(len(set(answer)))

Submission status: Wrong Answer

Solution code:
N= int(input())
As = list(map(int,input().split()))
As.sort()
import sys
if As[0]==As[-1]:
     print(0)
     sys.exit( )

count=0
for i in range(N):
    flg=True
    for j in range(i):
        if i==j:
            continue
        elif As[i]%As[j]==0:
            flg=False
            break
    if flg:
        count +=1
print(count)

Submission status: Wrong Answer

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

    # divisors.sort()
    return sorted(divisors)

n = int(input())
A = sorted(tuple(map(int, input().split())))
if n ==1:
    print(1)
    exit()
if A[0] == 1:
    if A[1] == 1:
        print(0)
    else:
        print(1)
else:
    ans = []
    tyo = []
    for i in range(n):
        flag = True
        if A[i] in tyo:
            continue
        tmp = make_divisors(A[i])
        for x in tmp:
            if bisect.bisect_left(ans, x)< len(ans):
                if x == ans[bisect.bisect_left(ans,x)]:
                    flag = False
                    break
        if not flag:
            continue


        if i<n-1:
            if A[i+1] == A[i]:
                tyo.append(A[i])
                continue
        ans.append(A[i])
    print(len(ans))

Submission status: Wrong Answer

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

for i in range(N):
    count=0
    for j in range(N):
        if i == j:
            continue
        if A[i]%A[j]==0:
            break
        else: 
            count+=1
            if count==N-1:
                ans +=1
                break

print(ans)

Submission status: Wrong Answer

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

ans = 0
divjl = []
#sAl = sorted(Al)
for i in range(len(Al)):
    if i in divjl:
        continue
    flag = True
    for j in range(len(Al)):
        if i == j:
            continue
        if Al[i] % Al[j] == 0:
            flag = False
            divjl.append(j)
    if flag:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())

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

a.sort()

a = np.array(a)

i = 0

if a[0] != 1:
    while i < len(a):
        b = a / a[i]

        a = a[(b != b.astype(int)) | (b == 1)]

        i += 1

    u, counts = np.unique(a, return_counts=True)

    print(u)

    print(sum(counts == 1))

elif (len(a) > 1) and (a[0] == a[1]):
    print(0)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = [True] * len(A)

dou = [x for x in set(A) if A.count(x) > 1]
A.sort()

for i in range(len(A)):
        if A[i] > 450:
                break
        for j in range(i+1, len(A)):
                if A[j] % A[i] == 0:
                        ans[j] = False


count = 0
for i in ans:
        if i:
                count += 1
print(count -  len(dou))

Submission status: Wrong Answer

Solution code:
import bisect as bc
from collections import defaultdict
from collections import deque
N = int(input())
A = list(map(int,input().split()))
A.sort()
q = [i for i in range(N)]

for i in range(N):
    ai = A[i]
    for j in q:
        if j == i:
            continue
        if A[j] % ai == 0:
            del q[bc.bisect_left(q,j)]

print(len(q))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=set(map(int,input().split()))
if len(a)==1:
	print('0')
	exit()
ans=0
for i,num in enumerate(a):
	count=0
	for j,nuum in enumerate(a):
		if i!=j:
			if num%nuum==0:
				count+=1
				break
	if count==0:
		ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = set(map(int,input().split()))
B = list(A)
B.sort()
count = 0
counter = collections.Counter(B)
for i in range(len(B)):
    if B[i]==1:
        count += 1
        continue
    else:
        check = 0
        for j in range(2,int(B[i]**0.5)+1):
            if B[i]%j==0 and (j in counter or B[i]//j in counter):
                check += 1
                break
        if check==0:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N, *A = map(int, open(0).read().split())

    ctr = Counter(A)
    memo = []
    dp = set()
    ans = 0

    for a in sorted(A):
        if a == 1:
            if ctr[a] == 1:
                ans = 1
            break

        if ctr[a] == 1:
            for v in memo:
                if v > int(a ** 0.5):
                    if a % v != 0:
                        ans += 1
                    elif a % v == 0 and v not in dp and a // v not in dp:
                        ans += 1
                    break
                if a % v == 0:
                    break
            else:
                ans += 1

        memo.append(a)
        dp.add(a)

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A_count = Counter(A)
A_set = list(set(A))
if len(A_set) == 1:
    print(0)
else:
    for i in range(len(A_set)):
        for j in range(len(A_set)):
            if(j == i): continue
            if(A_set[i]%A_set[j] == 0):
                d_num -= A_count[A_set[i]]
                break
    print(d_num)

Submission status: Wrong Answer

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

a.sort()

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
 
N = int(input())
A = Counter(list(map(int, input().split())))
A = [x[0] for x in A.items() if x[1] == 1]
A.sort()
seen = [0]*(1000000+1)
ans = 0
for a in A:
    if seen[a] == 0:
        ans += 1
        x = a
        j = 1
        while x <= 1000000:
            seen[x] = 1
            j += 1
            x = a*j
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from collections import Counter

    N = int(input())
    A = tuple(map(int, input().split()))
    counter_A = Counter(A)

    def divisor(n):
        d = []
        i = 2
        while i*i <= n:
            if n % i == 0:
                d.append(i)
                if i*i != n:
                    d.append(n//i)
            i += 1
        return d
    
    count = 0
    for i in counter_A.keys():
        if counter_A[i] > 1:
            continue
        d = divisor(i)
        flag = True
        for j in d:
            if j in counter_A:
                flag = False
                break
        if flag:
            count += 1
    print(count)


main()

Submission status: Wrong Answer

Solution code:
from numba import jit
@jit(cache=True)
def kkk(al):
    k=0
    for i in range(n):
        f=0
        for j in range(i+1,n):
            if i!=j and al[i]%al[j]==0:
                f=1
                break
        if f==0:
            k=k+1
    return(k)
        
n=int(input())
a=input()
a0=a.split()
al=list()
for i in range(n):
    al.append(int(a0[i]))
al.sort(reverse=True)

k=kkk(al)
if al[n-2]==al[n-1]:
    k=k-1
print(k)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
M=max(a)
num=[0]*M
for x in a:
	num[x-1]+=1
for i in range(M):
	if num[i]>=2:
		num[i]=0
ret=[1]*M
for i in range(M):
	if num[i]:
		j=i+i+1
		while j<M:
			ret[j]=0 
			j+=i+1
	else:
		ret[i]=0
print(ret.count(1))

Submission status: Wrong Answer

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

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

import math
import bisect
from collections import Counter
chou = [i for i in li if li.count(i) >= 2]
se = set(chou)
#print(se)
li = list(set(li))
while len(li)>0:
    ba = li.pop(-1)
    if ba in se:
        continue
    s_ba = math.ceil(math.sqrt(ba))
    index = bisect.bisect_right(li, s_ba)
    tmp_li = li[:index+1]
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = []
mul = set()
for i in range(N):
	flag = 0
	for j in range(len(ans)):
		if A[i] % ans[j] == 0:
			flag = 1
			if A[i] == ans[j]:
				mul.add(A[i])
			break;
	if flag == 0:
		j = 0
		while j < len(ans):
			if ans[j] % A[i] == 0:
				ans.pop(j)
				j -= 1
			j += 1
		ans.append(A[i])
print(len(ans)-len(mul))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

ans = 0

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


# エラトステネスの篩っぽく処理
res = deepcopy(A)
ans_list = [-1 for _ in range(N)]
ind = 0

#print(res)

while -1 in ans_list[ind+1:]:
    #print(ans_list)
    ind = ans_list.index(-1)
    now = res[ind]
    #print("now", ind, now)
    for j in range(ind+1,N):
        if ans_list[j] == -1 and res[j] % now == 0:
            ans_list[j] = 0
    ans_list[ind] = 1

ans = sum(ans_list)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
N = int(input())
#開業されたN個要素を受け付ける
A_list = list(map(int, input().split()))
dup = [x for x in set(A_list) if A_list.count(x) == 1]

#print(dup)

sorted_A_list = sorted(dup)

#print(sorted_A_list)
i = 0
while(i<len(sorted_A_list)):
    j = i+1
    while(j<len(sorted_A_list)):
        if sorted_A_list[j]%sorted_A_list[i] == 0:
            sorted_A_list.pop(j)
        else:
            j=j+1
    i=i+1


print(len(sorted_A_list))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]
A_dict = defaultdict(int)
for a in A:
    A_dict[a] += 1
del_list = []
for key in A_dict.keys():
    if A_dict[key] >= 2:
        del_list.append(key)
for dl in del_list:
    del A_dict[dl]
A = []
for key in A_dict.keys():
    A.append(key)
A = sorted(A)
ans = []
flag = True
for a in A:
    for i in ans:
        if a % i == 0:
            flag = False
            break
    if flag:
        ans.append(a)
    flag = True
print(len(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
p = 0
if 1 in a:
    if a.count(1) >= 2:
        print(0)
        exit(0)
    else:
        print(1)
        exit(0)

for i in range(n):
    if a.count(a[i]) >= 2:
        pass
    else:
        for j in range(n):
            if a[i] % a[j] == 0:
                break
            else:
                pass
            if j == n - 1:
                p += 1

print(p)

Submission status: Wrong Answer

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



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


sa = set(a)
c = 0

for i in range(n):
    f = True
    
    for j in make_divisors(a[i]):
        if j in sa and j != a[i]:
            f = False

    if a[i] == a[i-1]:
        f = False
    if f:
        c += 1


print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
Nmax = 10**6+1

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

prime = [0]*Nmax
for i in range(N):
    if prime[A[i]] == 0:
        prime[A[i]] = 1
    else:
        prime[A[i]] = -1

for a in A:
    if prime[a] == 1:
        for q in range(a*2, Nmax, a):
            prime[q] = 0



print(sum(a for a in prime if a == 1))

Submission status: Wrong Answer

Solution code:
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
  
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
A = LI()
d = collections.deque(A)
ans = 0
for i in range(N):
    c_d = d
    c_d.remove(A[i])
    if A[i] in c_d:
        continue
    else:
        yakusu_list = divisor(A[i])
        warikirenai = True
        for j in yakusu_list:
            if j in c_d:
                warikirenai = False
                break
        if warikirenai == True:
            ans += 1
print(ans-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
if N == 1:
  print(0)
  exit()
List = list(map(int,input().split()))
List.sort()
counter = 0
while len(List) > 0:
  flag = 0
  if len(List)> 1 and List[0] == List[1]:
    flag = 1
  List = [item for item in List if item%List[0]!=0]
  if flag == 0:
    counter += 1
print(counter)

Submission status: Wrong Answer

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

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

count = 0
for i in range(len(a)):
    if len(a) == 1:
        break
    elif is_prime(a[i]):
        count += 1
    else:
        checker = 0
        for j in range(len(a)):
            if i != j and a[i] % a[j] == 0:
                checker = 1
                break
        if checker == 0:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    answer = n
    chk = [0 for _ in range(a[-1] + 1)]
    for aa in a:
        chk[aa] += 1
    for i in range(a[-1] + 1):
        if a[0] == 1 and chk[i]:
            if i == 1:
                answer = 0 if chk[i] else 1
        elif chk[i] == 1:
            for j in range(2 * i, a[-1] + 1, i):
                answer -= chk[j]
                chk[j] = 0
        else:
            answer -= chk[i]
    answer = max(answer, 0)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if n == 1:
    print(0)
else:
    max_arr = max(arr)
    mark = [0 for i in range(max_arr+1)]

    for i in range(n):
        for j in range(arr[i], max_arr+1, arr[i]):
            mark[j] += 1
    # print(mark)
    count = 0
    for i in range(n):
        if mark[arr[i]] == 1:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
ans=0
for i in range(N):
    B=A.copy()
    t=B[i]
    del B[i:]
    arr=[]
    if all(list(map(lambda x: t%x!=0, B))):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
def is_prime(n,A):
    if n == 1:
        return False
    for i in A:
        if i!=n and n % i == 0:
            return False
    return True
a=0
B=[x for x in set(A) if A.count(x) == 1]
for i in B:
    if is_prime(i,B):
        a+=1
print(a)

Submission status: Wrong Answer

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

num = int(input())
a = list(map(int, input().split()))
b = 0
for i in a:
  for f in make_divisors(i)[:-1]:
    if f in a:
      b += 1
      break
print(num - b)

Submission status: Wrong Answer

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

b = sorted(a, reverse = True)
print(b)
k = 0
for i in range(n-1):
    if all([b[i]%b[j] != 0 for j in range(i+1, n)]):
        k = k+1
if b[n-1] != b[n-2]:
    k = k+1
print(k)

Submission status: Wrong Answer

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

A = list(set(A))
A.sort(reverse=True)

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

if sum(A) == N * A[0]:
    print(0)

else:
    dammy=[]
    for i in range(N):
        #素因数分解。
        pf={}
        m=A[i]    #341555136
        for i in range(2,int(m**0.5)+1):
            while m%i==0:
                pf[i]=pf.get(i,0)+1
                m//=i
        if m>1:pf[m]=1
        pfkey=list(pf.keys())
        #print(pfkey)
        for iii in pfkey:
            if iii not in dammy:
                #print('iii:',iii)
                dammy.append(iii)
            else:
                break
        #{136841: 1, 2: 6, 3: 1, 13: 1}
    #print('dammy:',dammy)
    #dammy=list(itertools.chain.from_iterable(dammy))

    #print(set(dammy))
    print(len(set(dammy)))