Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
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
def is_divisible(factors):
	global appeared
	
	for dic in appeared:
		can_divide = True
	
		for k, v in dic.items():
			try:
				if factors[k] < v:
					can_divide = False
					break
			except:
				can_divide = False
				break
		
		if can_divide:
			return True
	
	return False


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 = [] # 辞書をリスト化
lib = Factorization()

for k, v in sorted(dic.items(), key=lambda x:x[0]):
	factors = lib.get_factors(k)
	
	if v == 1:
		if is_divisible(factors) == False:
			ans += 1

	import copy
	copy_ = copy.deepcopy(factors)			
	appeared.append(copy_)

print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
c=0
for i in range(n):
    if i>0 and a[i-1]==a[i]:
        continue
    for j in range(n):
        if i==j:
            continue
        else:
            if a[j]>a[i] or a[i]//2<a[j]<a[i]:
                c+=1
                break
            if a[i]%a[j]==0:
                break
    else:
        c+=1
print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

num_array = np.zeros(max(a_list)+1, dtype=np.int8)
for a in a_list:
    num_array[a::a] += 1

count = 0
for a in a_list:
  if num_array[a] == 1:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

num_array = np.zeros(int(2e6+1), dtype=np.int8)
for a in a_list:
    num_array[a::a] += 1

count = 0
for a in a_list:
  if num_array[a] == 1:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
max_=10**6+1
ans=0

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

b=[True]*(max_+1)
data.sort()
c=Counter(data)
print(c)

for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
max_=10**6+1
ans=0

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

b=[True]*(max_+1)
data.sort()
c=Counter(data)
print(c)

for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:#複数存在考慮
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
a = sorted(list(set(a)))
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      if dp[m] == False:
         break
      dp[m] = False
      m += v
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = Counter(a)
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      if dp[m] == False:
         break
      dp[m] = False
      m += v
print(ans)

Submission status: Wrong Answer

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

from collections import defaultdict 
from collections import Counter
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]

    dd = Counter(A)

    #重複を取り除き、各要素が一つずつ存在するリストを作る
    A = [key for key in dd.keys()]  
    A.sort()

    #isntDiv[x]:=Tureのときxは他の要素で割り切れない
    isntDiv = defaultdict(lambda: 1) 
    #最小の要素は他の要素で割り切れない
    isntDiv[A[0]] = 1
    cnt = 0
    for i in A:
        if isntDiv[i]:
            cnt += 1
            for j in range(i*2, A[-1]+1 , i):
                isntDiv[j] = 0

    #重複している要素は自身と同じ数の異なる要素で割り切れるのでカウントしてはいけない
    for val in dd.values():
        if val > 1:
            cnt -= 1
    print(cnt) 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from collections import defaultdict 
from collections import Counter
def main():
    N = int(readline())
    if N == 1:
        print(0)
        return

    A = [int(i) for i in readline().split()]

    #重複している要素は除外する
    dd = Counter(A)

    if dd[1] > 1:
        print(0)
        return

    A = [int(key) for key, val in dd.items() if val == 1]  
    A.sort()

    #isntDiv[x]:=Tureのときxは他の要素で割り切れない
    isntDiv = defaultdict(lambda: 1) 

    if len(A) == 0:
        print(0)
        return

    #最小の要素は他の要素で割り切れない
    isntDiv[A[0]] = 1
    cnt = 0
    for i in A:
        if isntDiv[i]:
            cnt += 1
            for j in range(i*2, A[-1]+1 , i):
                isntDiv[j] = 0
    print(cnt) 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(set(list(map(int,input().split()))))
can_div = []
for num1 in range(0,len(a)):
  for num2 in range(1,len(a)):
    if num1 == num2:
      break
    if a[num1] % a[num2] == 0:
      can_div.append(a[num1])
print(len(set(a) - set(can_div)))

Submission status: Wrong Answer

Solution code:
from math import sqrt


