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:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1
    A = list(set(A))
    A.sort()

    if count[1] == 1:
        print(1)
        return
    if count[1] > 1:
        print(0)
        return

    sup = max(A)+1
    Not_Divisible = [True] * sup
    Not_Divisible[0] = False


    for a in A:
        if Not_Divisible[a]:
            for i in range(a*2,sup,a):
                Not_Divisible[i] = False
        if a > sup ** 0.5:
            break
    
    ans = 0
    for a in A:
        if Not_Divisible[a] and count[a] == 1:
            ans += 1

    print(ans)
            


    
main()

Submission status: Wrong Answer

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

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    while i * ai <= x:
        dp[i * ai] += 1
        if dp[i * ai] >= 2:
            break
        i += 1

ans = 0
for ai in a:
    if dp[ai] <= 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

if N == 1:
  print(1)
  exit(0)
#
A = list(set(A))
N = len(A)
if N == 1:
  print(0)
  exit(0)
#
A.sort()
ans = 0

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

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
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    if len(set(A)) == 1:
        print(0)
        return
    A.sort()
    from collections import defaultdict 
    #isntDiv[x]:=Tureのときxは他の要素で割り切れない
    isntDiv = defaultdict(lambda: 1) 
    cnt = 0
    #最小の要素は他の要素で割り切れない
    isntDiv[A[0]] = 1
    for i in A:
        if isntDiv[i]:
            cnt += 1
            for j in range(2*i, A[-1]+1 , i):
                isntDiv[j] = 0
    print(cnt) 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if N == 1:
  print(1)
  exit(0)
#
A = list(set(A))
N = len(A)
if N == 1:
  print(0)
  exit(0)
#
A.sort()
ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
"""
考え方のポイント
・自分以外では割り切れないような数の個数を求める
　→ 数列の各項に対して〇（割り切れない）×がついていって、〇の個数を数える
・[2, 2]みたいな入力は、他の数で割り切れるようになるので、同じ数が入っていると絶対に×になる。

まずは入力が全部異なる前提で進める。
範囲内の整数からなる全て配列dを用意する。
→ 入力の数列を約数としてもつ数にチェックをしていく（Anに2が含まれていれば、2の倍数全てにチェック（+1)する）
→ チェック後にd[i]をみたとき、d[i]の約数がan中に何個存在するかが示されていることになる。（2∈Aiならd[5](=6)の値は必ず1以上になってる)
"""
N = int(input())
An = [int(i) for i in input().split()]
An.sort()
max_val = 10**6
d = [0] * max_val


# O(N) = O(2*10^5)
# d[i]のうち、配列の値の位置を+1しとく。d[0]は1の約数、d[1]は2の約数を示すことに注意。
for i in An:
    d[i-1] += 1
    # O(MlogM) = 6*10^6
    # [2, 2]などの重複がない場合（既にカウントされているものではない場合)
    if(d[i-1] == 1):
        # 倍数の位置にも2としておいて以降はみないようにする
        for val in range(i*2, max_val, i):
            d[val-1] = 2

print(d.count(1))

Submission status: Wrong Answer

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

x = max(a)
dp = [0] * x
for ai in a:
    i = 1
    while i * ai < x:
        dp[i * ai - 1] += 1
        i += 1

ans = 0
for ai in a:
    if dp[ai-1] <= 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    a.sort()
    ans = []
    import collections
    cnt = collections.Counter(a)
    set_a = set(a)
    dq = collections.deque(set_a)

    while len(dq) > 0:
        now = dq.popleft()
        if cnt[now] > 1:
            continue
        for i in range(len(dq)):
            tmp = dq.popleft()
            if tmp % now == 0:
                continue
            if cnt[tmp] > 1:
                continue
            dq.append(tmp)

        ans.append(now)
    # print(len(dq))




    print(len(ans))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    while i * ai <= x:
        dp[i * ai] += 1
        if dp[i * ai] == 5:
            break
        i += 1

ans = 0
for ai in a:
    if dp[ai] <= 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    while i * ai <= x:
        dp[i * ai] += 1
        if dp[i * ai] == 2:
            break
        i += 1

ans = 0
for ai in a:
    if dp[ai] <= 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
"""
考え方のポイント
・自分以外では割り切れないような数の個数を求める
　→ 数列の各項に対して〇（割り切れない）×がついていって、〇の個数を数える
・[2, 2]みたいな入力は、他の数で割り切れるようになるので、同じ数が入っていると絶対に×になる。

まずは入力が全部異なる前提で進める。
範囲内の整数からなる全て配列dを用意する。
→ 入力の数列を約数としてもつ数にチェックをしていく（Anに2が含まれていれば、2の倍数全てにチェック（+1)する）
→ チェック後にd[i]をみたとき、d[i]の約数がan中に何個存在するかが示されていることになる。（2∈Aiならd[5](=6)の値は必ず1以上になってる)
"""
N = int(input())
An = [int(i) for i in input().split()]
An.sort()
max_val = 10**6
d = [0] * max_val


