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()))
a.sort()
 
dp = [True] * n
cnt = 0
for i in range(n):
    if dp[i]:
        for j in range(n):
            if i==j:
                continue

            if dp[j]:
                if a[j]%a[i]==0:
                    cnt += 1
                    dp[j] = False

ans = n - cnt
print(ans)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    def gcd(a, b):
        while b: a, b = b, a % b
        return a
    def isPrimeMR(n):
        d = n - 1
        d = d // (d & -d)
        L = [2]
        for a in L:
            t = d
            y = pow(a, t, n)
            if y == 1: continue
            while y != n - 1:
                y = (y * y) % n
                if y == 1 or t == n - 1: return 0
                t <<= 1
        return 1
    def findFactorRho(n):
        m = 1 << n.bit_length() // 8
        for c in range(1, 99):
            f = lambda x: (x * x + c) % n
            y, r, q, g = 2, 1, 1, 1
            while g == 1:
                x = y
                for i in range(r):
                    y = f(y)
                k = 0
                while k < r and g == 1:
                    ys = y
                    for i in range(min(m, r - k)):
                        y = f(y)
                        q = q * abs(x - y) % n
                    g = gcd(q, n)
                    k += m
                r <<= 1
            if g == n:
                g = 1
                while g == 1:
                    ys = f(ys)
                    g = gcd(abs(x - ys), n)
            if g < n:
                if isPrimeMR(g): return g
                elif isPrimeMR(n // g): return n // g
                return findFactorRho(g)
    def primeFactor(n):
        i = 2
        ret = {}
        rhoFlg = 0
        while i*i <= n:
            k = 0
            while n % i == 0:
                n //= i
                k += 1
            if k: ret[i] = k
            i += 1 + i % 2
            if i == 101 and n >= 2 ** 20:
                while n > 1:
                    if isPrimeMR(n):
                        ret[n], n = 1, 1
                    else:
                        rhoFlg = 1
                        j = findFactorRho(n)
                        k = 0
                        while n % j == 0:
                            n //= j
                            k += 1
                        ret[j] = k

        if n > 1: ret[n] = 1
        if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
        return ret

    #[(p1,n1),(p2,n2),...]の形で返す
    def primeFactor2(n):
        i = 2
        ret = {}
        rhoFlg = 0
        while i*i <= n:
            k = 0
            while n % i == 0:
                n //= i
                k += 1
            if k: ret[i] = k
            i += 1 + i % 2
            if i == 101 and n >= 2 ** 20:
                while n > 1:
                    if isPrimeMR(n):
                        ret[n], n = 1, 1
                    else:
                        rhoFlg = 1
                        j = findFactorRho(n)
                        k = 0
                        while n % j == 0:
                            n //= j
                            k += 1
                        ret[j] = k

        if n > 1: ret[n] = 1
        if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
        return ret

    #約数列挙
    #10^6以下で約数の数が最大なのは720720の時(240個しかない！)
    def divisors(N):
        pf = primeFactor(N)
        ret = [1]
        for p in pf:
            ret_prev = ret
            ret = []
            for i in range(pf[p]+1):
                for r in ret_prev:
                    ret.append(r * (p ** i))
        return sorted(ret)
        
        
    
    mod=10**9+7
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    for i in range(N):
        dd[A[i]]+=1
        
    A.sort()
    
    ans=0
    for i in range(N):
        if dd[A[i]]>=2:
            pass
        else:
            L=divisors(A[i])
            flag=1
            for v in L[1:-1]:
                if dd[v]:
                    flag=0
                    break
            if flag:
                ans+=1
                
    print(ans)
                    
        
        

                
    
    


main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
ml=max(l)
m=[0]*(ml+1)
for i in l:
    m[i]+=1
for i in range(ml+1):
    if m[i]>=1:
        for j in range(i,ml+1,i):
            if m[j]>0:
                m[j]=0
for i in range(ml+1):
    if m[i]>=2:
        m[i]=0
print(sum(m))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]  
A.sort()
i = 0
while True:
  if i>=len(A):
    print(len(A))
    break
  else:
    a = A[i]
    b = len(A)
    j = i+1
    check_allsame = len(A)-j
    while j<len(A):
      if A[j]==a:
        del A[j]
        check_allsame -= 1
      elif A[j]%a==0:
        del A[j]
      else:
        j+=1
    if i!=b-1 and check_allsame == 0:
      del A[-1]
    i+=1

Submission status: Wrong Answer

