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()))
ans=0
a.sort()
b=set([x for x in set(a) if a.count(x) > 1])
for i in range(len(a)):
  s=a[i]
  for j in range(i+1):
    if a[j]>s**0.5:
      if s not in b:
        ans+=1
        break
      else:
        break
    elif s%a[j]==0:
      break
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
A = [int(x) for x in input().split()]

c = collections.Counter(A)

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

total = 10 ** 6 + 1

X = [0] * total

for a in A:
    for aa in range(a + a, total, a):
        X[aa] = 1

ans = 0
for i in range(1, total):
    if X[i] == 0 and c[i] == 1:
        ans += 1

print(X)
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
A = [int(x) for x in input().split()]

c = collections.Counter(A)

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

total = 2 * 10 ** 5 + 1

X = [0] * total

for a in A:
    for aa in range(a + a, total, a):
        X[aa] = 1

ans = 0
for i in range(1, total):
    if X[i] == 0 and c[i] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import collections


N = int(input())
A = [int(x) for x in input().split()]

c = collections.Counter(A)

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

X = [0] * (2 * 10 ** 5 + 1)

for a in A:
    for aa in range(a + a, 2 * 10 ** 5 + 1, a):
        X[aa] = 1

ans = 0
for i in range(1, 2 * 10 ** 5 + 1):
    if X[i] == 0 and c[i] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = sorted(list(map(int,input().split())))
max = A[-1]
index = [0]*max
count = 0

for i in range(N):
  if(A.count(A[i])==1):
    if(index[A[i]-1]==0):
      count+=1
    for j in range(1,max):
      if(A[i]*j>max):break
      index[A[i]*j-1] += 1

print(count)

Submission status: Wrong Answer

Solution code:
def main():
	k = int(input())
	h = list(map(int,input().split()))
	ans = 0
	for i in range(k):
		temp = h[:i] + h[i+1:]
		for s in temp:
			if h[i] % s == 0 and h[i] >= s:
				break
			elif h[i] % s != 0 and s == temp[-1]:
				ans += 1
	print(ans)
			



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
def main():
	k = int(input())
	h = list(map(int,input().split()))
	ans = 0
	for i in range(k):
		temp = h[:i] + h[i+1:]
		for s in temp:
			print(h[i],s)
			if h[i] % s == 0 and h[i] >= s:
				break
			elif h[i] % s != 0 and s == temp[-1]:
				ans += 1
	print(ans)
			



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
def main():
	k = int(input())
	h = list(map(int,input().split()))
	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]

	ans = 0
	for i in range(k):
		temp = make_divisors(h[i])
		s = set(h[:i]+h[i+1:])
		for t in temp[2:]:
			if t in s:
				break
			elif t == temp[-1]:
				ans += 1
	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

a.sort()

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

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

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

a.sort()
aa=copy.copy(a)
wk=[]
an=0

while len(aa)>1:
    tg=aa[0]        
    wk=[aa[j] for j in range(1,len(aa)) if aa[j]%tg!=0]
    aa=wk
    an+=1
    wk=[]
if aa:
    an+=1
print(an)

Submission status: Wrong Answer

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

a.sort()
check = []
ans = 0

### 2 から 1000までの素数を列挙
prime = [i+2 for i in range(999)]
### エラトステネスの篩
index = 0
while True :
  if index == len(prime) :
    break
  else :
    p = prime[index]
    check_index = index + 1
    while True :
      if check_index == len(prime) :
        break
      else :
        if prime[check_index] % p == 0 :
          prime.pop(check_index)
        else :
          check_index += 1
    index += 1

### 素因数分解
def factorization(n, prime=prime) :
  ans = [0 for i in range(len(prime))]
  for i in range(len(prime)) :
    while True :
      if n % prime[i] == 0 :
        ans[i] += 1
        n /= prime[i]
      else :
        break
  return ans
  
def check_divisible(a, b) :
  for i in range(len(a)) :
    if a[i] - b[i] < 0 :
      return False
  return True

### すべての数を素因数分解
a_fact = []
for i in range(len(a)) :
  a_fact.append(factorization(a[i]))

check_fact = []

