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
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)

    # 約数を列挙　n=10^12までいける
    def make_divisors(n):
        divisors = []

        if 1 in seta:
            return True
        if cnta[n] > 1:
            return True

        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                if i in seta:
                    return True
                    if i != n // i:
                        if n // i in seta:
                            return True

        return False

    ans = 0
    for ai in seta:
        if not make_divisors(ai):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)

    # 約数を列挙　n=10^12までいける
    def make_divisors(n):
        divisors = []

        if 1 in seta:
            return True
        if cnta[n] > 1:
            return True

        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                if i in seta:
                    return True
                if i != n // i:
                    if n // i in seta:
                        return True

        return False

    ans = 0
    for ai in seta:
        if not make_divisors(ai):
            ans += cnta[ai]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)

    # 約数を列挙　n=10^12までいける
    def make_divisors(n):
        divisors = []

        if 1 in seta:
            return True
        if cnta[n] > 1:
            return True

        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                if i in seta:
                    return True
                if i != n // i:
                    if n // i in seta:
                        return True

        return False

    ans = 0
    for ai in seta:
        if not make_divisors(ai):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
c=collections.Counter(A)
if __name__=="__main__":
    if 1 in A:
        if c[1]==1:
            print(1)
        else:
            print(0)
    else:
        A=[]
        for key,value in c.items():
            if value==1:
                A.append(key)

        if len(A)==0:
            print(0)
        else:
            dp=[True for _ in range(10**6+10)]
            for a in A:
                if dp[a]:
                    i=2
                    while i*a<=10**6:
                        dp[i*a]=False
                        i+=1 
            ans=0
            for a in A:
                if dp[a]:
                    ans+=1
            print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
c=collections.Counter(A)
if __name__=="__main__":
    if 1 in A:
        if c["1"]==1:
            print(1)
        else:
            print(0)
    else:
        A=[]
        for key,value in c.items():
            if value==1:
                A.append(key)

        if len(A)==0:
            print(0)
        else:
            dp=[True for _ in range(10**6+10)]
            for a in A:
                if dp[a]:
                    i=2
                    while i*a<=10**6:
                        dp[i*a]=False
                        i+=1 
            ans=0
            for a in A:
                if dp[a]:
                    ans+=1
            print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
c=collections.Counter(A)
A=[]
for key,value in c.items():
    if value==1:
        A.append(key)
if len(A)==0:
    print(0)
else:
    dp=[True for _ in range(10**6+10)]
    for a in A:
        if dp[a]:
            i=2
            while i*a<=10**6:
                dp[i*a]=False
                i+=1
    ans=0
    for a in A:
        if dp[a]:
            ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
import bisect 
from math import floor
import numpy as np
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
double=[]
for i in range(N-1):
    if A[i]==A[i+1] and not(A[i] in double):
        double.append(A[i])
A=np.unique(A)
A=list(A)
for dead in double:
    A.remove(dead)
N=len(A)
ans=0
if N>0:
    ans+=1
    for i in range(1,N):
        a=A[i]
        root=floor(A[i]**0.5)
        flag=bisect.bisect_right(A,root)
        g=1
        for j in range(flag+1):
            if a%A[j]==0:
                g=0
                break
        if g==1:
            ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect 
from math import floor
import numpy as np
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
A=np.array(A)
A=np.unique(A)
N=len(A)
ans=0
if N>0:
    ans+=1
    for i in range(1,N):
        a=A[i]
        root=floor(A[i]**0.5)
        flag=bisect.bisect_right(A,root)
        g=1
        for j in range(flag+1):
            if a%A[j]==0:
                g=0
                break
        if g==1:
            ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect 
from math import floor
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
ans=0
for i in range(N):
    a=A[i]
    root=floor(A[i]**0.5)
    flag=bisect.bisect_right(A,root)
    g=1
    for j in range(flag+1):
        if j!=i and j<N and a%A[j]==0:
            g=0
            break
    for j in [i-1,i+1]:
        if j>=0 and j<N and a%A[j]==0:
            g=0
            break
    if g==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect 
from math import floor
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
ans=0
for i in range(N):
    a=A[i]
    root=floor(A[i]**0.5)
    flag=bisect.bisect_right(A,root)
    g=1
    for j in range(flag+1):
        if j!=i and j<N and a%A[j]==0:
            g=0
            break
    for j in [i-1,i+1]:
        if i>=0 and j<N and a%A[j]==0:
            g=0
            break
    if g==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect 