Solution code:
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    dp = [True for i in range(10**6+10)]
    ans = 0
    for i in a:
        if dp[i]:
            ans += 1
        for j in range(1, 10**6+10):
            if i*j > 10**6:
                break
            dp[i*j] = False
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
mt = list(map(int, input().split()))
s=set(mt)
s=list(s)
k=len(s)
g=Counter(mt)
ans=0
for i in range(k):
    for j in range(k):
        if(i!=j):
            if(s[i]%s[j]==0):
                break
    else:
        if(k>1):
            ans+=g[s[i]]
print(ans)

Submission status: Wrong Answer

Solution code:
def abc170_d():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    B = []
    for i in range(N):
        flag = True
        for b in B:
            if A[i] % b == 0:
                flag = False
                break
        if flag:
            if i < N-1 and A[i] != A[i+1]:
                B.append(A[i])
            elif i == N-1 and A[i] != A[i-1]:
                B.append(A[i])
    ans = len(B)
    print(ans)

abc170_d()

Submission status: Wrong Answer

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

if N == 1:
  print(1)
  exit(0)
#
A.sort()
A.append(0) 

b = []
ans = 0
i = 0
while i < N:
  c = A[i]
  for j in b:
    if c % j == 0:
      break
  else:
    b.append(c)
    if c == A[i+1]:
      while c == A[i]:
        i += 1
    else:
      ans += 1
  i += 1
#          
print(ans)

Submission status: Wrong Answer

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

num = max(l)+1
rcd = [0 for _ in range(num)]

l = set(l)
for x in l:
    for y in range(2*x, num, x):
        if x != rcd[y]:
            rcd[y] = 1

ans = 0
for k in l:
    if rcd[k] == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

num = max(l)+1
rcd = [0 for _ in range(num)]

l = set(l)
for x in l:
    for y in range(x, num, x):
        rcd[y] += 1

ans = 0
for k in l:
    if rcd[k] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

input = []
for l in sys.stdin:
  input.append(l)

total = input.pop(0)

arr = np.asarray(input[0].split(' '), dtype = 'uint16')
arr = np.sort(arr)[::-1]

cnt = 0
for i1, v1 in np.ndenumerate(arr):
  found = False
  for i2, v2 in np.ndenumerate(arr):
    if i1 == i2:
      continue
    if v1 % v2 == 0:
      found = True
      break
  if found == False:
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque,Counter

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

memo = [0] * (10**6+10)
cnt = Counter(A)
for k,v in cnt.items():
    if memo[k] > 1:
        continue
    for j in range(k,10**6+1,k):
        memo[j] += v 

ans = 0
for num in cnt:
    ans += (memo[num] == 0)

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) #小さい順にソートしておく
s=set()
cnt=collections.Counter(arr) #各要素の個数を事前に数えておく
print(cnt)

for i in range(n):
 if arr[i] in s: #Aiがすでに列挙した数に含まれていれば処理を行わない
   continue
 if cnt[arr[i]]>=2: #Aiが2個以上含まれているとき、Ai自身を列挙した数に加える
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1): #Ai自身を除くAiの倍数を列挙する
   s.add(arr[i]*j)
ans=0
for i in range(n): #列挙した数に含まれないAiの個数を数える
 if arr[i] in s:
   continue
 ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections as col
import numpy as np
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
C=col.Counter(A)
duplicated ={k for k,v in C.items() if v>1}
MAX=A[-1]
List=np.ones(MAX+1,np.int8)
ans=0
for i in A:
  if List[i]==0:
    continue
  if i not in duplicated:
    ans+=1
    List[i+i::i]=0
print(ans)

Submission status: Wrong Answer

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

ans = 0

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]

for i in li:
    s = make_divisors(i)
    
    for j in s:
        if j in li:
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(int,input().split()))
p = [ x for x in set(p) if p.count(x) == 1]
p.sort()
tp = [ 1 for _ in range(len(p))]
for i in range(len(p)):
    if tp[i]:
        for j in range(i+1,len(p)):
            if tp[j]:
                if p[j] % p[i] == 0:
                    tp[j] = 0
print(sum(tp))

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(int,input().split()))
p = [ x for x in set(p) if p.count(x) == 1]
p.sort()
tp = [ 1 for _ in range(len(p))]
for i in range(len(p)):
    if tp[i]:
        for j in range(i+1,len(p)):
            if p[j]:
                if p[j] % p[i] == 0:
                    tp[j] = 0