# O(N) = O(2*10^5)
# d[i]のうち、配列の値の位置を+1しとく。d[0]は1の約数、d[1]は2の約数を示すことに注意。
for i in An:
    d[i-1] += 1
    # O(MlogM) = 6*10^6
    # [2, 2]などの重複がない場合（既にカウントされているものではない場合）、倍数のところにチェックをつける
    # 重複がある場合は上の行で既に+1されているので、以降の処理はやらなくていい
    for val in range(i*2, max_val, i):
        d[val-1] += 1

print(d.count(1))

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sorted(il())

    cnt = collections.Counter(A)
    multiple = set()
    ret = 0
    maximum = max(A)
    for a in A:
        # 約数を既に使用済みの場合はcontinue
        if a in multiple:
            continue

        # 同じ数字が存在する場合はcontinue
        if cnt[a] != 1:
            continue

        ret += 1
        i = 1
        # 使用済みの整数の倍数を列挙
        while a * i <= maximum:
            multiple.add(a*i)
            i += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sorted(il())

    cnt = collections.Counter(A)
    multiple = set()
    ret = 0
    for a in A:
        # 約数を既に使用済みの場合はcontinue
        if a in multiple:
            continue

        # 同じ数字が存在する場合はcontinue
        if cnt[a] != 1:
            continue

        ret += 1
        i = 1
        # 使用済みの整数の倍数を列挙
        while a * i <= max(A):
            multiple.add(a*i)
            i += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=input()
arr=[int(i) for i in input().strip().split(' ')]
ans=0
# for i in range(len(arr)):
#     for j in range(len(arr)):
#         if i==j:
#             continue
#         if arr[i]%arr[j]==0:
#             break
#     else:
#         ans+=1
# print(ans)
dic1={}
dic2={}
for i in arr:
    dic1[i]=i
    dic2[i]=i
for i in dic1:
    for j in dic2:
        if i==j:
            continue
        if dic1[i]%dic2[j]==0:
            break
    else:
        ans+=1    
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

a.sort()
cnt = 0
dp = [True] * (a[-1]+1)
pre = -1
flg = False

for i in a:
    if dp[i] == True:
        cnt += 1
    if i == pre:
        if flg is True:
            continue
        else:
            cnt -= 1
            flg = True
    else:
        flg = False
        for j in range(1, a[-1]//i+1):
            dp[i*j] = False
    pre = i

print(cnt)

Submission status: Wrong Answer

Solution code:
#170D
def main():
    import sys
    #from collections import deque
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A.sort()
    judge = [True for i in range(len(A))]
    lena = len(A)
    #A = deque(A)
    def era(A):
        if len(A)==1:
            print(0)
            return
        for i in [idx for idx, x in enumerate(judge) if x==True]:
            for j in [idx for idx, x in enumerate(judge) if x==True]:
                if i ==j:
                    continue
                if A[j] % A[i]==0:
                    #print(A[j], A[i])
                    judge[j] = False
        #print(A)
        #print(judge)
        print(judge.count(True))
                    
                
    
    era(A)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())
an = [list(map(int, input().split()))]

an_n = np.array(an).reshape(-1)
an_n.sort()
# an_n2 = an_n
an_0 = an[0]
an_len = len(an_0)
for i, num in enumerate(an_n):
    if an_n[i] == 0:
        continue
    for j in range(i+1, an_len-i):
        if (an_n[j] == num):
            an_n[i] = 0
#         print(num, an_n[j])
        if an_n[j] % num == 0:
            an_n[j] = 0
rs = np.where(an_n != 0)
rs_0 = rs[0]      
print(len(rs_0))

Submission status: Wrong Answer

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

chk_list = sorted(A)
new_list = []
n = 1
while n < len(chk_list):
    new_list = chk_list[:n]
    for i in range(n,len(chk_list)):
        if chk_list[i]%chk_list[n-1] == 0:
            continue
        new_list.append(chk_list[i])
    chk_list = new_list
    new_list = []
    n += 1

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

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors = []
    upper_divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)

    upper_divisors.reverse()
    return lower_divisors + upper_divisors


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

if len(set(a)) == 1:
    print(0)
    exit()
a.sort()
cnt = 0
pre = -1
flg = False