from math import floor
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
ans=0
for i in range(N):
    a=A[i]
    root=floor(A[i]**0.5)
    flag=bisect.bisect_right(A,root)
    g=1
    for j in range(flag+1):
        if j!=i and j<N and a%A[j]==0:
            g=0
            break
    for j in [i-1,i+1]:
        if j<N and a%A[j]==0:
            g=0
            break
    if g==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect 
from math import floor
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
ans=0
for i in range(N):
    a=A[i]
    root=floor(A[i]**0.5)
    flag=bisect.bisect_left(A,root)
    # if flag==0 and i!=0:
    #     break
    # if flag==0:
    #     ans+=1
    #     continue
    g=1
    for j in range(flag+1):
        if j!=i and j<N and a%A[j]==0:
            g=0
            break
    for j in range(i-1,i+2):
        if j!=i and j<N and a%A[j]==0:
            g=0
            break
    if g==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect 
from math import floor
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
ans=0
for i in range(N):
    a=A[i]
    root=floor(A[i]**0.5)
    flag=bisect.bisect_left(A,root)
    # if flag==0 and i!=0:
    #     break
    # if flag==0:
    #     ans+=1
    #     continue
    g=1
    for j in range(flag+2):
        if j!=i and j<N and a%A[j]==0:
            g=0
            break
    if g==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#from bisect import bisect_right #二分探索用のモジュール bisect_right(a_list,value)

#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。

# = map(int,input().split())

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

# = [list(map(int,input().split())) for _ in range(XXXX)]

n = int(input())

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

aset = set(alist)

exit()

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

C=Counter(A)

A=set(A)

MAX_A=10**6

X=[0]*(MAX_A+1)

for a in A:
    for i in range(a,MAX_A+1,a):
        X[i]+=1

ans=len([a for a in A if (X[1]==1) and (C[a]==1)])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections

n = int(input())
aa = np.array(list(map(int,input().split())))
c = collections.Counter(aa)
a=np.unique(aa)
amax=max(a)+1
ah=[0]*amax

for i in a:
    if c[i]>=2:
        continue
    for j in range(i,amax,i):
        ah[j]+=1

an=0
for i in a:
    if ah[i]==1:
        an+=1
print(an)

Submission status: Wrong Answer

Solution code:
import sys

N=int(sys.stdin.readline())
array=sorted([int(x) for x in sys.stdin.readline().split()])
duplicate={}
sieve=set()
#check for duplicates
for i in array:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1
for i in array:
	if i in sieve:
		break
	else:
		for j in range(2*i,10**6,i):
			sieve.add(j)

for i in range(len(array)):
	if array[i] in sieve:
		array[i]=False
		
for i in range(len(array)):
	if array[i]:
		if duplicate[array[i]]>1:
			array[i]=False
		
array=[x for x in array if x!=False]