print(sum(tp))

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(int,input().split()))
p = [ x for x in set(p) if p.count(x) == 1]
p.sort()
tp = [ 1 for _ in range(len(p))]
for i in range(len(p)):
    if tp[i]:
        for j in range(i+1,len(p)):
            if p[j] % p[i] == 0 and p[j]:
                tp[j] = 0
print(sum(tp))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
count = 0
for i in range(N - 1):
    found = False
    if A[i] == A[i + 1]:
        continue

    for j in range(N - 1, i, -1):
        # print(A[i], A[j])
        if A[i] % A[j] == 0:
            found = True
            # print('Found')
            break
        if A[i] < 2 * A[j]:
            break

    if not found:
        # print('Not Found')
        count += 1

if N == 1 or A[0] != A[1]:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
count = 0
for i in range(N - 1):
    found = False
    if A[i] == A[i + 1]:
        continue

    for j in range(N - 1, i, -1):
        # print(A[i], A[j])
        if A[i] % A[j] == 0:
            found = True
            # print('Found')
            break
        if A[i] < 2 * A[j]:
            break

    if not found:
        # print('Not Found')
        count += 1

if N > 1 and A[0] != A[1]:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
count = 0

for i in range(N - 1):
    found = False

    for j in range(N - 1, i, -1):
        if A[i] % A[j] == 0:
            found = True

    if not found:
        count += 1

if A[N - 1] != A[N - 2]:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    a_max = max(a)
    is_divable = [True]*(a_max+1)
    ans = 0
    is_divable[0],is_divable[1] = False,False
    for el in a:
        if is_divable[el]:
            ans +=1
            k = 2
            while k*el <= a_max:
                is_divable[k*el] = False
                k+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()

B=[0]*( max(A)+1 )

for i in A:
  j=2
  if(B[i]==0):
    while( j*i <= max(A) ):
      B[j*i]=1
      j += 1

count=0
for i in A:
  if(B[i]==0):
    count +=1


print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
lst = list(map(int,input().split()))
lst.sort(reverse = True)
d = deque(lst)
cnt = 0

while d:
    ku = d.popleft()
    if all( ku % i != 0 for i in d):
      cnt += 1
    
print(cnt)

Submission status: Wrong Answer

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

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

else:
    for i in range(len(A)):
        value=A.pop(0)
        #一番はじめの数をpopして取り出す
        if all([value % j !=0 for j in A]):
            #これで自分自身はpopで取り除いているので、他のものにかんしてのみみれる
            result.append(value)
        A.append(value)
        #後ろに加えて元どおりにする
    print(len(result))

Submission status: Wrong Answer

Solution code:
lst=[]
c=0
flag=0
n = int(input())
str = input()
lst = str.split(' ')
#for i in range(0,n):
#  lst[i] = int(lst[i])
lst.sort()
#print(lst)
for i in range(0,n):
  flag=0
  if i+1<n:
    if int(lst[i+1])==int(lst[i]):
      flag=1
  for j in range(0,i):
    
    if  int(lst[i])%int(lst[j])==0:
      flag=1
      j=i
  if flag==0:
    c = c+1
print(c)

Submission status: Wrong Answer

Solution code:
lst=[]
c=0
flag=0
n = int(input())
str = input()
lst = str.split(' ')
#for i in range(0,n):
#  lst[i] = int(lst[i])
lst.sort()
#print(lst)
for i in range(0,n):
  flag=0
  for j in range(0,i):
    
    if  int(lst[i])%int(lst[j])==0:
      flag=1
      j=i
  if flag==0:
    c = c+1
print(c)

Submission status: Wrong Answer

Solution code:
lst=[]
c=0
flag=0
n = int(input())
str = input()
lst = str.split(' ')
for i in range(0,n):
  lst[i] = int(lst[i])
lst.sort()

for i in range(0,n):
  flag=0
  for j in range(0,i):
    
    if  lst[i]%lst[j]==0:
      flag=1
      j=i
  if flag==0:
    c = c+1
print(c)

Submission status: Wrong Answer

Solution code:
lst=[]
c=0
flag=0
n = int(input())
str = input()
lst = str.split(' ')
for i in range(0,n):
  lst[i] = int(lst[i])
lst.sort()
print(lst)
for i in range(0,n):
  flag=0
  for j in range(0,i):
    
    if  lst[i]%lst[j]==0:
      flag=1
      j=i
  if flag==0:
    c = c+1
print(c)

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 = []
for a in map(int,input().split()):
    A.append(a)
