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:
from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

n, *a = map(int, open(0).read().split())
b = set(a)
P = Osa_k(max(b))
cnt = n == 1
for i, j in Counter(a).items():
    cnt += j == 1 and all(d not in b for d in P.div(i) if d != 1)
print(cnt)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res

    def div(self, n):
        factors = self.__call__(n)
        res = {1} # {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

n, *a = map(int, open(0).read().split())
b = set(a)
P = Osa_k(max(b))
cnt = 0
for i, j in Counter(a).items():
    if j > 1:
        continue
    cnt += all(d not in b for d in P.div(i))
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = {2 : n_twoes}
        n >>= n_twoes
        while n > 1:
            p = min_factor[n]
            res[p] = res.get(p, 0) + 1
            n //= p
        return res.values()

def f(K):
    res = 1
    for i in K:
        res *= i + 1
    return res

P = Osa_k(10**7)
print(sum(i * f(P(i)) for i in range(1, int(input()) + 1)))

Submission status: Wrong Answer

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

M = (A[-1])**(1/2)

table = [1 for i in range(N)]

for i, a in enumerate(A):
    if a >= M:
        break
    elif table[i]:
        for j, b in enumerate(A[i+1:]):
            if not(b % a):
                table[j+i+1] = 0

    pre = a

pre = 0
for i, a in enumerate(A):
    if a == pre:
        table[i] = 0
        table[i-1] = 0
    pre = a

print(sum(table))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, *A = map(int, open(0).read().split())
A.sort()
c, s = Counter(A), set()
M = max(A) + 1
ans = 0
for a in A:
    if a in s:
        continue
    ans += c[a] == 1
    for i in range(a * a, M, a):
        s.add(i)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from operator import mul
from functools import reduce

class Osa_k:
    def __init__(self, n_max):

        
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

n, *a = map(int, open(0).read().split())
O = Osa_k(max(a))
c = [None] * n
a.sort()
cnt = 0
for i in range(n):
  s = O.d(a[i])
  c[i] = s
  cnt += sum(c[j] < s for j in range(i))
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

aMax = a[-1]
l = len(a)
count = 0
k = 0
kSet = set()

for i in range(n):
    value = a[i]
    if not(value in kSet):
        if a[i-1] == value:
            count -= 1
            kSet.add(value)
            continue
        count += 1
        j = 2
        k = 0
        while k < aMax:
            k = a[i] * j
            kSet.add(k)
            j += 1
    #if value ** 2 > aMax:
    #    break

print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = input()

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

#print(N)
#print(x)


def hantei(list_1):
    list_length = len(list_1)
    return [(list_1[a], list_1[b]) for a in range(list_length) for b in range(list_length) if a < b if list_1[a] != list_1[b] and list_1[a] % list_1[b] != 0]

def hantei_2(list_1):
    count = 0
    a = 0
    while a <= len(list_1) - 1:
        b = a + 1
        while b <= len(list_1) - 1:
            if list_1[a] % list_1[b] == 0:
                break
            elif b == len(list_1) -1:
                count += 1
                break
            b += 1
        a += 1
    return count

print(hantei_2(x))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

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

array = [0 for i in range((10 ** 6)+1)]
for v in a:
  array[v] += 1
  
if array[1] != 0:
  print(0)
  sys.exit()
  
for i in range(1, len(array)):
  if array[i] == 0:
    continue
    
  for j in range(i*2, len(array), i):
    array[j] = 0
    