def get_divisors(n):
    div = []
    append = div.append
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            append(i)
            if i != n // i:
                append(n // i)
    div.sort()
    return div


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

# check
if len(set(A)) == 1:
    print(0)
else:
    cnt = 0
    for idx, a in enumerate(A):
        if idx == 0:
            check = A[1:]
        elif idx == N - 1:
            check = A[:idx]
        else:
            check = A[:idx] + A[idx + 1:]

        if a != 1 and 1 in check:
            continue
        elif a in check:
            continue
        else:
            div = get_divisors(a)
            if not [1 for d in div if d in check]:
                cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
from math import sqrt


def get_divisors(n):
    div = []
    append = div.append
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            append(i)
            if i != n // i:
                append(n // i)
    div.sort()
    return div


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

# check
if len(set(A)) == 1:
    print(0)
else:
    cnt = 0
    for idx, a in enumerate(A):
        if idx == 0:
            check = A[1:]
        elif idx == N - 1:
            check = A[:idx]
        else:
            check = A[:idx] + A[idx + 1:]
        check = set(filter(lambda x: x <= a, check))

        if a != 1 and 1 in check:
            continue
        elif a in check:
            continue
        else:
            div = get_divisors(a)
            if not [1 for d in div if d in check]:
                cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=list(map(int,input().split()))
def factorize(n):
    fct=[]
    for i in range(1,int(pow(n,0.5))+1):
        if n%i==0:
            fct.append(i)
            if i!=n//i:
                fct.append(n//i)
    return fct
s=set()
c=Counter(a)
a.sort()
ans=0
for i in range(n):
    if c[a[i]]==1:
        if not set(factorize(a[i]))&s:
            s.add(a[i])
            ans+=1
print(ans)

Submission status: Wrong Answer

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

# check
if len(set(A)) == 1:
    print(0)
else:
    cnt = 0
    for idx, a in enumerate(A):
        if idx == 0:
            check = A[1:]
        elif idx == N - 1:
            check = A[:idx]
        else:
            check = A[:idx] + A[idx + 1:]
        check = set(filter(lambda x: x <= a, check))

        if a != 1 and 1 in check:
            continue
        elif a in check:
            continue
        else:
            fl = True
            for c in check:
                if a % c == 0:
                    fl = False
                    break

            if fl is True:
                cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
from math import sqrt


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


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

# check
if len(set(A)) == 1:
    print(0)
else:
    cnt = 0
    for idx, a in enumerate(A):
        if idx == 0:
            check = A[1:]
        elif idx == N - 1:
            check = A[:idx]
        else:
            check = A[:idx] + A[idx + 1:]
        check = set(filter(lambda x: x <= a, check))

        if is_prime(a) is True and a not in check and 1 not in check:
            cnt += 1
            continue
        elif a in check:
            continue
        else:
            fl = True
            for c in check:
                if a % c == 0:
                    fl = False
                    break

            if fl is True:
                cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
  
n=int(input())
a = list(input().split())
a = [int(i) for i in a]
l=[True]*n
sort = sorted(a,reverse=True)
dep=[x for x in set(a) if a.count(x) >= 2]


for i in range(n):
  if l[i:] == [False]*len(sort[i:]):
    break
  if l[i] == False:
    continue
  if is_prime(sort[i]) and sort[i] not in dep:
    continue

  
  for ii in range (i+1,n):
    #print(sort[ii])
    if sort[i] % sort[ii] == 0:
      #print("割り切れる")
      l[i] = False
    if sort[ii] == sort[i]:
      #print("重複")
      l[i] = False
      l[ii] = False

#print(l)
#print(sort)
print(len([x for x in l if x]))

Submission status: Wrong Answer

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

# check
if len(set(A)) == 1:
    print(0)
else:
    cnt = 0
    for idx, a in enumerate(A):
        if idx == 0:
            check = A[1:]
        elif idx == N - 1:
            check = A[:idx]
        else:
            check = A[:idx] + A[idx + 1:]
        check = set(filter(lambda x: x <= a, check))

        if a in check:
            continue

        fl = True
        for c in check:
            if a % c == 0:
                fl = False
                break

        if fl is True:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

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

# check
if len(set(A)) == 1:
    print(0)
else:
    cnt = 0
    for idx, a in enumerate(A):
        if idx == 0:
            check = A[1:]
        elif idx == N - 1:
            check = A[:idx]
        else:
            check = A[:idx] + A[idx + 1:]
            
        if a in check:
            continue

        fl = True
        for c in check:
            if a % c == 0:
                fl = False
                break

        if fl is True:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

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

# check
if len(set(A)) == 1:
    print(0)
else:
    cnt = 0
    for idx, a in enumerate(A):
        if idx == 0:
            check = A[1:]
        elif idx == N - 1:
            check = A[:idx]
        else:
            check = A[:idx] + A[idx + 1:]

        fl = True
        for c in check:
            if a % c == 0:
                fl = False
                break

        if fl is True:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

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

# check
if len(set(A)) == 1:
    print(0)
else:
    cnt = 0
    for idx, a in enumerate(A):
        if not [1 for ind, n in enumerate(A) if ind != idx and a % n == 0]:
            cnt += 1

    print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = list(input().split())
a = [int(i) for i in a]
sort = sorted(a)
sortSet = list(set(sort))
n=len(sortSet)
l=[True]*n

dep=[x for x in set(a) if a.count(x) >= 2]

for i in range(n):
  #print(sort[i], l)
  if sortSet[i] == False:
    continue
  if l[i:] == [False]*len(sortSet[i:]):
    break
  for ii in range (i+1,n):
    #print(sort[ii])
    if sortSet[ii] % sortSet[i] == 0:
      #print("割り切れる")
      l[ii] = False
    if sortSet[ii] == sortSet[i]:
      #print("重複")
      l[i] = False
      l[ii] = False


ansl=len([x for x in l if x])
#print([i for i in range(ansl) if sortSet[i] not in dep])
print(len([i for i in range(ansl) if sortSet[i] not in dep]))

Submission status: Wrong Answer

Solution code:
# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
A.sort()
MAX=10**6+1
L = [0]*MAX
used = set()
first = True
for a in A:
    if L[a] ==2:
        continue
    if a in used and first:
        first = False
        for i in range(0,MAX,a):
            L[i] = 2
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[a] = 1
    for i in range(2*a,MAX,a):
        L[i] = 2
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
A.sort()
MAX=A[-1]+2
L = [0]*MAX
used = set()
first = True
for a in A:
    if L[a] ==2:
        continue
    if a in used and first:
        first = False
        for i in range(0,MAX,a):
            L[i] = 2
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[a] = 1
    for i in range(2*a,MAX,a):
        L[i] = 2
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
A.sort()
MAX=A[-1]+1
L = [0]*MAX
used = set()
first = True
for a in A:
    if L[a] ==2:
        continue
    if a in used and first:
        first = False
        for i in range(0,MAX,a):
            L[i] = 2
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[a] = 1
    for i in range(2*a,MAX,a):
        L[i] = 2
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)

Submission status: Wrong Answer

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    lim = max(a) + 1
    tmp = [0] * (lim)
    # set_a = list(set(a))
    # set_a.sort()
    a.sort()

    for aa in a:
        if tmp[aa] == 0:
            for j in range(lim):
                if aa * j > lim-1:
                    break
                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
M = 10 ** 6 + 5
N = int(input())
A_ref = list(map(int, input().split()))
A = set()
for i in A_ref:
    A.add(i)
print(A)
cnt = [0] * M
for i in A:
    if(cnt[i] > 2):
        continue
    for j in range(i, M, i):
        cnt[j] += 1
ans = 0
for i in A:
    if(cnt[i] == 1):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
M = 10 ** 6 + 5
N = int(input())
A_ref = list(map(int, input().split()))
A = set()
for i in A_ref:
    A.add(i)
cnt = [0] * M
for i in A:
    for j in range(0, M, i):
        cnt[j] += 1
ans = 0
for i in A:
    if(cnt[i] == 1):
        ans += 1
print(ans)

Submission status: Wrong Answer

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

def find_next_true(ind, bools, N):
    for i in range(ind+1, N):
        if bools[i]:
            return i
    return N

def Main(N, A):
    A.sort()
    bools = [True]*N
    i = 0
    j = 0
    while i*i < N:
        j = find_next_true(i, bools, N)
        while j < N:
            div, mod = divmod(A[j], A[i])
            if mod == 0:
                bools[j] = False
                if div == 1:
                    bools[i] = False
            j = find_next_true(j, bools, N)
        i = find_next_true(i, bools, N)
    return bools.count(True)

print(Main(N, A))

Submission status: Wrong Answer

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

flags = [False for i in range(Amax+1)]
counts = [0 for i in range(Amax+1)]

for a in A:
    flags[a] = True
    counts[a] += 1

count = 0
for i in range(1, Amax+1):
    if counts[i] == 1:
        count += 1
    if flags[i]:
        for j in range(i*2, Amax+1, i):
            flags[j] = False
print(count)

Submission status: Wrong Answer

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

flags = [False for i in range(Amax+1)]
counts = [0 for i in range(Amax+1)]

for a in A:
    flags[a] = True
    counts[a] += 1

count = 0
for i in range(1, Amax+1):
    if counts[i] > 1:
        flags[i] = False
    if flags[i]:
        for j in range(i*2, Amax+1, i):
            flags[j] = False
print(sum(flags))

Submission status: Wrong Answer

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

flags = [False for i in range(Amax+1)]
counts = [0 for i in range(Amax+1)]

for a in A:
    flags[a] = True
    counts[a] += 1

count = 0
for i in range(1, Amax+1):
    if counts[i] > 1:
        flags[i] = False
    elif flags[i]:
        for j in range(i*2, Amax+1, i):
            flags[j] = False
print(sum(flags))

Submission status: Wrong Answer

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

A.sort(reverse=True)
S=0
if len(set(A)) == 1:
    print(int(0))

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

    print(int(N-S))

Submission status: Wrong Answer

Solution code:
"""A問題
x= list(map(int,input().split()))
a = 1
for i in x:
    if i == 0:
        print(a)
    a+=1
"""
"""B問題
[x,y]= list(map(int,input().split()))
if (y-2*x)%2==0 and y-2*x>=0 and 4*x-y>=0 :
    print("Yes")
else:
    print("No")
"""
""" c問題
[x,n]= list(map(int,input().split()))
p= list(map(int,input().split()))
q= [i for i in range(102)]
p= [i for i in q if i not in p]
r = [abs(i-x) for i in p]
print(p[r.index(min(r))])
 """
n= int(input())
a= list(set(map(int,input().split())))
if len(a)==1:
    print(0)
else:
    a.sort()
    b=list()
    for i in range(1,len(a)):
        for j in range(i):
            if a[i]%a[j]== 0:
                b.append(a[i])
                break
    print(len(a)-len(b))

Submission status: Wrong Answer

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

for j in range(N):
    for i in range(N):
        if A[j]%A[i] == 0 and A[j] != A[i]:
            temp += 1
            break
        
        else:
            pass
    

print(N-temp)

Submission status: Wrong Answer

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

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        ans+=1

for i in ng:
    if i in mul:
        ans-=1

print(ans)

Submission status: Wrong Answer

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

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        ans+=1

print(ans-len(ng))

Submission status: Wrong Answer

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


same=set()
cur=a[0]
miss=False
for i in a[1:]:
  if cur==i:
    if not miss:same.add(cur)
  else:
    miss=False
    cur=i

    
vmax=a[-1]//2
while True:
	newa=[]
	k=a[0]
	if not k in same:ans+=1
	for i in a[1:]:
		if not i%k==0:newa.append(i)
	a=newa
	if len(a)==0 or a[0]>vmax:break
print(ans+len(a))

Submission status: Wrong Answer

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


same=set()
cur=a[0]
miss=False
for i in a[1:]:
  if cur==i:
    if not miss:same.add(cur)
  else:
    miss=False
    cur=i

    
vmax=a[-1]//2
while True:
	newa=[]
	k=a[0]
	if not k in same:ans+=1
	for i in a[1:]:
		if not i%k==0:newa.append(i)
	a=newa
	if len(a)==0 or a[0]>vmax:break
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	Aset = set(A)
	if 1 in Aset:
		print(1)
		return
	Acnt = Counter(A)
	ans = 0
	for i, num in enumerate(A):
		div = 2
		flag = True
		if Acnt[num] > 1:
			continue
		while div*div <= num:
			if num % div == 0:
				other = num//div
				if div in Aset or other in Aset:
					flag = False
					break
			div += 1
		if flag:
			ans += 1
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(max(arr)+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i] or cnt[i] >= 2:
        continue
    ans += 1
    for k in range(i,ma+1,i):
        check[k] = False
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	Aset = set(A)
	if 1 in Aset:
		print(0)
		return
	Acnt = Counter(A)
	ans = 0
	for i, num in enumerate(A):
		div = 2
		flag = True
		if Acnt[num] > 1:
			continue
		while div*div <= num:
			if num % div == 0:
				other = num//div
				if div in Aset or other in Aset:
					flag = False
					break
			div += 1
		if flag:
			ans += 1
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
ab=[]
for i in Counter(a):
  if Counter(a)[i]==1:
    ab.append(i)
ans=set([])
a.sort()
ans_count=0
N=10**9+1
ab=set(ab)
if len(ab)==0:
  print(0)
else:
  for i in range(n):
    if (not a[i] in ans) and (a[i] in ab):
      N=a[i]
      count=1
      ans.add(N)
      ans_count+=1
      count+=1
      while N*count<10**6+1:
        ans.add(N*count)
        count+=1
  print(ans_count)

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from collections import Counter
n=int(stdin.readline())
a=sorted(map(int,stdin.readline().split()))
d=Counter(a)
m1=max(a);ans=0
vis=[0]*(m1+1)
for v in a:
    if not vis[v]:
        if d[v]>1:ans+=1
        for mul in range(v,m1+1,v):
            vis[mul]=1
stdout.write(str(ans))

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
n=int(stdin.readline())
a=sorted(map(int,stdin.readline().split()))
if a[0]==a[-1]:
    print(0)
    exit(0)
m1=max(a);ans=0
vis=[0]*(m1+1)
for v in a:
    if not vis[v]:
        ans+=1
        for mul in range(v,m1+1,v):
            vis[mul]=1
stdout.write(str(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
ab=[]
for i in Counter(a):
  if Counter(a)[i]==1:
    ab.append(i)
ans=set([])
a.sort()
ans_count=0
N=10**9+1
ab=set(ab)
if len(ab)==0:
  print(0)
else:
  for i in range(n):
    if (not a[i] in ans) and (a[i] in ab):
      N=a[i]
      count=1
      ans.add(N)
      ans_count+=1
      while N*count<10**6+1:
        count+=1
        ans.add(N*count)
  print(ans_count)

Submission status: Wrong Answer

Solution code:
import math

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

a.sort()

is_prime = [True]*(10**6 + 1)

is_prime[0] = False

for i in a:
    for j in range(2 * i, max(a)+1, i):
        is_prime[j] = False

result = 0

for e in set(a):
    if is_prime[e]:
#        print('e = {}'.format(e))
        result += 1

print(result)

Submission status: Wrong Answer

Solution code:
from collections import Counter


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

    A_set = set(A)
    A_dict = Counter(A)
    A_dict_sort = sorted(A_dict.items())

    for key, count in A_dict.items():
        if count > 1:
            A_set.discard(key)

        k = key * 2

        if key in A_set:
            while k <= max(A):
                A_set.discard(k)
                k += key

    print(len(A_set))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter


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

    A_set = set(A)
    A_dict = Counter(A)
    A_dict_sort = sorted(A_dict.items())

    for key, count in A_dict.items():
        if count > 1:
            A_set.discard(key)
            continue

        k = key * 2

        if key in A_set:
            while k <= max(A):
                A_set.discard(k)
                k += key

    print(len(A_set))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(N):
    if tmp[arr[i]] >= 2:
        continue
    flg = True
    for k in range(1,int(arr[i]**0.5)+1):
        if arr[i] % k == 0:
            if tmp[k] != 0:
                flg = False
                break
            if k != arr[i] // k:
                if tmp[arr[i] // k] != 0 and arr[i] // k != arr[i]:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter


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

    A_set = set(A)
    A_dict = Counter(A)

    for key, count in A_dict.items():
        if count > 1:
            A_set.discard(key)
            continue

        k = key * 2

        if key in A_set:
            while k <= max(A):
                A_set.discard(k)
                k += key

    print(len(A_set))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

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

#a.sort()

is_prime = [True]*(max(a) + 1)

is_prime[0] = False

for i in a:
    for j in range(2 * i, max(a)+1, i):
        is_prime[j] = False

result = 0

for e in set(a):
    if is_prime[e]:
#        print('e = {}'.format(e))
        result += 1

print(result)

Submission status: Wrong Answer

Solution code:
import math

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

a.sort()

is_prime = [True]*(max(a) + 1)

is_prime[0] = False
is_prime[1] = False

for i in a:
    for j in range(2 * i, max(a)+1, i):
        is_prime[j] = False

result = 0

for e in set(a):
    if is_prime[e]:
#        print('e = {}'.format(e))
        result += 1

print(result)

Submission status: Wrong Answer

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

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

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

unique=[]

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

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

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

ans=0
a=list(set(a))
for elem in a:
    if cnt[elem]==0:
        ans+=1

print(ans)