for i in a:
    if i == pre:
        if flg is True:
            continue
        else:
            cnt -= 1
            flg = True
    else:
        flg = False
    l = set(make_divisors(i))
    if len(l & b) == 0:
        cnt += 1
    add(i)
    pre = i
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True for _ in range(a[n-1])]
for val in set(a):
    for i in range(2,a[n-1]+1,val):
        dp[i-1]=False
ans = 0
for val in a:
    if dp[val-1] and a.count(val)==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True for _ in range(a[n-1])]
for val in set(a):
    for i in range(2,a[n-1],val):
        dp[i-1]=False
ans = 0
for val in a:
    if dp[val-1] and a.count(val)==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import Counter
c=Counter(a)
dp=(10**6+1)*[0]
ans=0

for ai in a:  
  if dp[ai]==0:
    if c[ai]>1:continue
    ans+=1
  for i in range(1,10**6+1):
    if ai*i<=10**6:
      dp[ai*i]=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True for _ in range(a[n-1])]
for val in set(a):
    temp=2
    for temp in range(2,a[n-1]//val):
        dp[val*temp-1]=False
ans = 0
for val in a:
    if dp[val-1] and a.count(val)==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#170D
def main():
    import sys
    #from collections import deque
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A.sort()
    judge = [True for i in range(len(A))]
    lena = len(A)
    #A = deque(A)
    def era(A):
        if len(A)==1:
            print(0)
            return
        for i in range(lena):
            if judge[i] == False:
                continue
            for j in range(i+1, lena):
                if judge[j] == False:
                    continue
                if A[j] % A[i]==0:
                    #print(A[j], A[i])
                    judge[j] = False
        #print(A)
        #print(judge)
        print(judge.count(True))
                    
                
    
    era(A)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
am = max(a)+1
b = [0]*am
ans = 0
for i in a:
    for j in range(i,am,i):
        if b[j]>=2: break
        b[j]+=1
for i in a:
    if b[i]==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())
an = [list(map(int, input().split()))]
an_n = np.array(an).reshape(-1)
an_n2 = np.array(an).reshape(-1)
cnt = 0
for i, num in enumerate(an_n):
    if num == 0:
        continue
    an_a = np.where(an_n % num == 0)
    t = an_a[0]
    if len(t) > 1:
        ab = an_n[i]
        an_n[t] = 0
        an_n[i] = ab

rs = np.where(an_n2 != 0)
rs_0 = rs[0]
print(len(rs_0))

Submission status: Wrong Answer

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

def slove():
    n = int(input())
    A = list(map(int,input().split()))
    a = [0] * (10**6 + 1)
    for value in A:
        #print(value)
        a[value] += 1
    ans = 0
    count = 0
    #print(a[0:30])
    for item in a:
        #print(item)
        if item == 1:
            #print(item)
            ans += 1
        if item != 0:
            for i in range(count,10**6,count):
                a[i] = 0
            #print(a[0:30])
        count += 1
    print(ans)

if __name__ == "__main__":
    slove()

"""
import sys
input = sys.stdin.readline

def slove():
    n = int(input())
    A = list(map(int,input().split()))
    A = sorted(A)
    ans = 0
    flag = False
    while len(A) != 0:
        ans += 1
        tmp = A.pop(0)
        #print(A)
        k = 0
        for i in range(len(A)):
            if A[i-k] % tmp == 0:
                if A[i-k] == tmp:
                    flag = True
                A.remove(A[i-k])
                k += 1
        if flag:
            ans -= 1
            flag = False
        
    print(ans)


if __name__ == "__main__":
    slove()
"""

Submission status: Wrong Answer

Solution code:
#170D
def main():
    import sys
    #from collections import deque
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A = list(set(A))
    A.sort()
    judge = [True for i in range(len(A))]
    lena = len(A)
    #A = deque(A)
    def era(A):
        if len(A)==1:
            print(0)
            return
        for i in range(lena):
            if judge[i] == False:
                continue
            for j in range(i+1, lena):
                if A[j] % A[i]==0:
                    #print(A[j], A[i])
                    judge[j] = False
        #print(A)
        #print(judge)
        print(judge.count(True))
                    
                
    
    era(A)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