A.sort()
c = 0
lenA = len(A)
for i in range(lenA):
    Ai = A[i]
    if i < lenA - 1:
        if Ai == A[i + 1]:
            continue
    flg = False
    l = A[:i]
    lenl = len(l)
    lastj = i // 2
    j = lastj
    while lenl > 0:
        lj = l[j]
        q,m = divmod(Ai,lj)
        if m == 0:
            flg = True
            break
        if q == 1:
            del l[j:]
            lenl = len(l)
            j = lastj - 1
            lastj = j - 1
        else:
            del l[j]
            lenl = len(l)
            lastj = j
            j = lenl - (lenl - j) // 2
        if j >= lenl:
            j = lenl - 1
    if not flg:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import math
import bisect

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

a.sort()

b = [0 for i in range(a[n-1]+1)]

count = 0
temp2 = -1
temp3 = -2
for i in a:
    if(b[i] == 0):
        count += 1
        temp = i
        while(temp <= a[n-1]):
            b[temp] = 1
            temp += i
    if(i == temp2 and temp2 != temp3):
        count -= 1
    temp3 = temp2
    temp2 = i



print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
n = inp()
a = inpl()
for x in a:
    make_divisors(x)

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 = []
for a in map(int,input().split()):
    A.append(a)
A.sort()
c = 0
for i in range(len(A)):
    Ai = A[i]
    Ad = make_divisors(Ai)
    sAd = set(Ad)
    l = A[:i]
    sl = set(l)
    s = sl - sAd
    if len(sl) == len(s):
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = inpl()
p = []
res = 0
a.sort()
for i,x in enumerate(a):
    for y in p:
        if x%y == 0:
            break
    else:
        res += 1
        p.append(x)
print(res)

Submission status: Wrong Answer

Solution code:

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

cnt = 0
for i, a in enumerate(A):
    if a <= _max // 2:
        k = 2
        x = 0
        while(1):
            x = a * k
            if x in A:
                A.remove(x)

            if x >= _max:
                break

            k = k + 1
    if i >= len(A) // 2:
        break

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

Submission status: Wrong Answer

Solution code:

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

cnt = 0
for i, a in enumerate(A):
    if a <= _max // 2:
        k = 2
        x = 0
        while(1):
            x = a * k
            if x in A:
                A.remove(x)

            if x >= _max:
                break

            k = k + 1

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

Submission status: Wrong Answer

Solution code:

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

cnt = 0
for i, a in enumerate(A):
    k = 2
    x = 0
    while(1):
        x = a * k
        if x in A:
            A.remove(x)

        if x >= _max:
            break

        k = k + 1
    if a >= _max//2:
        break

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

Submission status: Wrong Answer

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

class Factorization:	
	def __init__(self):
		# privateなインスタンス変数を作成
		self.__factors = dict()
		self.__n = 0
	
	
	def get_factors(self, n):
		# [summary] 素因数分解した結果を、辞書([素因数, 指数]...)で返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			# 2より小さい数の場合、素因数分解できない
			return { n:1 }
		else:
			self.__factorization()
			
			return self.__factors
	
	
	def get_divisors(self, n):
		# [summary] 約数をリストに列挙
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return [1]
		else:
			self.__factorization()
			divisors = [1]
			
			for k, v in self.__factors.items():
				import copy
				copy_ = copy.deepcopy(divisors)
								
				for i in range(1, v + 1):
					for c in copy_:
						divisors.append(c * (k ** i))
			
			return divisors

				
	def count_divisors(self, n):
		# [summary] 約数の個数を返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return 1
		else:
			self.__factorization()
			count = 1
			
			for v in self.__factors.values():
				count *= v + 1
			
			return count
	

	def	__factorization(self):
		# [summary]素因数分解した結果を、インスタンス変数に格納
		
		# 2,3,5で、割れなくなるまで割り続ける
		# (末尾に2,3,5のつく数は素数でないことが明白なので
		# 後続の処理で素数のリストに入れないように、先に処理する)
		self.__divide_with(2)
		self.__divide_with(3)
		self.__divide_with(5)
			
		# 平方根以下の素数で総当たりで試し割りする
		# (実際は、素数らしき数)
		import math
		sqrt_ = math.floor(math.sqrt(self.__n))
			
		primes = [7, 11, 13, 17, 19, 23, 29, 31]
		i = 0
		is_break = False
			
		while self.__n > 1:
			for p in primes:
				if p + i <= sqrt_:
					self.__divide_with(p + i)
				else:
					# 試し割りする数が平方根を超えたら、ループを抜ける
					is_break = True
						
					# 1が素因数に追加されることを防止
					if self.__n > 1:
						self.__factors.setdefault(self.__n, 1)
				
			if is_break:
				break
			else:
				i += 30
	
	
	def __divide_with(self, d):
		count = 0
		
		while self.__n % d == 0:
			self.__n //= d
			count += 1
		
		if count > 0:
			self.__factors.setdefault(d, count)


# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

ans = 0
appeared = set()
lib = Factorization()

for k, v in sorted(dic.items(), key=lambda x:x[0]):
	is_exist = False

	if v == 1:
		divisors = lib.get_divisors(k)
		
		for d in divisors:
			if d in appeared:
				is_exist = True
				break

		if is_exist == False:
			ans += 1

	if is_exist:
		appeared.add(k)

print(ans)

Submission status: Wrong Answer

Solution code:
num = int(input())
arr = input().split()

arr2 = list(set(arr))
num2 = len(arr2)
counter = 0

for i in range(num2):
  a = int(arr2[i])
  
  for j in range(num2):
    b = int(arr2[j])

    if a != b and a % b == 0:
      break
      
    if j == num2-1:
      counter += 1;

print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
as_ = list(map(int, input().split()))
as_ = sorted(list(set(as_)))

num = 0
if 1 < len(as_):
    for i in range(len(as_)):
        for j in range(i):
            if as_[i] % as_[j] == 0:
                break
        else:
            num += 1
print(num)

Submission status: Wrong Answer

Solution code:
n = int(input()) #このnは使わない
*A, = map(int, input().split())
maxA = max(A)
print(A)
print(maxA)

# 連想配列 [key : value]

# C[a : count]
C = {a : 0 for a in A}
#要素を見つけるたびに1増える
#重複がある場合はC[a] >= 2になる
#例えば5が4つ見つかると C[5] = 4
for a in A:
    C[a] += 1
print(C)


D = {a : 0 for a in A}
#Aの数値をkeyとして扱う
for a in A:
    if C[a] > 0:
        t = 2
        while a*t <=maxA:
            #aの倍数にフラグを立てる
            # D[2]が存在する場合, D[4]やD[6]は約数が存在することになる
            D[a*t] = 1
            t += 1
print(D)

ans = 0
for a in A:
    # 重複がないもので,約数が存在しないものが答え
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#abc170
#abc170
n = int(input())
ln = list(map(int, input().split()))
ln = sorted(list(set(ln)), reverse = True)
#print(ln)
counter = 0
for i in range(len(ln)):
    for j in range(i + 1, len(ln)):
        if ln[i] % ln[j] == 0:
            counter += 1
            #print(i,j)
            break
if len(ln) == 1:
  print(0)
else:
  print(len(ln) - counter)

Submission status: Wrong Answer

Solution code:
#abc170
n = int(input())
ln = list(map(int, input().split()))
ln = list(set(ln))
#print(ln)
counter = []
for i in range(len(ln)):
    
    for j in range(i +1, len(ln)):
        if ln[j] % ln[i] == 0:
            counter.append(j)
            #print(i,j)
            
print(len(ln) - len(set(counter) ))

Submission status: Wrong Answer

Solution code:
#abc170
n = int(input())
ln = list(map(int, input().split()))
ln = list(set(ln))
#print(ln)
counter = []
for i in range(len(ln)):
    
    for j in range(i +1, len(ln)):
        if ln[j] % ln[i] == 0:
            counter.append(j)
            #print(i,j)
            
print(len(set(counter)))

Submission status: Wrong Answer

Solution code:
#abc170
n = int(input())
ln = list(map(int, input().split()))
ln = list(set(ln))
#print(ln)
counter = 0
for i in range(len(ln)):
    
    for j in range(i +1, len(ln)):
        if ln[j] % ln[i] == 0:
            counter += 1
            #print(i,j)
            
print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
aL = sorted(list(map(int, input().split(" "))))
# aL = sorted(list(set(aLP)))

dp = [False for _ in range(1000001)]

d = {}
for a in aL:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

ans = 0
for a in aL:
    if dp[a] or d[a] > 1:
        continue
    ans += 1

    c = 1
    while a * c <= 1000000:
        dp[a * c] = True
        c += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
aLP = list(map(int, input().split(" ")))
aL = sorted(list(set(aLP)))

dp = [False for _ in range(1000001)]

ans = 0
for a in aL:
    if not dp[a]:
        ans += 1
    else:
        continue
    c = 1
    while a * c <= 1000000:
        dp[a * c] = True
        c += 1