print(len(array))

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
num=[True for i in range(a[-1]+1)]
for i in range(n):
  if num[a[i]]:
    t=a[-1]%a[i]==0
    for j in range(a[-1]//a[i]+t):
      if j<2:
        continue
      num[a[i]*j]=False
    if i==n-1:
      pass
    elif a[i]==a[i+1]:
      num[a[i]]=False
    else:
      pass
  else:
    continue
ans=0
for i in range(n):
  if num[a[i]]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
num=[True for i in range(a[-1]+1)]
for i in range(n):
  if num[a[i]]:
    for j in range(a[-1]//a[i]):
      if j<2:
        continue
      num[a[i]*j]=False
    if i==n-1:
      pass
    elif a[i]==a[i+1]:
      num[a[i]]=False
    else:
      pass
  else:
    continue
ans=0
for i in range(n):
  if num[a[i]]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
a.sort()
p=0
cross=0
for i in range(n-1):
  if a[i]==p:
    continue
  elif a[i]==a[i+1]:
    p=a[i]
    cross+=1
a=np.array(a)
ans=0
while True:
  if len(a)!=0:
    first=a[0]
    ans+=1
    a=a[1:]
  b=a.copy()
  if len(b)==0:
    break
  b%=first
  a=a[b!=0]
print(ans-cross)

Submission status: Wrong Answer

Solution code:
import sys
N=int(sys.stdin.readline())
array=sorted([int(x) for x in sys.stdin.readline().split()])
duplicate={}
#check for duplicates
for i in array:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1
#loop from the list to check which are divisible and mark them as False
for i in range(N):
	if array[i]==False:
		break
	for j in range(i+1,N):
		if array[j]==False:
			break
		if array[j]%array[i]==0:
			array[j]=False

#remove all False
array=[x for x in array if x!=False]

#after that if the only remaining are duplicates, mark them as False
for i in range(len(array)):
	if duplicate[array[i]]>1:
		array[i]=False

#remove all False
array=[x for x in array if x!=False]

print(len(array))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [True]*(max(A)+1)
for i in range(1, max(A)+1):
  if i in A and dp[i] != False:
    for j in range(i,max(A)+1):
      if j % i == 0 and j != i:
        dp[j] = False
cnt = 0
for a in A:
  if dp[a] == True:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
sum = 0
for i in range(n):
    f = True
    if a[i] % a[i-1] == 0:
        continue
    for j in range(i+1,n):
        if a[i] % a[j] == 0:
            f = False
            break
    if f:
        sum += 1
print(sum)

Submission status: Wrong Answer

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

sum = 0
for i in range(n):
    #print(i)
    f = True
    if a[i] not in a[:i] and a[i] not in a[i+1:]:
        for j in range(2,a[i]//2 + 1):
            if a[i]%j == 0:
                if j in a:
                    #print(i,j)
                    f = False
                    break
    else:
        f = False
    if f:
        sum += 1

print(sum)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
ans=[]
a.sort()
for i in range(1,n):
  for x in a[:i]:
    if a[i]%x==0:
      ans.append(x)
      break
print(len(ans))

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
memo = [0] * (10**6 + 1)
f = defaultdict(int)
for i in a:
    if f[i]:
        continue
    f[i] = 1
    for j in range(i, 10**6+1, i):
        memo[j] += 1

ans = 0
for i in a:
    if memo[i] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
aa = []
a.sort()
ans = 0
flag = 0
if n == 1:
    print(0)
else:
    while len(a) >= 1:
        for i in range(1, len(a)):
            if a[i] % a[0] == 0:
                if a[i] == a[0]:
                    flag = 1
            else:
                aa.append(a[i])
        if flag != 1:
            ans += 1
        a = aa[:]
        aa = []

    print(ans)

Submission status: Wrong Answer

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

a.sort()
num = 0
cnt = 1
flag = 0
if n == 1:
    print(0)
else:
    while num <= len(a) - 2:
        while cnt < n:
            if a[cnt] % a[num] == 0:
                if a[cnt] == a[0]:
                    flag = 1
                a.pop(cnt)
                n -= 1
            else:
                cnt += 1
        if flag == 1:
            a.pop(num)
            n -= 1
            flag = 0
        else:
            num += 1
        cnt = num + 1

    print(len(a))

Submission status: Wrong Answer

Solution code:
_ = int(input())
A = list(set(map(int, input().split())))
n = len(A)
A.sort()
ans = 0
D = [True]*(A[-1]+1)
for i in range(n-1):
    if D[A[i]]:
        for j in range(A[-1]//A[i]+1):
            D[A[i]*j] = False
        ans += 1
if D[A[-1]]: ans += 1
print(ans if n>1 else 0)

Submission status: Wrong Answer

Solution code:
_ = int(input())
A = list(set(map(int, input().split())))
n = len(A)
A.sort()
D = [True]*n
if n==1:
    print(0)
else:
    for i in range(n):
        if D[i] and 0<=i<n-1:
            for j in range(i+1,n):
                if A[j]%A[i]==0:
                    D[j] = False
    print(sum(D))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
A.sort()
D = [True]*n
if len(set(A))==0:
    print(0)
else:
    for i in range(n):
        if D[i] and 0<=i<n-1:
            for j in range(i+1,n):
                if A[j]%A[i]==0:
                    D[j] = False
print(sum(D))

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    ma = A[-1]
    hurui = [0] * (ma + 10)
    for a in A:
        if hurui[a] == 0:
            hurui[a] = 1
        else:
            hurui[a] = 10

    for a in A:
        if hurui[a] == 0:
            continue

        for i in range(a*2, ma+10, a):
            hurui[i] = 0

    print(sum(hurui) % 10)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

data = [True]*N

for i in range(N):
    if data[i]:
        for j in range(i,N):
            if A[i]==A[j]:
                data[i]=False
                data[j]=False
            elif A[j]%A[i]==0:
                data[j]=False

print(data.count(True))

Submission status: Wrong Answer

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

table = [0]*N

for i in range(N):
    for j in range(i+2):
        # print(i,j)
        if i!=j and A[i]%A[j]==0:
            table[i]=1
            break
        if A[i]/2 <= A[j]:
            if i == (N-1):
                if A[i-1] == A[i]:
                    table[i] = 1
            elif A[i] == A[i-1] or A[i] == A[i+1]:
                table[i] = 1
            break

# print(table)
print(table.count(0))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n=int(input())
alist=list(map(int,input().split()))
a_sort=sorted(alist,reverse=True)
ans=0


def amari(val,i):
  for j in range(n-i-1):
    val2=a_sort[n-j-1]
    k=int(val1%val2)
    if k==0:
      return 0
      break
  return 1 


for i in range(n):
  val1=a_sort[i]
  if amari(val1,i)==0:
    continue
  else:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import time

def main():
    N = int(input())
    As = list(map(int, input().split()))
    As.sort()
    made = As[-1]
    lis = [True for _ in range(1, made+1)]
    for i in As:
        for j in range(2, int(made/i)+1):
            if lis[i*j-1] == False:
                continue
            lis[i*j-1] = False
    answer = len([int(x) for x in As if lis[x-1]])

    print(answer)

if __name__ == '__main__':
    #start = time.time()
    main()
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

Submission status: Wrong Answer

Solution code:
import sys
import time

def main():
    N = int(input())
    As = list(map(int, input().split()))
    As.sort()
    made = As[-1]
    lis = [True for _ in range(1, made+1)]
    for i in As:
        for j in range(2, int(made/i)+1):
            if lis[i*j-1] == False:
                continue
            lis[i*j-1] = False
    answer = len([int(x) for x in As if lis[x-1]])

    if answer == len(As):
        print(0)
    else:
        print(answer)

if __name__ == '__main__':
    #start = time.time()
    main()
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
Ad = {}
for a in A:
    Ad[a] = Ad.get(a, 0) + 1
A, maxA, ans = sorted(Ad.keys()), max(Ad.keys()), 0

for a in A:
    if Ad[a] == 1:
        ans, m = ans + 1, 2
        if a == 1:
            break
        while a * m <= maxA:
            if a * m in Ad:
                Ad[a * m] = 0
            m += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
Ad = {}
for a in A:
    Ad[a] = Ad.get(a, 0) + 1
A, maxA, ans = sorted(Ad.keys()), max(Ad.keys()), 0

for a in A:
    if Ad[a] == 1:
        ans, m = ans + 1, 2
        while a * m <= maxA:
            if a * m in Ad:
                Ad[a * m] = 0
            m += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
aas = sorted(list(map(int, input().split())))
aas_len = len(aas)
if aas_len == 1:
    print(0)
    exit()
aas_max = aas[-1]
arr = [1]*(aas_max+1)
for i in range(aas_len):
    if arr[aas[i]] == 0:
        continue
    if arr[aas[i]] == 1:
        arr[aas[i]] = 2
    else:
        arr[aas[i]] = 0
        continue
    idx = aas[i]*2
    while idx <= aas_max:
        arr[idx] = 0
        idx += aas[i]
res = 0
for i in aas:
    if arr[i] != 0:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
aas = sorted(list(set(list(map(int, input().split())))))
aas_len = len(aas)
if aas_len == 1:
    print(0)
    exit()
aas_max = aas[-1]
arr = [1]*(aas_max+1)
for i in range(aas_len):
    if arr[aas[i]] == 0:
        continue
    idx = aas[i]*2
    while idx <= aas_max:
        arr[idx] = 0
        idx += aas[i]
res = 0
for i in aas:
    if arr[i] == 1:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
aas = list(set(sorted(list(map(int, input().split())))))
if len(aas) == 1:
    print(0)
    exit()
aas_max = aas[-1]
i = 0
while i != len(aas):
    j = i + 1
    while j != len(aas):
        if aas[j]%aas[i] == 0:
            del aas[j]
        else:
            j += 1
    i += 1
print(len(aas))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

vals, cnts = np.unique(A, return_counts=True)

if len(vals) == 1:
    print(0)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(max(A) + 1, dtype=int)
    for x in vals:
        sat[2 * x::x] = 0
    ans = ((sat[vals] == 1) & (cnts == 1)).sum().item()
    print(ans)

# 5
# 2 2 2 3 3
# 5
# 1 1 1 1 2

Submission status: Wrong Answer

Solution code:
import numpy as np

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

vals, cnts = np.unique(A, return_counts=True)

if len(vals) == 1:
    print(0)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(max(A) + 1, dtype=int)
    for x in vals:
        sat[2 * x::x] = 0
    ans = sum(cnt for val, cnt in zip(vals, cnts) if sat[val])
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = sorted(list(set(A)))
V = max(A) + 1

if len(A) == 1:
    print(0)
elif 1 in A:
    print(1)
else:
    sat = np.ones(V, dtype=int)
    for a in A:
        sat[2 * a::a] = 0
    print(sum(1 for a in A if sat[a]))

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    a = sorted(a)
    if len(a) == 1:
        return "1"
    ans = [a[0]]
    for _a in a[1:]:
        for b in ans:
            if _a % b == 0:
                break
        else:
            ans.append(_a)
    return str(len(ans) - (a[0] == a[1]))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  a_max = a[-1]
  b = 0
  db = [0] * a_max
  for i in range(n-1):
    if a[i] != a[i+1]:
      db[a[i]-1] = 1
  if n > 1 and a[-1] != a[-2]:
    db[-1] = 1
  for i in a:
    t = 2
    while(i * t <= a_max):
      db[i*t-1] = 0
      t += 1
  print(sum(db))
  

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  a_max = a[-1]
  b = 0
  db = [0] * a_max
  for i in a:
    if i != b:
      db[i-1] = 1
      b = i
  for i in a:
    t = 2
    while(i * t <= a_max):
      db[i*t-1] = 0
      t += 1
  print(sum(db))
  

if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

    import math
    import numpy as np


    A_sorted = np.sort(A)

    cnt1 = 0
    cnt2 = 0
    for i in range(1, N):
        for j in range(N):
            if A_sorted[i] // A_sorted[j] == 0:
                break
            elif i > j:
                if A_sorted[i] % A_sorted[j] == 0 and A_sorted[i] != A_sorted[j]:
                    cnt1 += 1
                    break

                elif A_sorted[i] == A_sorted[j]:
                    cnt2 += 1
                    break

    if cnt2 == 0:
        print(N-cnt1)
    else:
        print(N-cnt1-cnt2-1)


if __name__ =='__main__':
    main()

Submission status: Wrong Answer

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

    import math
    import numpy as np


    A_sorted = np.sort(A)

    cnt1 = 0
    cnt2 = 0
    for i in range(1, N):
        for j in range(N):
            if i > j:
                if A_sorted[i] % A_sorted[j] == 0 and A_sorted[i] != A_sorted[j]:
                    cnt1 += 1
                    break

                elif A_sorted[i] == A_sorted[j]:
                    cnt2 += 1
                    break

    if cnt2 == 0:
        print(N-cnt1)
    else:
        print(N-cnt1-cnt2-1)


if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()
L = max(A)

dp = [1] * (L + 1)
dp[0] = 0
num_list = [0] * (L + 1)

for i in A:
    if num_list[i] == 0:
        for j in range(i * 2, L + 1, i):
            dp[j] = 0
    num_list[i] = 1

ans = 0
for i in range(L + 1):
    if num_list[i] == 1 and dp[i] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

if n != 1:
    if a[0] != a[1]:
        counter += 1
        set_factor.add(a[0])

    for i in range(1, n - 1):
        back = a[i - 1]
        forward = a[i + 1]
        if a[i] != back:
            if a[i] != forward:
                for j in range(1, int(a[i] ** (1/2)) + 1):
                    if a[i] % j == 0:
                        high_factor = a[i] // j
                        if j in set_factor or high_factor in set_factor:
                            break
                else:
                    counter += 1
            set_factor.add(a[i])

    if a[n - 2] != a[n - 1]:
        for j in range(1, int(a[n - 1] ** (1/2)) + 1):
            if a[n - 1] % j == 0:
                high_factor = a[n - 1] // j
                if j in set_factor or high_factor in set_factor:
                    break
        else:
            counter += 1
else:
    counter = 1
print(counter)

Submission status: Wrong Answer

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

    import math
    import numpy as np


    A_sorted = np.sort(A)

    cnt1 = 0
    cnt2 = 0
    for i in range(N):
        for j in range(N):
            if i > j:
                if A_sorted[i] % A_sorted[j] == 0 and A_sorted[i] != A_sorted[j]:
                    cnt1 += 1
                    break

                elif A_sorted[i] == A_sorted[j]:
                    cnt2 += 1
                    break

    if cnt2 == 0:
        print(N-cnt1)
    else:
        print(N-cnt1-cnt2-1)


if __name__ =='__main__':
    main()