### 小さいほうから順番にチェック
for i in range(len(a)) :
  ### 同じ数が存在するかチェック
  if len(check) > 0 :
    if check[-1] == a[i] :
      continue
  if i < len(a) - 1 :
    if a[i+1] == a[i] :
      check.append(a[i])
      check_fact.append(a_fact[i])
      continue
  
  ### これ以降は省略できないか?
  flag = False
  for i_check in range(len(check_fact)) :
    if check_divisible(a_fact[i], check_fact[i_check]) :
      flag = True
      break
  ### 割り切れるものがcheck内になかったものを数える
  
  if not(flag) :
    ans += 1
    check.append(a[i])
    check_fact.append(a_fact[i])
  
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

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

a.sort()
aa=copy.copy(a)
wk=[]
an=0

while len(aa)>1:
    tg=aa[0]
    for j in range(1,len(aa)):
        if aa[j]%tg!=0:
            wk.append(aa[j])
    aa=wk
    an+=1
    wk=[]
if aa:
    an+=1
print(an)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().rstrip().split(' ')))
    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if a[i] == a[j]:
                continue
            if a[i] % a[j] == 0:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
A = list(map(int,input().split()))
count = 0
for i,a in enumerate(A):
    flag = 0
    A2 = deepcopy(A)
    del A2[i]
    Aas = sorted(A2)
    if a not in A2:
        for b in Aas:
            if a % b  == 0:
                flag = 1
                break
            if a/b < 2:
                break
    if flag == 0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a_list = list(map(int, input().split()))
    res_set = set(a_list)
    # キーに要素、値に出現回数を持つカウンタ
    a_counter = Counter(a_list)
    for e in a_counter.items():  # e:(整数，出現回数)
        if e[1] == 1:
            for i in range(e[0] * 2, 2 * 10**5 + 1, e[0]):  # その整数を含まない倍数
                res_set.discard(i)
        else:
            for i in range(e[0], 2 * 10**5 + 1, e[0]):  # その整数を含む倍数
                res_set.discard(i)
    print(len(res_set))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
THE_NUM = 10**6 + 1

dp = [True] * THE_NUM

for i in A:
  for j in range(i * 2, THE_NUM, i):
    dp[j] = False

ans = 0
prev_num = -1
for i, x in enumerate(A):
  # the same number after the second will not counted in the answer.
  if dp[x] == True and prev_num != i:
    ans += 1

# if they are all the same number, the answer is 0.
if A[0] == A[-1]:
  ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
A = list(map(int,input().split()))
count = 0
Aas = sorted(A)
for i,a in enumerate(A):
    flag = 0
    A2 = deepcopy(A)
    del A2[i]
    if a not in A2:
        for b in Aas:
            if a % b  == 0:
                flag = 1
                break
            if a/b < 1:
                break
    if flag == 0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
A = list(map(int,input().split()))
count = 0
Aas = sorted(A)
Ades = sorted(A,reverse=True)
for i,a in enumerate(A):
    flag = 0
    A2 = deepcopy(A)
    del A2[i]
    if a not in A2:
        for b in Aas:
            if a % b  == 0:
                flag = 1
                break
            if a/b < 1:
                break
        if flag == 0:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())))
count=0
b=Counter(a)
count_list=[0]*(10**6)
for i in a:
  if b[i]==1:
    if count_list[i-1]==0:
      count+=1
      j=1
      while i*j<=10**6:
        count_list[i*j-1]+=1
        j+=1
print(count)

Submission status: Wrong Answer

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

for i in range(N-1):
    for j in range(i+2):
        if i == j or A_list[i] % A_list[j] != 0:
            if j == i+1:
                count += 1
            continue
        else:
            break


for j in range(N-1):
    if A_list[N-1] % A_list[j] != 0:
        if j == N-2:
            count += 1
        continue
    else:
        break


print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
dp = [True for i in range(max(A)+1)]
d = {}
for i in A:
    if i in d.keys():
        d[i]+=1
    else:
        d[i] = 1

for i in A:
    if d[i]>1:
        dp[i]  = False
    j = 2*i
    if (dp[i]):
        while (j<=max(A)):
            dp[j] = False
            j+=i