count = 0
for v in array:
  if v == 1:
    count += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    n = I()
    a = set(IL())
    lst = []
    ans = len(a)-(n-len(a))
    for rep in a:
        st = set()
        for i in range(2,rep+1):
            if rep<i*i:
                break
            if rep%i==0:
                st.add(i)
                st.add(rep//i)
        st.add(rep)
        lst.append(st)

    for rep in lst:
        if len(rep.intersection(a))!=1:
            ans -= 1

    print(max(ans,0))
    exit()

Submission status: Wrong Answer

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

cnt = 0
for i in range(len(a)):
    for j in range(len(a)):
        if i == j:
            continue

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

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
dp = [0]*(10**6+1)
for i in range(len(A)):
    dp[A[i]] += 1
def p_factor(x):
    L = []
    for i in range(1,int(x**0.5)+1):
        cur = x//i
        if x%i == 0:
            L.append(i)
            if cur != x & cur != i:
                L.append(cur)
    return L
ans = 0
for i in range(len(A)):
    if dp[A[i]] > 1:
        ans += 1
    else:
        if A[i] != 1:
            T = p_factor(A[i])
            for j in range(len(T)):
                if dp[T[j]] >= 1:
                    ans += 1
                    break
        else:
            None
print(len(A)-ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
dp = [0]*(10**6+1)
for i in range(len(A)):
    dp[A[i]] += 1
def p_factor(x):
    L = []
    for i in range(1,int(x**0.5)+1):
        if x%i == 0:
            L.append(i)
            if x//i != x:
                L.append(x//i)
    return L
ans = 0
for i in range(len(A)):
    T = p_factor(A[i])
    if dp[A[i]] > 1:
        ans += 1
    else:
        for j in range(len(T)):
            if dp[T[j]] >= 1:
                ans += 1
                break
print(len(A)-ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
dp = [0]*(10**6+1)
for i in range(len(A)):
    dp[A[i]] += 1
def p_factor(x):
    L = []
    for i in range(1,int(x**0.5)+1):
        if x%i == 0:
            L.append(i)
            if x//i != x:
                L.append(x//i)
    return L
ans = 0
for i in range(len(A)):
    T = p_factor(A[i])
    if dp[A[i]] > 1:
        ans += 1
    else:
        for j in range(len(T)):
            if dp[T[j]] >= 1:
                ans += 1
                break
print(len(A)-ans)

Submission status: Wrong Answer

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

dp = [1]*a[-1]

a_max = a[-1]
for i in set(a):
    j = 2
    while i*j <= a_max:
        dp[i*j-1] = 0
        j += 1

ans = 0
for i in range(n):
    if i == 0:
        if dp[a[i]-1]:
            ans += 1
    elif dp[a[i]-1] and a[i-1] != a[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

dp = [1]*a[-1]

for i in set(a):
    j = 2
    while i*j <= a[-1]:
        dp[i*j-1] = 0
        j += 1

ans = 0
for i in range(n):
    if dp[a[i]-1] and a[i-1] != a[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

dp = [1]*a[-1]

for i in range(1, a[-1]):
    if i in a:
        j = 2
        while i*j <= a[-1]:
            dp[i*j-1] = 0
            j += 1

ans = 0
for i in range(n):
    if dp[a[i]-1] and a[i-1] != a[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

dp = [1]*a[-1]

if a[0] == a[-1]:
    print(0)
    exit()

for i in range(1, a[-1]):
    if i in a:
        j = 2
        while i*j <= a[-1]:
            dp[i*j-1] = 0
            j += 1

ans = 0
for k in a:
    ans += dp[k-1]
print(ans)

Submission status: Wrong Answer

Solution code:

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


lim = 10 ** 6 + 10
ok = [True] * (lim + 1)
ans = 0
for n in sorted(X):
    if ok[n]:
        ans += 1
        for j in range(n, lim + 1, n):
            ok[j] = False

print(ans)

Submission status: Wrong Answer

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

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

for i in range(n):
    cnt[a[i]] += 1

a_uniq = []

for i in range(10 ** 6 + 1):
    if cnt[i] == 1:
        a_uniq.append(i)

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

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

ans = 0

for i in a_uniq:
    if cnt[i] == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

nums.sort()

if n == 1:
    print(1)
    exit()

ans_list = [nums[0]]

for i in range(n):
    valid = True
    for j in range(len(ans_list)):
        if nums[i] % ans_list[j] == 0:
            # 割り切れた
            valid = False
            break
        # if nums[i] < ans_list[j] * 2:
        #     break
    if valid:
        ans_list.append(nums[i])
    
# nums[0] = num[1] の場合は0を減らす：
ans = len(ans_list)
if nums[0] == nums[1] :
    ans -= 1

print(ans)
# print(ans_list)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]+sorted(list(map(int,input().split())))+[0]
m=max(a)+1
s=[1]*m
c=0
for i in range(1,n+1):
    if s[a[i]]:
        if a[i-1]!=a[i] and a[i+1]!=a[i]:
            c+=1
        for j in range(i,m,i):
            s[j]=0
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
m=max(a)+1
s=[1]*m
c=0
for i in a:
    if s[i]:
        c+=1
        for j in range(i,m,i):
            s[j]=0
print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
tf = [True] * (m+1)
cnt = 0
        
for i in range(n):
  ai = arr[i]
  if tf[ai] == True:
    cnt += 1
    for j in range(ai, m, ai):
      tf[j] = False
    if ai in arr[i+1:]:
      cnt -= 1
    

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
m =max(a)
arr = [0]*(m+1)

for i in a:
  for j in range(i,m+1,i):
    arr[i]+=1

cnt = 0
for i in a:
  if arr[i] ==1:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())))
arr = [0]*(max(a)+1)

for i in a:
  for j in range(i,max(a)+1,i):
    arr[i]+=1

cnt = 0
for i in a:
  if arr[i] ==1:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

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

maxVal = max(A)+1
isPrime = [0] * maxVal
isDuplicate = [0] * maxVal
isDivisible = [0] * maxVal

for i in range(len(A)-1):
    if A[i] == A[i+1]:
        isDuplicate[A[i]] = 1

for i in range(len(A)):
    if not isDivisible[A[i]] and not isDuplicate[A[i]]:
        isPrime[A[i]] = 1

        j = 2
        while A[i] * j < maxVal:
            isDivisible[A[i] * j] = 1

            j += 1

ans = isPrime.count(1)

print(ans)

Submission status: Wrong Answer

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

maxVal = max(A)+1
isPrime = [0] * maxVal
isDuplicate = [0] * maxVal
isDivisible = [0] * maxVal

for i in range(len(A)-1):
    if A[i] == A[i+1]:
        isDuplicate[A[i]] = 1


for i in range(len(A)):
    if not isDivisible[A[i]] and not isDuplicate[A[i]]:
        isPrime[A[i]] = 1

        j = 1
        while A[i] * j < maxVal:
            isDivisible[A[i] * j] = 1

            j += 1

ans = isPrime.count(1)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
a_max = a_list[-1]

div_set = set(x for x in set(a_list) if a_list.count(x) > 1)

count = 0
i = 0
for a in a_list:
    if a in div_set:
        continue
    count += 1
    while a <= a_max:
        div_set.add(a)
        a += a
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = {}
for a in A:
  if a not in count:
    count[a] = 0
  count[a] += 1

ans = 0
for a in A:
  if count[a] > 1:
    continue

  if 1 in count:
    if a == 1 and count[1] == 1:
      ans += 1
    continue

  #print(a)
  ok = True
  if a > 2 and a % 2 == 0 and (2 in count or (a//2) in count):
    #print(a, 2)
    ok = False
  else:
    for c in range(3, 1+int(a**0.5), 2):
      if a % c == 0 and (c in count or (a//c) in count):
        #print(a, c)
        ok = False
        break
  ans += ok
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = {}
for a in A:
  if a not in count:
    count[a] = 0
  count[a] += 1

ans = 0
for a in A:
  if count[a] > 1:
    continue

  if 1 in count:
    if a == 1 and count[1] == 1:
      ans += 1
    continue

  #print(a)
  ok = True
  if a % 2 == 0 and (2 in count or (a//2) in count):
    ok = False
  else:
    for c in range(3, 1+int(a**0.5), 2):
      if a % c == 0 and (c in count or (a//c) in count):
        ok = False
        break
  ans += ok
print(ans)

Submission status: Wrong Answer

Solution code:
N = input()
A = [int(x) for x in input().split()]
A.sort()
B = []
if len(set(A))==1:
  print(0)
else:
  while True:
    if not A[0] in A[1:]:
    	B.append(A[0])
    A=[j for j in A if j%A[0]!=0]
    if len(A)==0:
      break
  print(len(B))

Submission status: Wrong Answer

Solution code:
N = input()
A = [int(x) for x in input().split()]
A.sort()
B = []
if len(set(A))==1:
  print(0)
else:
  while True:
    i = 0
    B.append(A[i])
    A=[j for j in A if j%A[i]!=0]
    if len(A)==0:
      break
    else:
      i+=1
  print(len(B))

Submission status: Wrong Answer

Solution code:
N = input()
A = [int(x) for x in input().split()]
A.sort()
B = []
if len(set(A))==1:
  print(0)
else:
  while True:
    i = 0
    B.append(A[i])
    A=[j for j in A if j%A[i]!=0]
    if len(A)==0:
      break
    else:
      i+=1
print(len(B))

Submission status: Wrong Answer

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

if len(set(A))==1:
  print(0)
else:
  for i in range(len(A)):
      A=A[:(i+1)] + [j for j in A[(i+1):] if j%A[i]!=0]
  print(len(A))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=sorted(list(set(A)))
s=0
for i in range(len(B)):
    ok=1
    for j in range(i+1,len(B)):
        if B[j]%B[i]==0:
            ok=0
            break
    if ok==1:
        s+=1
C=[x for x in set(A) if A.count(x) > 1]
s=s-len(C)
print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
a_set=set(map(int, input().split()))

#a_ls=sorted(a_ls_pre)
#binary=[1]*N

ans=0

while a_set!=set([]):
	m=min(a_set)
	a_new=set([])
	flag=0
	for val in a_set:
		if val%m!=0:
			a_new.add(val)
		if val==m:
			flag=1
		
	a_set=a_new
	if flag==0:
		ans+=1

print(ans)


# 2darray [[0] * 4 for i in range(3)]
# import itertools

Submission status: Wrong Answer

Solution code:
N = int(input())
a_set=set(map(int, input().split()))

#a_ls=sorted(a_ls_pre)
#binary=[1]*N

ans=0

while a_set!=set([]):
	m=min(a_set)
	a_new=set([])
	for val in a_set:
		if val%m!=0:
			a_new.add(val)
		
	a_set=a_new
	ans+=1

print(ans)


# 2darray [[0] * 4 for i in range(3)]
# import itertools

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
a=sorted(a)
dp=[True]*a[-1]
for i in range(n):
    if i!=n-1:
      if a[i]==a[i+1]:
        dp[a[i]-1]=False
        dp[a[i+1]-1]=False
        continue
    if not dp[a[i]-1]:
      continue
    k=2
    while a[-1]>=k*a[i]:
        dp[k*a[i]-1]=False
        k+=1
ans=0
for i in range(n):
    if dp[a[i]-1]:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

a.sort()

s = 0
if len(a) > 1 and a[0] == a[1]:
    s = -1

j = 0
for i in range(n):
    if a[i] ** 2 > a[-1]:
        j = i

d = a[j]

b = []

while len(a) > 0:
    c = a[0]
    b.append(c)

    a = [x for x in a if (x % c != 0)]
    if c == d:
        break


print(s + len(b))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
a=sorted(a)
dp=[True]*a[-1]
for i in range(n):
    if not dp[a[i]-1]:
        continue
    if i!=n-1:
      if a[i]==a[i+1]:
        dp[a[i]-1]=dp[a[i+1]-1]=False
        continue
    k=2
    while a[-1]>=k*a[i]:
        dp[k*a[i]-1]=False
        k+=1
ans=0
for i in range(n):
    if dp[a[i]-1]:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
a=sorted(a)
dp=[True]*a[-1]
for i in range(n):
    if not dp[a[i]-1]:
        continue
    k=2
    while a[-1]>=k*a[i]:
        dp[k*a[i]-1]=False
        k+=1
ans=0
for i in range(n):
    if dp[a[i]-1]:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
a=sorted(a,reverse=True)
dp=[True]*a[0]
for i in range(n):
    if not dp[a[i]-1]:
        continue
    k=2
    while a[0]>=k*a[i]:
        dp[k*a[i]-1]=False
        k+=1
ans=0
for i in range(n):
    if dp[a[i]-1]:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())

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

if len([i for i in A if i == A[0]]) == n:
  print(0)
  sys.exit()

A.sort()

ans = 1

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort(reverse=True)
ans = 0
for i in range(n):
    not_divisible = True
    for j in range(i+1,n):
        if a_ls[i] % a_ls[j] == 0:
            not_divisible = False
            break
    if not_divisible:
        ans += 1
if n > 1 and a_ls[-2] == a_ls[-1]:
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

a.sort()

s = 0
if len(a) > 1 and a[0] == a[1]:
    s = -1

b = []

while len(a) > 0:
    c = a[0]
    b.append(c)

    a = [x for x in a if (x % c != 0)]

    if len(a) > 0 and a[0] > a[-1]:
        break

    

print(s + len(b))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

a.sort()

s = 0
if len(a) > 1 and a[0] == a[1]:
    s = -1

b = []

while len(a) > 0:
    c = a[0]
    b.append(c)

    a = [x for x in a if (x % c != 0)]

print(s + len(b))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
a.sort()
m = a[-1]+1
ans = [0] * m

for i in a:
	ans[i] = 1

for k in set(a):
	for j in range(k*2,m,k):
		ans[j] = 0
print(ans.count(1))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
a.sort()
m = a[-1]+1
ans = [0] * m

for i in a:
	ans[i] = 1

for k in set(a):
	for j in range(k*2,m-1,k):
		ans[j] = 0
print(ans.count(1))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
#C = [x for x in set(A) if A.count(x) == 1]
#A = list(set(A))

MAX_A = 1000001

dp = [0]*MAX_A

for i in A:
  if dp[i] == 0:
    for j in range(i, MAX_A,i):
      dp[j] += 1
  else:
    dp[i] += 1
  if i > 1000:
    break

c = 0
for i in A:
  if dp[i] == 1:
    c += 1

print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
C = [x for x in set(A) if A.count(x) == 1]
A = list(set(A))

MAX_A = 1000001

dp = [0]*MAX_A

for i in A:
  if dp[i] != 1:
    for j in range(i, MAX_A,i):
      dp[j] = 1
  if i > 1000:
    break

c = 0
for i in C:
  c += dp[i]

print(len(C)-c)

Submission status: Wrong Answer

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

# from numba import njit

from collections import Counter
# from itertools import accumulate
# import numpy as np
# from heapq import heappop,heappush
# from bisect import bisect_left

# @njit
def solve(n,a):
  if n == 1:
    return 0
  a = list(sorted(a))
  m = max(a)
  flags = [False] + [True]*m
  for i in range(m):
    x = i+1
    if not x in a:
      continue
    y = x * 2
    while y <= m:
      flags[y] = False
      y += x
  d = Counter(a)
  return sum(flags[i] for i in a if d[i] == 1)


  return sum(flags)



def main():
  N = int(input())
  # N,M = map(int,input().split())
  a = list(map(int,input().split()))
  print(solve(N,a))
  return

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

# from numba import njit

# from collections import Counter
# from itertools import accumulate
# import numpy as np
# from heapq import heappop,heappush
# from bisect import bisect_left

# @njit
def solve(n,a):
  if n == 1:
    return 0
  a = list(sorted(a))
  flags = [True]*n
  for i in range(n-1):
    for j in range(i+1,n):
      if a[i] == a[j]:
        flags[i] = False
        flags[j] = False
      elif a[j] % a[i] == 0:
        flags[j] = False
  return sum(flags)



def main():
  N = int(input())
  # N,M = map(int,input().split())
  a = list(map(int,input().split()))
  print(solve(N,a))
  return

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
tmp_a = [0] * n
for i in range(n):
    if tmp_a[i] == 0:
        for j in range(i+1,n):
            if a[j]%a[i] == 0:
                tmp_a[j] = 1
print(n-sum(tmp_a))

Submission status: Wrong Answer

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

answer = 0
sorted_List =  sorted(A)

def main(answer, sorted_List):
    if len(sorted_List) == 1:
        return answer+1, []

    if sorted_List[0] == sorted_List[1]:
        index = len(sorted_List)
        for i,x in enumerate(sorted_List):
            if x != sorted_List[0]:
                index = i-1
                break
        del sorted_List[0:index]
        return answer , sorted_List

    del_List = []
    for i, x in enumerate(sorted_List):
        if sorted_List[i] % sorted_List[0] == 0:
            del_List.append(x)
        if sorted_List[0]*2 > sorted_List[i]:
            ind = i
        
    for del_num in del_List:
        sorted_List.remove(del_num)

    answer += ind
    del sorted_List[0:ind]

    return answer+1, sorted_List

while len(sorted_List) > 0:
    answer , sorted_List = main(answer, sorted_List)

print(answer)

Submission status: Wrong Answer

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

answer = 0
sorted_List =  sorted(A)

def main(answer, sorted_List):
    if len(sorted_List) == 1:
        return answer+1, []

    if sorted_List[0] == sorted_List[1]:
        index = len(sorted_List)
        for i,x in enumerate(sorted_List):
            if x != sorted_List[0]:
                index = i-1
                break
        del sorted_List[0:index]
        return answer , sorted_List

    del_List = []
    for i, x in enumerate(sorted_List):
        if sorted_List[i] % sorted_List[0] == 0:
             del_List.append(x)
        
    for del_num in del_List:
        sorted_List.remove(del_num)

    return answer+1, sorted_List

while len(sorted_List) > 0:
    answer , sorted_List = main(answer, sorted_List)
    
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
A.sort()
A_list = defaultdict(int)
A_max = max(A)

for a in A:
    i = 2
    if A_list[a] != 1:
        while a * i <= A_max:
            A_list[a * i] = 1
            i += 1
    if A.count(a) > 1:
        A_list[a] = 1
    if a > A_max / 2:
        break

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

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = list(map(int,input().split()))
b=list(set(sorted(a)))
cnt=0
for i in range(len(b)-1):
  ans=True
  for j in range(0,i):
    if b[i]%b[j]==0:
      ans=False
  if ans:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A = sorted(A, key=lambda x: -x)
all = [True] * 10000001

for i in range(N):
    if all[i] == False:
        continue
    b = A[i]
    while b < 10000001:
        all[b] = False
        b += A[i]

ans = 0
for i in all:
    if i:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

A = sorted(A, key=lambda x: -x)
all = [True] * N

for i in range(N):
    for j in range(i+1, N):
        if all[i] == False:
            continue
        if A[i] % A[j] == 0:
            all[i] = False

ans = 0
for i in all:
    if i:
        ans += 1
print(ans)