a.sort()
l=[]
d={}
count=0
for i in range(n):
    c=0
    for j in range(1,math.floor(math.sqrt(a[i]))+1):
        if a[i]%j==0:
            if j in d:
                c=1
                break
            if a[i]%(a[i]//j)==0:
                if (a[i]//j) in d:
                    c=1
                    break
    
    if c==0:
        count+=1
    d[a[i]]=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def Yes(x):print("Yes")if x==True else print("No")
n=N()
l=L()
l.sort()
from math import sqrt
ans=0
import collections
c=collections.Counter(l)
if 1 in c:
    print(0)
    quit()
for i in l:
    if c[i]>1:
        continue
    for j in range(2,int(sqrt(i))+1):
        if i%j==0:
            if c[j] or c[i//j]:
                break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

Amax = max(num_list)

dp = np.ones( (Amax+1,), dtype=np.bool8 )
dp2 = np.zeros( (Amax+1,), dtype=np.bool8 )

for i in range(Amax+1):
    if i in num_list:
        for j in range(i+i, Amax+1, i):
            dp[j] = False

for n in num_list:
    dp2[n] = dp[n]

print( sum(dp2) )

Submission status: Wrong Answer

Solution code:
n = int(input())
cnt = [0]*1000001
ans = 0
a = list(map(int,input().split()))
a.sort()

for i in range(n):
    j = a[i]
    while j<=1000000:
        if cnt[j]<2:
            cnt[j]+=1
            j+=a[i]
        else:
            break
for i in range(n):
    if cnt[a[i]]<2: ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
cnt = [0]*1000001
ans = 0
a = list(map(int,input().split()))
a.sort()

for i in range(n):
    j = a[i]
    while j<1000000:
        if cnt[j]<2:
            cnt[j]+=1
            j+=a[i]
        else:
            break
for i in range(n):
    if cnt[a[i]]<2: ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#170D
def main():
    import sys
    #from collections import deque
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A = list(set(A))
    A.sort()
    #A = deque(A)
    def era(A):
        if len(A)==1:
            print(0)
            return
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                if A[j] % A[i]==0:
                    #print(A[j], A[i])
                    A[j] =0
            while 0 in A:
                A.remove(0)
        #print(A)
        print(len(A))
                    
                
    
    era(A)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(N)]

A.sort()

for i in range(N):
    if dp[i] < 2:
        p = A[i]
        for j in range(N):
            if dp[j] < 2 and A[j]%p == 0 and A[j] >= p:
                dp[j] += 1
cnt = 0
# for i in range(N):
#     if dp[i] == 1:
#         cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(N)]

A.sort()

for i in range(N):
    if dp[i] < 2:
        p = A[i]
        for j in range(i-1, N):
            if A[j]%p == 0 and A[j] >= p:
                dp[j] += 1
cnt = 0
for i in range(N):
    if dp[i] == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

Amax = max(num_list)

dp = np.ones( (Amax+1,), dtype=np.bool8 )

for i in range(Amax+1):
    if dp[i]:
        if i in num_list:
            for j in range(i+i, Amax+1, i):
                dp[j] = False

print( sum(dp[np.asarray(num_list)])  )

Submission status: Wrong Answer

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

if N == 1:
    print(1)
else:
  for i in range(N-1):
    for j in range(i+1, N):
      if A[i] % A[j] == 0:
        cnt-=1
        break
    cnt += 1
  if A[-2] % A[-1] != 0:
    cnt += 1
  print(cnt)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
lst = []
for k,v in Counter(A).items():
    if v==1:
        lst.append(k)
if len(lst)==0:
    print(0)
elif 1 in lst:
    print(1)
else:
    lst.sort()
    ans = 0
    mx = 10**6+5
    er = [False] + [True]*mx
    for l in lst:
        if er[l]:
            ans += 1
            i = 0
            while True:
                er[i*l] = False
                i += 1
                if i*l > mx:
                    break
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())
an = [list(map(int, input().split()))]
an_n = np.array(an).reshape(-1)
cnt = 0
for num in an_n:
    an_a = np.where(an_n % num == 0)
    it = an_a[0]
    if len(it) == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
if 1 in A:
    print(1)
else:
    c = Counter(A)
    lst = []
    for k,v in c.items():
        if v==1:
            lst.append(k)
    if len(lst)==0:
        print(0)
    else:
        lst.sort()
        mx = max(lst)
        ans = 0
        err = [False] + [True]*(mx)
        for l in lst:
            if err[l]:
                ans += 1
                i = 0
                while True:
                    err[l*i] = False
                    i += 1
                    if l*i > mx:
                        break
        print(ans)

Submission status: Wrong Answer

Solution code:
#170D
def main():
    import sys
    from collections import deque
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A = list(set(A))
    A.sort()
    A = deque(A)
    def era(A):
        if len(A)==1:
            print(0)
            return
        for i in range(len(A)):
            for j in range(len(A)-1, i, -1):
                if A[j] % A[i]==0:
                    #print(A[j], A[i])
                    A.pop()
                    break
        print(len(A))
                    
                
    
    era(A)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np

def main():
    MOD = 10**9+7
    n = int(input())
    A = list(map(int,input().split()))

    A.sort()
    T = A[-1]+1

    dp = [True] * T

    d = defaultdict(int)

    for a in A:
        d[a] += 1
        if dp[a]:
            for j in range(2*a,T,a):
                dp[j] = False

    ans = 0
    
    for a in A:
        if d[a] == 1 and dp[a] == True:
            ans += 1

    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
if 1 in A:
    print(0)
else:
    c = Counter(A)
    lst = []
    for k,v in c.items():
        if v==1:
            lst.append(k)
    if len(lst)==0:
        print(0)
    else:
        lst.sort()
        mx = max(lst)
        ans = 0
        err = [False] + [True]*(mx)
        for l in lst:
            if err[l]:
                ans += 1
                i = 0
                while True:
                    err[l*i] = False
                    i += 1
                    if l*i > mx:
                        break
        print(ans)

Submission status: Wrong Answer

Solution code:
I = lambda :list(map(int,input().split()))

n,=I()
l = sorted(I())
g=[0]*(10**6+1)
an=0
for i in range(n):
  x=l[i];f=1
  for j in range(1,int(x**0.5)+1):
    if x%j==0:
      if g[j] or g[x//j]:
        f=0;break
  g[x]=1
  if f and (i!=n-1 and l[i+1]!=l[i]):
    an+=1
print(an)

Submission status: Wrong Answer

Solution code:
import collections


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

    A.sort()

    sames = 0
    C = collections.Counter(A)
    for v in C.values():
        if v > 1:
            sames += 1

    a_max = A[-1]
    dp = [True] * a_max
    A = set(A)

    for a in A:
        if dp[a - 1]:
            tmp_a = a * 2
            while tmp_a < a_max:
                dp[tmp_a - 1] = False
                tmp_a += a

    r = 0
    for a in A:
        if dp[a - 1]:
            r += 1

    print(r - sames)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if N == 1:
    print(1)
else:
  for i in range(N-1):
    for j in range(i+1, N):
      if A[i] % A[j] == 0:
        cnt-=1
        break
    cnt += 1
  if A[-1] != A[-2]:
    cnt += 1
  print(cnt)

Submission status: Wrong Answer

Solution code:
#170D
def main():
    import sys
    from collections import deque
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A = list(set(A))
    A.sort(reverse=True)
    A = deque(A)
    def era(A):
        if len(A)==1:
            print(0)
            return
        for i in range(len(A)):
            for j in range(len(A)-1, i, -1):
                if A[i] % A[j]==0:
                    #print(A[j], A[i])
                    A.popleft()
                    break
        print(len(A))
                    
                
    
    era(A)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections


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

    A.sort()

    sames = 0
    C = collections.Counter(A)
    for v in C.values():
        if v > 1:
            sames += 1

    a_max = A[-1]
    dp = [True] * a_max
    A = set(A)

    for a in A:
        if dp[a - 1]:
            tmp_a = a * 2
            while tmp_a < a_max + 1:
                dp[tmp_a - 1] = False
                tmp_a += a

    r = 0
    for a in A:
        if dp[a - 1]:
            r += 1

    print(r - sames)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
I = lambda :list(map(int,input().split()))

n,=I()
l = sorted(I())
g=[0]*(10**6+1)
an=0
for i in range(n):
  x=l[i];f=1
  for j in range(1,int(x**0.5)+1):
    if x%j==0:
      if g[j] or g[x//j]:
        f=0;break
  g[x]=1
  if f:
    an+=1
print(an)

Submission status: Wrong Answer

Solution code:
#170D
def main():
    import sys
    from collections import deque
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A = list(set(A))
    A.sort(reverse=True)
    A = deque(A)
    def era(A):
        if len(A)==1:
            print(0)
            return
        for i in range(len(A)):
            for j in range(len(A)-1, i, -1):
                if A[i] % A[j]==0:
                    #print(A[j], A[i])
                    A.popleft()
        print(len(A))
                    
                
    
    era(A)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
lst = []
for k,v in Counter(A).items():
    if v==1:
        lst.append(k)
if len(lst)==0:
    print(0)
else:
    lst.sort()
    ans = 0
    mx = max(lst)+10
    er = [False] + [True]*mx
    for l in lst:
        if er[l]:
            ans += 1
            i = 0
            while True:
                er[i*l] = False
                i += 1
                if i*l > mx:
                    break
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(10 ** 6 + 10)]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 10 ** 6 + 9, a[i]):
            table[j] = False
        if i + 1 < n - 1:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n - 1:
            ans += 1
print(ans)