count = 0
for i in A:
    if dp[i] == True:
        count +=1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [True for i in range(max(A)+1)]
d = {}
for i in A:
    if i in d.keys():
        d[i]+=1
    else:
        d[i] = 1

for i in A:
    if d[i]>1:
        dp[i]  = False
    j = 2*i
    if (dp[i]):
        while (j<=max(A)):
            dp[j] = False
            j+=i
count = 0
for i in A:
    if dp[i] == True:
        count +=1
print(count)

Submission status: Wrong Answer

Solution code:

import math

n = int(input())
given_lst = list(map(int,input().split()))
lst = [i for i in range(max(given_lst)+1)]
lst_status = [1 for _ in range(len(lst))]


for e in given_lst:
    divided_num = e + e
    while(divided_num <= max(given_lst)):
        lst_status[divided_num] = 0
        divided_num += e

ans = 0
for e in given_lst:
    if lst_status[e] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = False
b = [False] * 1000010
c = [False] * 1000010
for i in range(n - 1):
    if a[i] == a[i + 1]:
        b[a[i]] = True

ans = 0
for i in range(n):
    if b[a[i]]:
        continue
    if not c[a[i]]:
        ans += 1
        for j in range(a[i], 1000010, a[i]):
            c[j] = True

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = False
b = [False] * 1000010
for i in range(n - 1):
    if a[i] == a[i + 1]:
        b[a[i]] = True

ans = 0
for i in range(n):
    if not b[a[i]]:
        ans += 1
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()] 

c = Counter(a)
a.sort()
max_a = a[-1]
flag = [True for _ in range(max_a+1)]
ans = []
for i in a:
    if c[i] >= 2:
        flag[i] = False
    
    if not flag[i]:
        continue
    else:
        for j in range(i + i, max_a + 1, i):
            flag[j] = False
for i in a:
    if flag[i]:
        ans.append(i)
#print(ans)
print(len(ans))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()] 

c = Counter(a)
a.sort()
max_a = a[-1]
flag = [True for _ in range(max_a+1)]
ans = []
for i in a:
    if c[i] >= 2:
        flag[i] = False
    elif not flag[i]:
        continue
    else:
        for j in range(i + i, max_a + 1, i):
            flag[j] = False
for i in a:
    if flag[i]:
        ans.append(i)
#print(ans)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import copy

N = int(input())
A_n = set(map(int, input().split(' ')))
# print(A_n)
count = 0
for a in A_n:
    temp = copy.deepcopy(A_n)
    temp.remove(a)
    # print(len(temp))
    if 0 not in set(map(lambda x: a%x, temp)) and len(temp) != 0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_n = sorted(list(map(int, input().split(' '))), reverse=True)
count = 0
for i in range(len(A_n)-1):
    # print(list(map(lambda x: x%A_n[i], A_n)))
    # print(str(A_n[i]) + ' ' + str(A_n[i+1:]))
    # print(list(map(lambda x: A_n[i]%x, A_n[i+1:])))
    if 0 not in set(map(lambda x: A_n[i]%x, A_n[i+1:])):
        # print('☆'+str(i)+'☆')
        count += 1
# print(A_n)
# print(A_n[-1])
# print(A_n[:-1])
if A_n[-1] not in set(A_n[:-2]):
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_n = sorted(list(map(int, input().split(' '))), reverse=True)
count = 0
for i in range(len(A_n)-1):
    if list(map(lambda x: A_n[i]%x, A_n[i+1:])).count(0) == 0:
        count += 1
if A_n[-1] not in set(A_n[:-2]):
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_n = sorted(list(set(map(int, input().split(' ')))), reverse=True)
if len(A_n) == 1:
    print('0')
else:
    count = len(A_n)
    for i in range(len(A_n)-1):
        for j in range(i+1, len(A_n)):
            if A_n[i]%A_n[j] == 0:
                # print(str(A_n[i]) + ' ' + str(A_n[j]))
                count -= 1
                break
    print(count)

Submission status: Wrong Answer

Solution code:
n = 10
A = [33, 18, 33, 28, 8, 19, 89, 86, 2, 4]