print(ans - (len(aLP) - len(aL)))

Submission status: Wrong Answer

Solution code:
n = int(input())
aL = list(map(int, input().split(" ")))
aL2 = sorted(list(set(aL)))

dp = [False for _ in range(1000001)]

ans = 0
for a in aL:
    if not dp[a]:
        ans += 1
    else:
        continue
    c = 1
    while a * c <= 1000000:
        dp[a * c] = True
        c += 1

print(ans - (len(aL) - len(aL2)))

Submission status: Wrong Answer

Solution code:
n = int(input())
aL = sorted(list(set(list(map(int, input().split(" "))))))

dp = [False for _ in range(1000001)]

if len(aL) == 1 and n != 1:
    print(0)
    exit()

ans = 0
for a in aL:
    if not dp[a]:
        ans += 1
    else:
        continue
    c = 1
    while a * c <= 1000000:
        dp[a * c] = True
        c += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
check=[0 for i in range(10**6+1)]
for i in a:
    for j in range(i*2, 10**6+1,i):
        check[j]+=2
ans=0
for g in a:
    if check[g]==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

multiple = [False] * 1_000_001
once = set()
twice = set()
count = 0

for a in sorted(map(int, input().split())):
  if a in once:
    if a in twice:
      continue
    else:
      count -= 1
      twice.add(a)
  elif multiple[a]:
    continue
  else:
    count += 1
    once.add(a)
print(count)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()])
A = np.sort(A)
A_uniq, A_index, A_count = np.unique(A, return_index=True, return_counts=True)
A_bool = np.zeros((len(A_uniq)))

if(len(A_uniq)==1):
  print(0)
  sys.exit()
else:
  n = 1
  for i in range(1,len(A_uniq)):
    l = 0
    for j in range(i):
      if((A_uniq[i] % A_uniq[j]) == 0):
        break
      l += 1
    if((l == i) and (A_count[i]==1)):
      n += 1
      A_bool[i] = 1
  print(n)

Submission status: Wrong Answer

Solution code:
from sys import stdin
 
N = int(stdin.readline().strip())
A = sorted([int(x) for x in stdin.readline().strip().split(" ")])
A = list(set(A))
sum_num = 0

for i in range(len(A)):
    tmp = [A[i]] * N
    tmp = [x % y for (x, y) in zip(tmp, A)]
    tmp[i] = 1
    if 0 not in tmp:
        sum_num += 1

print(sum_num)

Submission status: Wrong Answer

Solution code:
from sys import stdin
 
N = int(stdin.readline().strip())
A = [int(x) for x in stdin.readline().strip().split(" ")]
A = list(set(A))
sum_num = 0

for i in range(len(A)):
    tmp = [A[i]] * N
    tmp = [x % y for (x, y) in zip(tmp, A)]
    tmp[i] = 1
    if 0 not in tmp:
        sum_num += 1

print(sum_num)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
list_input = list(map(int, sys.stdin.readline().split()))

list_input.sort()
list_input = list(set(list_input))
if len(list_input) == 1:
    print(0)
    exit()

max_num = list_input[-1]

list_false = []
for i in list_input:
    for j in list_input:
        if i == j:
            continue
        elif i % j == 0:
            list_false.append(i)
            break

print(n-len(list_false))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
from collections import defaultdict
dict_A = defaultdict(int)
for a in A:
  dict_A[a] += 1
I = []
for key in dict_A.keys():
  if dict_A[key] >= 2:
    I.append(key)
A = sorted(list(set(A)))
from collections import deque
Q = deque(A)
ans = 0
while Q:
  q = Q.popleft()
  if q in I:
    pass
  else:
  	ans += 1
  temp_Q = deque([])
  while Q:
    r = Q.popleft()
    if r%q!=0:
      temp_Q.append(r)
  Q = temp_Q
print(ans) if N!=1 else print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
from collections import defaultdict
dict_A = defaultdict(int)
for a in A:
  dict_A[a] += 1
A = []
for key in dict_A.keys():
  if dict_A[key] == 1:
    A.append(key)
A = sorted(A)
from collections import deque
Q = deque(A)
ans = 0
while Q:
  q = Q.popleft()
  ans += 1
  temp_Q = deque([])
  while Q:
    r = Q.popleft()
    if r%q!=0:
      temp_Q.append(r)
  Q = temp_Q
print(ans) if N!=1 else print(0)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if 2*i > len(dp)-1:
            pass
        elif dp[2*i] == 0:
            pass
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)