Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

dp = [False] * (A[-1] + 1)
for a in A:
    dp[a] = True

for idx, a in enumerate(A):
    if A[idx] == A[idx - 1]: dp[a] = False
    for j in range(2, A[-1]//a + 1):
        dp[a * j] = False

count = 0
for d in dp:
    if d:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc170/abc170_d
import sys
from collections import Counter

i2s = sys.stdin.readline().rstrip

def main():
    N = int(i2s())
    A = sorted(map(int, i2s().split(' ')))
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, A[-1] // a + 1):
            if B[a * i]:
                B[a * i] = 0
    print(sum(B.values()))
    return

main()

Submission status: Wrong Answer

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


A = sorted(list(set(A)))
if len(A) == 1:
    print(0)
    sys.exit(0)
dp = [False] * (A[-1] + 1)
for a in A:
    dp[a] = True

for a in A:
    for j in range(2, A[-1]//a + 1):
        dp[a * j] = False

count = 0
for d in dp:
    if d:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=sorted(map(int,input().split()))
L=[A[0]]
if n==1:
    print(1)
else:
    c=0
    if A[0]!=A[1]:
        c=1
    for i in range(n-1):
        #print(str(A[i+1])+'だよ')
        flag=0
        for l in L:
            #print(l)
            if A[i+1] in L:
                flag=1
                break
            if A[i+1]%l==0:
                #print(str(l)+'でわれちゃったから抜けるね')
                flag=1
                break
            if l>=int(A[i+1]//2):
                #print(str(l)+'おおきくなっちゃったから抜けるね')
                break
        if flag==0:
            L.append(A[i+1])
            c+=1
    print(c)
    #print(L)

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
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=list(map(int,input().split()))
m=max(a)
d=[0]*m
for i in a:
    for j in range(2,m+1):
        if i*j>m:
            break
        d[i*j-1]=1
a=set(a)
ans=len(a)
if ans==1:
  print(0)
  exit()
for i in a:
    if d[i-1]==1:
        ans-=1
print(ans)

Submission status: Wrong Answer

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

A.sort()
if len(set(A)) == 1:
    print(0)
    sys.exit(0)
dp = [False] * (A[-1] + 1)
for a in A:
    dp[a] = True

for a in A:
    for j in range(2, A[-1]//a + 1):
        dp[a * j] = False

count = 0
for d in dp:
    if d:
        count += 1
print(count)

Submission status: Wrong Answer

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

A.sort()
if len(set(A)) == 1:
    print(0)
    sys.exit(0)
dp = [False] * (A[-1] + 1)
for a in A:
    dp[a] = True

for i in range(2, A[-1] + 1):
    if i in A:
        for j in range(2, A[-1]//i + 1):
            dp[i * j] = False

count = 0
for d in dp:
    if d:
        count += 1
print(count)

Submission status: Wrong Answer

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

m = max(p)

v = [-1] * (m +1)
c = {}
for i in p:
    if v[i] == -1:
        v[i] = 0
    elif v[i] == 0:
        if i in c:
            c[i] += 1
        else:
            c[i] = 1
    else:
        continue
    for j in range(2,m//i+1):
        if i*j > m:
            break
        v[i*j] = 1
x = 0
for i in p:
    if v[i]:
        x += 1

print(n-x-sum(c.values())-len(c))

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
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=list(map(int,input().split()))
m=max(a)
d=[0]*m
for i in a:
    for j in range(2,m+1):
        if i*j>m:
            break
        d[i*j-1]=1
ans=len(set(a))
if ans==1:
  print(0)
  exit()
for i in a:
    if d[i-1]==1:
        ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = set(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0
if len(a) == 1:
    print(0)
    exit()
for i in a:
    if lst[i] >= 2:  # 配列中のカウントが2以上なら以降の処理を省略
        continue
    else:
        for j in range(1, a_max// i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
            lst[i * j] += 1
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

A.sort()
if len(set(A)) == 1:
    print(0)
    sys.exit(0)
dp = [True] * (A[-1] + 1)

for i in range(2, A[-1] + 1):
    if i in A:
        for j in range(2, A[-1]//i + 1):
            dp[i * j] = False

values = []
for idx, value in enumerate(dp):
    values.append(idx) if value == True else values
print(len(set(A) & set(values)))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = set(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0
for i in a:
    if lst[i] >= 2:  # 配列中のカウントが2以上なら以降の処理を省略
        continue
    else:
        for j in range(1, a_max// i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
            lst[i * j] += 1
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

m = max(p)

v = [-1] * (m +1)
c = {}
for i in p:
    if v[i] == -1:
        v[i] = 0
    elif v[i] == 0:
        if i in c:
            c[i] += 1
        else:
            c[i] = 1
    for j in range(2,m//i+1):
        if i*j > m:
            break
        v[i*j] = 1
x = 0
for i in p:
    if v[i]:
        x += 1

print(n-x-sum(c.values())-len(c))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()  # 直下で数列A中の最大値が欲しいのでソート，後でも同じことしてる．
lst = [0] * (a[-1] + 1)
cnt = 0
for i in a:
    # print(i, end=' ')
    if a.count(i) >= 2:  # 同じ数字が数列Aに2つ以上含まれているなら以降の処理を省略
        # print('continue1')
        continue
    elif lst[i] >= 2:  # 配列中のカウントが2以上なら以降の処理を省略
        # print('continue2')
        continue
    else:
        for j in range(1, a[-1] // i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
            # print(i*j, end=',')
            lst[i * j] += 1
        # print()
# print(lst)
# print(len(lst))
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A.sort()
count = 0
for i in range(n - 1):
    if A[i] % A[i + 1] == 0:
        count += 1
        continue
    place = bisect.bisect(A, math.floor(math.sqrt(A[i])))
    if place == 0:
        continue
    for j in range(place + 1):
        if A[i] % A[j] == 0:
            count += 1
            break
i = n - 1
for j in range(i):
    if A[i] % A[j] == 0:
        count += 1
        break
print(n - count)

Submission status: Wrong Answer

Solution code:
# 
n = int(input())
a = list(map(int, input().split()))
a.sort()  # 直下で数列A中の最大値が欲しいのでソート，後でも同じことしてる．
lst = [0] * (a[-1] + 1)
cnt = 0
for i in a:
    # print(i, end=' ')
    if a.count(i) >= 2:  # 同じ数字が数列Aに2つ以上含まれているなら以降の処理を省略
        # print('continue1')
        continue
    elif lst[i] >= 2:  # 配列中のカウントが2以上なら以降の処理を省略
        # print('continue2')
        continue
    else:
        for j in range(1, a[-1] // i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
            # print(i*j, end=',')
            lst[i * j] += 1
        # print()
# print(lst)
# print(len(lst))
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

A.sort()
count = 0
for i in range(n - 1):
    if A[i] % A[i + 1] == 0:
        count += 1
        continue
    place = bisect.bisect(A, math.floor(math.sqrt(A[i])))
    if place == 0:
        continue
    for j in range(place + 1):
        if A[i] % A[j] == 0:
            count += 1
            break
i = n - 1
place = bisect.bisect(A, math.floor(math.sqrt(A[i])))
for j in range(place + 1):
    if A[i] % A[j] == 0:
        count += 1
        break
print(n - count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

for x in s:
    t = x
    while t <= 10**6:
        P[t] += 1
        t += x

ans = 0

for x in a:
    #print(P[x])
    if P[x] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

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

for x in s:
    t = x
    while t <= 10**6:
        P[t] += 1
        t += x

ans = 0

for x in a:
    print(P[x])
    if P[x] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = list(map(int, input().split()))

ans = []
que = deque(sorted(a))
x = que.popleft()
que.append(x)

while que:
    if len(que) == 1:
        ans.append(que.pop())
        break
    nx = que.popleft()
    if x == nx:
        ans.append(x)
        x = que.popleft()
        que.append(x)
        continue
    if nx % x != 0:
        que.append(nx)

if n == 1:
    print(1)
elif a.count(a[0]) == n:
    print(0)
else:
    print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
A_Max = A[-1]
B = [True]*(A_Max+1)

for i in range(N):
    if B[A[i]]:
        for j in range(2,A_Max+1):
            if A[i] * j > A_Max:
                break
            B[A[i] * j] = False

ans = 0
for i in range(N):
    if B[A[i]]:
            B[A[i]] = False
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
A_Max = A[-1]
B = [True]*(A_Max+1)

for i in range(N):
    if B[A[i]]:
        for j in range(2,A_Max):
            if A[i] * j > A_Max:
                break
            B[A[i] * j] = False

ans = 0
for i in range(N):
    if B[A[i]]:
            B[A[i]] = False
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)

    # divisors.sort()
    return divisors

N = int(input())
A = list(map(int, input().split()))
s = set(A)
ans = 0
for a in s:
  d = make_divisors(a)
  if len(s & d) == 1:
    ans += 1
    
print(ans if len(A) == len(s) else ans - 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    A = Scanner.map_int()
    A.sort(reverse=True)

    MAX = 10 ** 6 + 10
    memo = [False for _ in range(MAX)]
    for i in range(N):
        memo[A[i]] = True
        for j in range(A[i] * 2, MAX, A[i]):
            memo[j] = False
        if i - 1 > 0 and A[i] == A[i - 1]:
            memo[A[i]] = False

    print(sum(memo))


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

U = 10**6
line = [1]*(U+1)
ans = set()
for a in A:
    if line[a]:
        if a in ans:
            ans -= {a}
        else:
            ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	A = np.array(LI())
	A.sort()
	count = 0
	a_max = A[-1]
	dp = [1]*a_max
	for a in A:
		point = dp[a-1]
		if point == 1:
			dp[a-1] = 2
			count += 1
			for i in range(2,a_max):
				if a*i > a_max:
					break
				dp[a*i-1] = 0
		elif point == 2:
			count -= 1
			dp[a-1] = 0
	print(count)






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	n = I()
	A = np.array(LI())
	A.sort()
	count = 0
	a_max = A[-1]
	dp = [1]*a_max
	for a in A:
		point = dp[a-1]
		if point == 1:
			dp[a-1] = 2
			count += 1
			for i in range(2,a_max):
				if a*i > a_max:
					break
				dp[a*i-1] = 0
		elif point == 2:
			count -= 1
			dp[a-1] = 0
	print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
def D():
    N = int(input())
    A = list(map(int, input().split()))
    nums = Counter(A)
    n = max(A)
    dp = [True for i in range(n+1)]
    p = 2
    while (p <= n): 
        if (p in nums and dp[p] == True): 
            for i in range(p*2, n+1, p): 
                # print(i)
                dp[i] = False
        p += 1
    ans = 0
    for num in nums:
        if nums[num] == 1 and dp[num]:
            # print(num)
            ans += 1
    print(ans)

D()

Submission status: Wrong Answer

Solution code:
N=int(input())
#5
A=sorted(map(int,input().split()))
#24 11 8 3 16

dp = [1]*max(A)
l = len(dp)

for a in A:
	if dp[a-1] == 1:
		dp[a-1] = 2
		for i in range(2*a, l+1, a):
			dp[i-1] = 0
	elif dp[a-1] == 2:
		dp[a-1] = 0

sum([1 for a in A if dp[a-1] != 0])

Submission status: Wrong Answer

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

b = [True for i in range(n)]

s = 0
while s < n-1:
    if b[s]:
        for k in range(s+1, n):
            if b[k]:
                b[k] = bool(a[k] % a[s])
        b[s] = a[s+1] != a[s]
    s += 1

print(b)
print(b.count(True))

Submission status: Wrong Answer

Solution code:
def resolve():
    _ = int(input())
    targets = list(map(int, input().split()))

    targets.sort()
    dup = [0 for i in range(10**6+1)]

    for target in targets:
        target_m = target
        while target_m <= 10**6:
            dup[target_m - 1] += 1
            if dup[target_m - 1] >= 2:
                break
            target_m += target

    ans = 0
    targets = set(targets)
    for i in range(len(dup)):
        if (dup[i] == 1) and i+1 in targets:
            ans += 1

    print(ans)

resolve()

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
input = stdin.readline

N = int(input())
A_list = list(map(int, input().split()))
# ans_list =np.ones(N)
# A_list = np.array(A_list)

# for i in range(N-1):
#     for j in range(i+1,N):
#         if A_list[i] %  A_list[j] == 0:
#             ans_list[i] = 0
#             if (A_list[j] %  A_list[i] == 0):
#                 ans_list[j] = 0
#         elif(A_list[j] %  A_list[i] == 0):
#             ans_list[j] = 0
# print(int(np.sum(ans_list)))
A_set = list(set(A_list))
maxA =  A_set[-1]
dp = [1] * (( 10 ** 6) + 1)

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

for elem in A_set:
    for i in range(2 * elem,  10 ** 6 + 1, elem):
        dp[i] = 0

ans = 0
for i in unique:
    if not (dp[i] == 0):
        ans += 1

print(ans)

Submission status: Wrong Answer

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

a.sort()
b = set(a)
ans = 0
for i in range(n):
    if a[i] in b:
        ans += 1
        b.remove(a[i])
        rem = []
        for j in b:
            if j % a[i] == 0:
                rem.append(j)
        for j in rem:
            b.remove(j)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
 
A.sort(reverse=True)
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 len(A) > 1:
    if A[-1] != A[-2]:
      cnt += 1
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

a.sort()
l = a[-1]
dp = [ 1 if i in a else 0 for i in range(l+1)]

for i in range(n):
    tmp = a[i]
    if i < n-1:
        if tmp == a[i+1]:
            dp[tmp] = 0
    if dp[tmp] == 0:
        continue
    g = l//tmp
    for k in range(2,g+1):
        dp[tmp*k] = 0

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
d = {}
for a in A:
    d.setdefault(a,0)#setdefault(key,value):辞書の既存のkeyについては変更せず
    d[a] += 1       #新規のkeyにのみ新たなvalueで要素を追加できる   
#今は({A1:1,A2:1,...An:1}となっている)
A = sorted(set(A))#重複要素なくしてかつ昇順にする
t = [True] * (10 ** 6 + 1)#Aiの制約範囲最大までのTrueのリストを作る
print(d)
for a in A:
    if d[a] > 1:
        t[a] = False
    for i in range(a+a, 10 ** 6 + 1, a):#自分自身を含めないためのa+a
        t[i] = False
print(sum(1 for a in A if t[a]==True))

Submission status: Wrong Answer

Solution code:
def resolve():
    _ = int(input())
    targets = list(map(int, input().split()))

    targets.sort()
    dup = [0 for i in range(10**6+1)]

    for target in targets:
        target_m = target
        while target_m <= 10**6:
            dup[target_m] += 1
            if dup[target_m] >= 2:
                break
            target_m += target

    ans = []
    for i in range(len(dup)):
        if (dup[i] == 1) and i in set(targets):
            ans.append(i)

    print(len(ans))

resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    counter = Counter(A)
    B = [True] * (10 ** 6 + 1)
    ans = 0
    for ai in A:
        if B[ai]:
            for i in range(ai, 10 ** 6 + 1, ai):
                B[i] = False
            if counter[ai] == 1:
                ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

a.sort()
l = a[-1]
dp = [ 1 if i in a else 0 for i in range(l+1)]

for i in range(n):
    tmp = a[i]
    if i < n-1:
        if tmp == a[i+1]:
            dp[tmp] = 0
    if dp[tmp] == 0:
        continue
    g = l//tmp
    for k in range(2,g+1):
        dp[tmp*k] = 0

print(sum(dp))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
 
A.sort(reverse=True)
for i in range(N-1):
  for j in range(i+1, N):
    if A[i] % A[j] == 0:
      cnt-=1
      break
  cnt += 1
      
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
A.sort(reverse=True)
print(A)
for i in range(N-1):
  for j in range(i+1, N):
    if A[i] % A[j] == 0:
      cnt-=1
      break
  cnt += 1
      
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = np.array(sorted(list(map(int, input().split()))))
ans = 0
idx = 0
while True:
  try: a = A[idx]
  except: break
  A = A[A>a][np.where(A[A>a] % a != 0)]
  if len(A)==0 and ans ==0:
    continue
  ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
 
A.sort(reverse=True)
for i in range(N-1):
  ans = True
  for j in range(i+1, N):
    if A[i] % A[j] == 0:
      cnt-=1
      break
  cnt += 1
      
print(cnt)

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n = int(input())
a = list(map(int, input().split()))
a.sort()
if n == 1:
    print(1)
    sys.exit()
if n == 2:
    if a[0] == a[1]:
        print(0)
    elif a[1]%a[0] == 0:
        print(1)
    else:
        print(2)
    sys.exit()

b = []
pre = a[0]
if a[0] != a[1]:
    if pre == 1:
        print(1)
        sys.exit()
else:
    if pre == 1:
        print(0)
        sys.exit()

judge = [False for i in range(10**6+1)]
for num in a:
    judge[num] = True
for i in range(1,(10**6)):
    if judge[i]:
        for j in range(i*2,10**6+1,i):
            judge[j] = False
ans = 0
for i in range(1,10**6+1):
    if judge[i]:
        ans+=1
subans = 0
c = collections.Counter(a)
for k,v in c.items():
    if v > 1:
        subans+=1
print(ans-subans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
l = [True] * (10**6 + 1)
cnt = 0
for i in range(n):
  d = a[i]
  if l[d]:
    if i < n-1 and a[i] != a[i+1]:
      cnt += 1
    elif i == n-1:
      cnt += 1
    for j in range(d, 10**6 + 1, d):
      l[d] = False
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
import sys
 
n  = int(input())
l  = list(map(int, input().split()))
l = sorted(list(set(l)))

dp = [0 for _ in range(max(l)+1)]
for n in l:
    dp[n] += 1
    for i in range(n*2, len(dp), n):
        dp[i] += 2

print(dp.count(1))

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
S = set()
D = set()
for a in A:
    if a in S:
        D.add(a)
    else:
        S.add(a)
M = max(S)
A = [0]*(M+1)
for s in S:
    if s in D:
        A[s] += 1
        continue
    else:
        for i in range(2*s,M+1,s):
            A[i]+=1
count = 0
for s in S:
    if A[s]==0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import copy
from numba import jit
N = int(input())
c=list(map(int, input().split()))

@jit
def search(N,c):
  count = 0
  for i in range(N):
    b = []
    m = copy.copy(c)
    a = c[i]
    m.pop(i)
    m.sort()
    for j in range(N-1):
      if m[j]>c[i]:
        count+=1
        break
      elif c[i]%m[j]==0:
        break
      elif j == N-2:
        count+=1
      elif c[i]%m[j]!=0:
        continue
      
  return count

print(search(N,c))

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter
from sys import exit
N = int(input())
if N == 1:
  print(1)
  exit()
A = map(int, input().split())
ban = {k for k, i in Counter(A).items() if i >= 2}
D = deque(sorted(list(set(A))))
ans = 0
while D:
  ini = D.popleft()
  if not ini in ban:
    ans += 1
  if len(D) == 0:
    break
  for i in range(len(D)):
    d = D.popleft()
    if d % ini != 0:
      D.append(d)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = Counter(A)
    c = sorted(c.items(), key=lambda x: x[0])
    ans = []
    for k, v in c:
        if v > 1:
            continue

        for a in ans:
            if k % a == 0:
                break
        else:
            ans.append(k)

    print(len(ans))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


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

    S = list(count.keys())
    double = []
    for s in S:
        if count[s] > 1:
            double.append(s)
    double = set(double)
    S = set(S)
    if 1 in S:
        print(1)
        return

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

        # divisors.sort()
        return divisors

    answer = 0
    for a in A:
        if a in double:
            continue

        divisors = make_divisors(a)

        cnt = 0
        for div in divisors:
            if div in S:
                break
            else:
                cnt += 1

        if cnt == len(divisors):
            answer += 1
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy
from numba import jit
N = int(input())
c=list(map(int, input().split()))

@jit
def search(N,c):
  count = 0
  for i in range(N):
    b = []
    m = copy.copy(c)
    a = c[i]
    m.pop(i)
    m.sort()
    for j in range(N-1):
      if m[j]>c[i]:
        count+=1
        break
      elif c[i]%m[j]!=0:
        continue
      elif c[i]%m[j]==0:
        break
  return count

print(search(N,c))