C = {a:0 for a in A}

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

maxA = max(A)

D = {a:0 for a in A}

for a in A:
    t = 2
    while a*t <= maxA:
        if a*t in A:
            D[a*t] = D[a*t]+1
        t = t+1

counter = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        counter = counter+1
        
print(counter)

Submission status: Wrong Answer

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

C = 0

for i in range(n):
    for j in range(n):
        if A[i] % A[j] == 0 and i != j:
            C = C+1
            break

print(C)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
# n = 10
# A = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

C = 0

for i in range(n):
    for j in range(n):
        print(A[i] % A[j])
        if A[i] % A[j] == 0 and i != j:
            C = C+1
            break

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):
    count = 0
    for j in range(i+1,N):
        if A[i] % A[j] != 0:
            count += 1
    if count == N - (i+1):
        if i == N-1:
            if A[i] != A[i-1]:
                ans += 1
        else:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))
tmp = [0] * len(l)
ans = 0

l = list(set(l))

#print(l)

for x in range(len(l)):
    i = x + 1
    for j in l:
        #print("l[i]",l[i-1],"%","j",j," = ",l[i-1]%j)
        if l[i-1] % j ==0:
            tmp[i-1] = tmp[i-1]+1

#print(tmp)

for i in tmp:
    if i == 1:
        ans = ans + 1

if len(l) == 1:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = False
b = [False] * 1000010
for i in range(n - 1):
    if a[i] == a[i + 1]:
        b[a[i]] = True

ans = 0
for i in range(n):
    if not b[a[i]]:
        ans += 1
        for j in range(2 * a[i], 1000010, a[i]):
            b[j] = True

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = int(1e6) + 10
sieve = [0] * int(MAX)
for i in a:
    sieve[i] += 1
ans = 0
for idx, val in enumerate(sieve):
    if val == 0:
        continue
    if val > 1:
        sieve[idx] = 0
        continue
    ans += 1
    for i in range(idx * 2, MAX, idx):
        sieve[i] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    x_list = list(set(p_list))
    if len(x_list) == 1:
        print(0)
        sys.exit()
    ans = 0
    for i in range(len(p_list)):
        for j in range(len(x_list)):
            if (p_list[i] != x_list[j] and p_list[i]%x_list[j] == 0):
                ans += 1
                break

    print(len(p_list) - ans)
   
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
arr= list(map(int,input().split(' ')))
arr.sort()
count=0
d= [True for i in range(1000001)]
if arr.count(arr[0])!=n:
    for i in range(n):
        curr= arr[i]
        if d[curr]==True:
            count+=1
            db= curr*2
            while db<=1000000:
                d[db]=False
                db+=curr
    print(count)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr= list(map(int,input().split(' ')))
arr.sort()
count=0
d= [True for i in range(arr[n-1]+1)]
if arr.count(arr[0])!=n:
    for i in range(n):
        curr= arr[i]
        if d[curr]==True:
            count+=1
            db= curr*2
            while db<=arr[n-1]:
                d[db]=False
                db+=curr
    print(count)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr= list(map(int,input().split(' ')))
arr.sort()
count=0
d= [True for i in range(arr[n-1]+1)]
if arr.count(arr[0])!=n:
    for i in range(n):
        curr= arr[i]
        if d[curr]==True:
            count+=1
            db= curr*2
            while db<arr[n-1]:
                d[db]=False
                db+=curr
    print(count)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr= list(map(int,input().split(' ')))
arr.sort()
count=0
d= [True for i in range(n)]
if arr.count(arr[0])!=n:
    for i in range(n):
        if d[i]==True:
            count+=1
            for j in range(i+1,n):
                if arr[j]%arr[i]==0:
                    d[j]=False
    print(count)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr= list(map(int,input().split(' ')))
arr.sort()
count=0
if arr.count(arr[0])!=n:
    for i,j in enumerate(arr):
        count+=1
        for a,b in enumerate(arr[(i+1):]):
            if b%j==0:
                arr.remove(b)
    print(count)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
ans = [True for i in range(max(A)+1)]
maxa = max(A)
count = 0
alr = [0 for i in range(max(A)+1)]
for i in A:
    if not alr[i]:
        alr[i] += 1
        if ans[i]:
            count += 1
        n = 1
        while n*i <= maxa:
            ans[n*i] = False
            n+=1
    else:
        if alr[i] == 1:
            count -= 1
        alr[i] += 1
        
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
f = 0
sortedA = sorted(A, reverse=True)

for i in range(len(sortedA)):
    check = False
    for j in range(len(sortedA)):
        if i >= j:
            continue
        else:
            if sortedA[i] % sortedA[j] == 0:
                check = True
                break
    if check == True:
        f += 1
if len(A) - f == 1:
    ans = 0
else:
    ans = len(A) - f
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
f = 0
sortedA = sorted(A, reverse=True)

for i in range(len(sortedA)):
    check = False
    for j in range(len(sortedA)):
        if i >= j:
            continue
        else:
            if sortedA[i] % sortedA[j] == 0:
                check = True
                break
    if check == True:
        f += 1
ans = len(A) - f
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[int(i) for i in input().split()]
dp=[1]*(max(arr)+1)
ele=set()
for i in arr:
    ele.add(i)
for i in range(1,max(arr)+1):
    if i in ele and dp[i]:
        j=2
        while i*j<=max(arr):
            dp[i*j]=0
            j+=1
cnt=0
for i in range(1,len(dp)):
    if i in ele and dp[i]:
        cnt+=1
if len(ele)==1:
    print(0)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
D = [1 for i in range(max(A)+1)]
E = {}
for i in A:
    if i in E:
        E[i] += 1
        D[i] = 0
    else:
        E[i] = 1
F = set()
for i in E:
    if E[i] == 1:
        F.add(i)
for i in F:
    for j in range(2, max(A)//i+1):
        D[i*j] = 0
S = 0
for i in range(N):
    S += D[A[i]]
print(S)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
D = {i: 1 for i in range(1, max(A)+1)}
E = {}
for i in A:
    if i in E:
        E[i] += 1
        D[i] = 0
    else:
        E[i] = 1
F = set()
for i in E:
    if E[i] == 1:
        F.add(i)
for i in F:
    for j in range(2, max(A)//i+1):
        D[i*j] = 0
S = 0
for i in range(N):
    S += D[A[i]]
print(S)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
D = {i: 1 for i in range(1, max(A)+1)}
E = {}
for i in A:
    if i in E:
        E[i] += 1
        D[i] = 0
    else:
        E[i] = 1
F = set()
for i in E:
    if E[i] == 1:
        F.add(i)
for i in F:
    for j in range(2, max(A)//i+1):
        D[i*j] = 0
S = 0
for i in range(N):
    S += D[A[i]]
print(S)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
a.sort()
era=[1]*(ma+1)
era[0]=0
era[1]=0
#0と1はふるいにかけられている。
cn=Counter(a)

count=0
for i in range(n):
  if era[a[i]]==0:continue
  else:
    era[a[i]]=0
    if cn[a[i]]==1:
      count+=1
    for j in range(2*a[i],ma+1,a[i]):
      era[j]=0
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
a.sort()
era=[1]*(ma+1)
era[0]=0
era[1]=0
#0と1はふるいにかけられている。

count=0
for i in range(n):
  if era[a[i]]==0:continue
  else:
    era[a[i]]=0
    count+=1
    for j in range(2*a[i],ma+1,a[i]):
      era[j]=0
print(count)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
if N == 1:
    print(0)
    sys.exit()
A = [int(i) for i in input().split()]
ls = [0 for i in range(10**6+1)]
s = set()
for a in A:
    if ls[a] == 0:
        cur = 1
        while a*cur <= 10**6:
            ls[a*cur] += 1
            cur += 1
        s.add(a)
    else:
        ls[a] += 1
ans = 0
for a in A:
    if ls[a] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
if N == 1:
    print(0)
    sys.exit()
A = [int(i) for i in input().split()]
ls = [0 for i in range(10**6+1)]
ls[0], ls[1] = 0, 0
s = set()
for a in A:
    if ls[a] == 0:
        cur = 1
        while a*cur <= 10**6:
            ls[a*cur] += 1
            cur += 1
        s.add(a)
    else:
        if a in s:
            ls[a] += 1
            continue
        cur = 1
        while a*cur <= 10**6:
            ls[a*cur] += 1
            cur += 1
        s.add(a)
ans = 0
for a in A:
    if ls[a] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

cnt_A = Counter(A_list)
max_num = max(A_list)


for i in range(len(A_list)-1):
    if A_list[i] not in cnt_A:
        continue
    
    for j in range( 2, max_num // A_list[i] + 1 ):
        n = A_list[i] * j
        
        if n in cnt_A:
            del cnt_A[n]


ans = [ k for k,v in cnt_A.items() if v == 1 ]
print( len(ans) if ans else 0 )

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

def main():
    n = int(input())
    A = sorted(list(map(int, input().split())))

    multiples = Counter(A)

    bucket = Counter(A)
    res = 0

    for num in A:
        if bucket[num] == 1 and multiples[num] == 1:
            res += 1
        if multiples[num] == 1:
            for i in range(num, 10**6+1, num):
                multiples[i] = 0
    
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    l = list(set(p_list))

    if len(l) == 1:
        print(0)
        sys.exit()
        
    ans = 0
    for i in range(len(l)):
        count = 0
        for j in range(len(l)):
            if i != j:
                
                if l[i]%l[j] != 0:
                    count += 1
                else:
                    continue
        if (count == len(l)-1):
            ans += 1

    print(ans)

   
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline

def main():
    N = int(input())
    l = Counter(list(map(int, input().split())))
    A = []
    for a, count in sorted(l.items()):
        if count == 1:
            A.append(a)

    if len(A) == 0:
        print(0)
        return
    MAX_PRIME = A[-1] + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in A:
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    ans = 0
    for a in A:
        if is_prime[a]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def 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
n = int(input())
a = [int(k) for k in input().split()]
c = 0
for i in range(n):
    l = divisors(a[i])
    l.remove(1)
    for j in range(n):
        if i == j:
            continue
        if a[j] in l:
            break
    else:
        # print(a[i])
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:
    print(1)
else:
    l=[int(i) for i in input().split()]
    l.sort()
    res=0
    ll=[]
    for i in range(n):
        flag=True
        for j in ll:
            if not l[i]%j:
                flag=False
                break
            if l[i]<j*j:
                break
        if flag:
            ll.append(l[i])
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
    print(res)

Submission status: Wrong Answer

Solution code:
def main():
    max_num = 10**6
    N = int(input())
    A = list(map(int, input().split()))
    M = {}
    for a in A:
        if a not in M:
            M[a] = 0
        M[a] += 1
    B = set(sorted(A))
    S = [0]*(max_num + 1)
    ans = 0

    for b in B:
        if M[b] > 1:
            continue
        if S[b] != 0:
            continue
        ans += 1
        v = b
        while v <= max_num:
            S[v] = 1
            v += b
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = 0
    amax = max(a)

    for i in a:
        if (amax ** 0.5) + 1 < i:
            break
        if table[i-1] is False:
            continue
        for j in range(i*2, amax+1, i):
            table[j-1] = False

    c = Counter(a)
    for i in set(a):
        if table[i-1]:
            if c[i] == 1:
                res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = []
    amax = max(a)
    dup = 0

    for i in a:
        if table[i-1]:
            res.append(i)
        else:
            continue
        for j in range(i, amax+1, i):
            table[j-1] = False
    print(len(res) - dup)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = []
    amax = max(a)
    dup = 0

    for i in a:
        if table[i-1]:
            if i not in res:
                res.append(i)
            else:
                dup += 1  
                continue
        else:
            continue
        for j in range(i *2, amax, i):
            table[j-1] = False
    print(len(res) - dup)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

total = 0
flag = 0

for i in range(n):
  for j in range(i):
    if i == j:
      continue
    
    if int(a[i]/a[j]) == a[i]/a[j]:
      flag = 1
      break
    
  if flag == 0:
    total += 1
  else:
    flag = 0
    
print(total)