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:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

cnt = [0] * (10 ** 6 + 1)
for a in A:
    cnt[a] += 1

if cnt[1] >= 2:
    print(0)
    exit()

if cnt[1] == 1:
    print(1)
    exit()

answer = 0
for i in range(2, 2 * 10 ** 5 + 1):
    if cnt[i] == 1:
        answer += 1
    if cnt[i] == 0:
        continue
    k = 2
    while i * k <= 2 * 10 ** 5:
        cnt[i * k] = 0
        k += 1

print(answer)

Submission status: Wrong Answer

Solution code:
import sys

from collections import deque

readline = sys.stdin.buffer.readline

N = int(readline())
A = sorted(list(map(int, readline().split())))

if len(set(A)) == 1:
    print(0)

else:
    cc = []

    i = 0
    while True:
        c = deque([])
        if i >= len(A):
            break
        a = A[i]
        for ac in A:
            if ac % a != 0:
                c.append(ac)

        c.appendleft(a)
        A = list(c)
        i += 1

    print(len(A))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(v) for v in input().split()]
s = set()
not_uniq = set()

for a in A:
    if a in s:
        not_uniq.add(a)
    else:
        s.add(a)

A.sort()

furui = [True for _ in range(int(1e6)+1)]

ans = 0
for a in A:
    base = a * 2
    if not a in not_uniq:
        ans += 1 if furui[a] else 0

    while base * base < int(1e6) + 1:
        furui[base] = False
        base += a

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
flg=0
for i in range(n):
  for j in range(i):
    if a[i]%a[j]==0:
      flg=1
      break
  if flg==0:
    ans=ans+1
  flg=0

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def lcm(a, b):
    a, b = max(a, b), min(a, b)
    c = a * b
    while a % b > 0:
        a, b = b, a % b
    return c // b

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    if N == 1: 
        print(1)
        return 0
    #lcmA = lcm(A[0], A[1])
    #for i in range(2, N): lcmA = lcm(lcmA, A[i])

    B = [False] * (max(A) + 1)
    nums = dict()
    for a in A:
        B[a] = True
        if a in nums: nums[a] += 1
        else: nums[a] = 1
    
    ans = 0
    for k in nums:
        if nums[k] > 1: continue
        else:
            flag = True
            for i in range(2, k):
                if i ** 2 > k: break
                if k % i == 0:
                    if B[i] or B[k//i]:
                        flag = False
                        break
            if flag: ans += 1
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    answer = n
    chk = [0 for _ in range(a[-1] + 1)]
    for aa in a:
        chk[aa] += 1
    for i in range(a[-1] + 1):
        if chk[i] == 1:
            for j in range(2 * i, a[-1] + 1, i):
                answer -= chk[j]
                chk[j] = 0
        else:
            answer -= chk[i]
            chk[i] = 0
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
num = int(input())
arr = input().split()
arr = [int(i) for i in arr]

arr = sorted(arr, reverse=True)

cnt = 0

for i in range(num-1):
  flg=0
  for j in range(i+1, num):
    if arr[i]%arr[j]==0:
      flg=1
      break
  if flg==0: cnt += 1
    
print(cnt)

Submission status: Wrong Answer

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

    m = 10**6 + 1
    c = [0]*m
    for i in a:
        c[i] += 1

    ans = 0
    for i in a:
        if c[i] > 1:
            continue
        for j in range(1, int(i**0.5)+1):
            if i % j == 0:
                if c[j]:
                    break
                if j*j != i and j!=1:
                    if c[i//j]:
                        break
        else:
            ans += 1
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=sorted(A,reverse=True)
count=0
for i in range(N):
  flag=False
  for j in range(i+1,N):
    if B[i]%B[j]==0:
      flag=True
  if flag==False:
    count+=1
    
print(count)

Submission status: Wrong Answer

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

nums.sort()

if n == 1:
    print(1)
    exit()

ans_list = [nums[0]]

for i in range(n):
    valid = True
    for j in range(len(ans_list)):
        if nums[i] % ans_list[j] == 0:
            # 割り切れた
            valid = False
            break
        if nums[i] < ans_list[j] * 2:
            break
    if valid:
        ans_list.append(nums[i])
    
# nums[0] = num[1] の場合は0を減らす：
ans = len(ans_list)
if nums[0] == nums[1] :
    ans -= 1

print(ans)
# print(ans_list)

Submission status: Wrong Answer

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

a = sorted(a)

ps = [a[0]]
for ai in a[1:]:
    is_divided = False
    for p in ps:
        if ai % p == 0:
            is_divided = True
            break
    if not is_divided:
        ps.append(ai)

print(len(ps))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

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


def make_divisors(n):
    divisors = [1]
    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


setA = set(A)
countA = Counter(A)
count = 0
for num in A:
    if countA[num] >= 2:
        continue
    divisors = make_divisors(num)
    if all([e not in setA for e in divisors]):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

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

    # divisors.sort()
    return divisors


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

    A.sort()


    ans = 0
    s = set()
    for a in A:
        divs = make_divisors(a)
        for div in divs:
            if div in s:
                break
        else:
            ans += 1

        s.add(a)

    c = collections.Counter(A)
    for k in c.keys():
        if c[k] > 1:
            ans -= 1

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n = int(input())
orga = list(map(int, input().split()))
orga.sort()

if len(set(orga)) == 1:
    print(0)
    exit()

import collections
from collections import defaultdict
d = defaultdict(int)
c = collections.Counter(orga)

a=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        a.append(num)

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

ans=0
for num in a:
    found=False
    for div in m_div(num):
        if div in d:
            found=True
            break
    if not found:
        ans+=1
    d[num]=1
print(ans)

Submission status: Wrong Answer

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

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

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

cnt = 0
is_ok = [True for _ in range(max(a)+1)]

for v in a:
   divs = make_divisors(v)
   f = True
   for w in divs:
      # check
      if not is_ok[w]:
         f = False
         break
   if f:
      cnt += 1
   is_ok[v] = False

if cnt == 1:
   cnt = 0
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    A.sort()
    count = 0
    for i in range(N):
        if A[i] == -1:
            continue
        else:
            count += 1
        if i == N-1:
            break
        for j in range(i+1,N):
            if A[j]%A[i] == 0:
                A[j] = -1
    print(count)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(map(int, input().split())))
    D = Counter(A)

    B = []
    for k, v in D.items():
        if v == 1:
            B.append(k)

    W = set()
    res = 0
    for a in B:
        for i in range(1, int(pow(a, 0.5)) + 1):
            if a % i == 0:
                if i in W or a // i in W:
                    break
        else:
            res += 1
        W.add(a)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = []
    for i, c in Counter(list(map(int, input().split()))).items():
        if c > 1:
            continue
        A.append(i)
    A.sort()
    X = []
    ans = 0
    for a in A:
        for x in X:
            if a % x == 0:
                break
        else:
            ans += 1
            X.append(a)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
al = [int(i) for i in input().split()]

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

    divisors.sort()
    return divisors[:-1]
  
import collections

if n == 1:
  print(0)
else:
  total = 0
  ss = set(al)
  c = collections.Counter(al)
  for num in al:
    if c[num] >= 2:
      break
    for d in make_divisors(num):
      if d in ss:
        break
    else:
      total += 1
  print(total)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors


def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = Counter(A)
    b = set(A)
    c = {}
    def make_divisors(n):
        for i in range(1, int(math.sqrt(n))+1):
            if n % i == 0:
                if i in b:
                    return 0
                if i != n // i and n//i != n:
                    if n//i in b:
                        return 0
        return 1


    def find(x):
        if x in c:
            return c[x]
        if a[x] > 1:
            return 0
        return make_divisors(x)
    r = 0
    for i in A:
        r += find(i)
    return r
print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())
A = sorted(map(int, input().split()))
if len(set(A)) == 1:
    print(0)
    exit()
ans = 0
used = set()
for a in A:
    if any(a % x == 0 for x in used):
        continue
    ans += 1
    used.add(a)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
c = collections.Counter(l)

l = sorted(l)
sosu = []

if len(c) == 1:
    print(0)
    exit()

ans = 0
for i1 in range(len(l)):
    for s in sosu:
        if l[i1] == s or l[i1] % s == 0:
            break
    else:
        sosu.append(l[i1])
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())

A = list(map(int, input().split()))
A.sort()
ans = []
ans.append(A[0])
before = A[0]
for a in A[1:]:
    if before == a:
        if a in ans:
            ans.remove(a)
        continue
    flag = True
    for b in ans:
        if a % b == 0:
            flag = False
            break
        if a < b*2:
            break
    if flag:
        ans.append(a)
    before = a

print(len(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

Ss = sorted(As)
primes = set()
cnt = 0
d = defaultdict(int)
for s in Ss:
    d[s] += 1
for s in Ss:
    if d[s] > 1:
        continue
    flg = False
    for p in primes:
        if s % p == 0: 
            flg = True
            break
    if not flg:
        # print("dw!,",s)
        primes.add(s)
        cnt += 1
# print(primes)
print(cnt)

Submission status: Wrong Answer

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

a.sort()
ans = 1
if n==1:
    print(ans)
    exit()
if n>=2 and a[0]==a[1]:
    ans=0
for i in range(1,n):
    c=0
    for j in range(i):
        if a[i]%a[j]==0:
            c=1
            break
    if c==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import Counter, deque

N = int(input())
A = list(map(int, input().split(' ')))
counter = Counter(A)
A = np.array(sorted([key for key, value in counter.items() if value == 1]))

results = deque()
while len(A) > 0:
    results.append(A[0])
    A = A[A % A[0] != 0]

print(len(results))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(n) for n in input().split()]
ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
def check(s, a, next):
    if a == next:
        return False
    while a%2==0:
        if 2 in s:
            return False
        a //= 2
        if a in s:
            return False
    x = 2
    while a>1 and a>=x*x:
        while a%x==0:
            if x in s:
                return False
            a //= x
            if a in s:
                return False
        x += 2
    if a>1:
        if a in s:
            return False
    return True

n = int(input())
al = list(map(int, input().split()))
al.sort()

s = set()
res = 0
for i in range(n):
    a = al[i]
    next = -1
    if i<n-1:
        next = al[i+1]
    if check(s,a,next):
        res += 1
    s.add(a)
print(res)

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

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

    A.sort(reverse=True)
    ans = 0

    while(A):
        ans += 1
        x = A.pop()
        next = []
        for y in A:
            if y % x != 0:
                next.append(y)
        A = list(next)
    if ans < 2:
        ans = 0
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
b = set(a)

lim = pow(10, 6)+3
judge = [False]*(lim)
ans = 0
a.sort()
key = 0
for i in range(lim):
  if judge[i] == True:
    continue
  elif i not in b:
    continue
  else:
    if key != n-1 and a[key] == a[key+1]:
      pass
    else:
      ans += 1
    key += 1
    while key < n-1 and a[key] == a[key+1]:
      key += 1
    for j in range(i, lim, i):
      judge[j] = True
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(_) for _ in input().split()]
a.sort()
ans=[1 for i in range(n)]

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


print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(map(int, input().split()))
S.sort()
ans = 0
if N > 1:
    if S[0] < S[1]:
        ans += 1
for i in range(N-1, 0, -1):
    num = S[i]
    flg = True
    for j in range(i):
        if num%S[j] == 0:
            flg = False
            break
        elif S[j] > num/2:
            break
    if num%S[i-1] == 0:
        flg = False
    if flg:
        ans += 1
print(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()
a.sort()

for i in range(n-1):
    if a[i] != a[i+1]:
        break
else:
    print(0)
    quit()

f = defaultdict(lambda : 1)
ans = 0
for i in a:
    if f[i]:
        ans += 1
        j = 1
        while i*j <= 10**6:
            f[i*j] = 0
            j += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
    C = Counter(A)

    U = [0]*(max(A)+1)
    ans = 0
    for e in C:
        if C[e] > 1:
            U[e] = 1
        else:
            f = 1
            for k in range(2,math.floor(math.sqrt(e))+1):
                if e % k == 0:
                    if U[k] == 1 or U[e//k] == 1:
                        f = 0
                        break
            if f == 1:
                ans += 1
            U[e] = 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
As = sorted(map(int, input().split()))

Aset = sorted(list(set(As)))
count = Counter(As)

ans = 0
for i in range(len(Aset)-1, 0, -1):
  if count[Aset[i]] > 1:
    continue
  for j in range(0,i):
    if Aset[i] % Aset[j] == 0:
      break
  else:
    ans += 1

if len(As) > 1 and As[0] != As[1]:
  ans += 1
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
if A.count(A[0]) == len(A):
    print(0)
    exit()
for i in range(n):
    chk = True
    for j in range(i+1, n):
        if A[i] % A[j] == 0:
            chk = False
            break
    if chk == True:
        ans += 1
    else:
        pass
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# 一番小さい数はかならず条件を満たす(同じ数があるときはだめ)
# i!=j の任意のjで割り切れない → N-i!=jで一つでも割り切れるものがある数

'''
エラトステネスの篩の数列版じゃない？
1  2  3  4  5  6  7  8  9  10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

小さい方から倍数を取ってけば良いかな
'''


N = read_a_int()
A = read_ints()
cnt = Counter(A)
A = []
for k, v in cnt.items():
    if v == 1:
        A.append(k)

A.sort()
AMAX = 10**6
cnt = 0  # なにでも割り切れないときのcnt
is_first = [True] * (AMAX + 1)
for a in A:
    if is_first[a]:
        cnt += 1
        for j in range(a, AMAX + 1, a):
            is_first[j] = False
print(cnt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]

if len(set(a)) == 1:
    print(0)
    sys.exit()

lis_prime = [True] * n
primes = []
cnt = 0

for i, val in enumerate(a):
    if lis_prime[i]:
        primes.append(val)
        cnt += 1

        for j in range(i, n):
            if a[j] % val == 0:
                lis_prime[j] = False

print(len(primes))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort()
s=set()
B=[]
while A:
    x=A.pop()
    if A:
        if x!=A[-1]:
            s.add(x)
            B.append(x)
        else:
            s.add(x)
            while A:
                y=A.pop()
                if y!=x:
                    A.append(y)
                    break
    else:
        s.add(x)
        B.append(x)
ans=0
for x in B:
    for j in range(1,int(x**0.5)+1):
        if j==1 and x!=1:
            if j in s:
                break
        elif x%j==0:
            if x//j in s or j in s:
                break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math as mt
#import numpy as np

def ro(n):
  return mt.floor(mt.sqrt(n))
def ya():
  print("Yes")
  return
def na():
  print("No")
  return


#x,n=map(int,input().split())
n=int(input())
lis=list(map(int,input().split()))
#s=input()

lis.sort(reverse=True)
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    #print("{} {}".format(lis[i],lis[j]))
    if lis[i]%lis[j]==0:
      break
  else:
    ans+=1
    print("x")
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
num=1
a.sort()
ans=0
num3=a.count(a[n-1])
if num3!=1:
    ans-=1
for i in range(n):
    num2=0
    for j in range(i):
        if a[i]%a[j]==0:
            num2=1
            break
    if num2!=1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
s=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 
229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
def make_divisors(n):
    divisors = []
    k=int(n**0.5)+1
    for i in s:
        if i>k:
            break
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()　#小さい順位欲しいとき
    return divisors

n=int(input())
a=sorted(list(map(int,input().split())))
dic={}
for k in a:
    x=make_divisors(k)
    if k in dic:
        dic[k]=0
        continue
    f=1
    for i in x:
        if i in dic:
            f=0
            break
    if f:
        dic[k]=1
print(sum(dic.values()))

Submission status: Wrong Answer

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

    a.sort()
    r = 0
    for i1 in range(n):
        flag = 1
        if i1 != n-1:
            if a[i1] == a[i1 + 1]:
                flag = 0
                continue
        for i2 in range(i1):
            if a[i2] == a[i1]:
                flag = 0
                break
            elif a[i2] > a[i1]//2 + 1:
                break
            else:
                if a[i1] % a[i2] == 0:
                    flag = 0
                    break
        if flag:
            r += 1
    print(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def divisor(i):
    s = []
    for j in range(1, int(i ** (1 / 2)) + 1):
        if i % j == 0:
            s.append(i // j)
            s.append(j)
    return sorted(set(s))

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [0] * (pow(10, 6) + 1)
for i in a:
    b[i] += 1
ans = n
for j in a:
    s = divisor(j)
    for k in s:
        if (b[k] > 0 and not k == j) or b[j] > 2:
            ans -= 1
            break
print(ans)

Submission status: Wrong Answer

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

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

def make_divisors(n):
   lower_divisors , upper_divisors = [], []
   i = 1
   while i*i <= n:
      if n % i == 0:
         lower_divisors.append(i)
         if i != n // i:
            upper_divisors.append(n//i)
      i += 1
   return lower_divisors + upper_divisors[::-1]

cnt = 0
is_ok = [True for _ in range(max(a)+1)]

for v in a:
   divs = make_divisors(v)
   f = True
   for w in divs:
      # check
      if not is_ok[w]:
         f = False
         break
   if f:
      cnt += 1
      is_ok[v] = False
if cnt == 1:
   cnt = 0
print(cnt)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
div = set()
dict_a = collections.Counter(a)
for i in range(n):
    flag = True
    if dict_a[a[i]] > 1:
        continue
    for j in range(1,int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            if j in div or a[i] // j in div:
                flag = False
                break
    div.add(a[i])
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    MAX_A = max(A)

    if len(set(A)) == 1:
        print(0)
        exit()

    ans = 0
    prime = [False] * 2 + [True] * (MAX_A - 1)
    visited = set()
    for a in A:
        if a in visited:
            ans += 1
            continue
        if prime[a]:
            visited.add(a)
            ans += 1
            for j in range(a, MAX_A + 1, a):
                prime[j] = False
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
a.sort()
k = 2*N
for i in range(N-1):
  if a[i] != a[i+1]:
    b = [a[i]]
    k = i+1
    break
if k == 2*N:
  print(0)
  exit()
for i in range(k,N):
  c = 0
  for j in b:
    if a[i]%j ==0:
      c = 1
  if c == 0:
    b.append(a[i])
print(len(b))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = sorted(map(int, input().split()))
if len(set(A)) == 1:
    print(0)
    exit()
ans = 0
used = set()
for a in A:
    divisors = set()
    for i in range(1, int(a**.5)+1):
        if a % i == 0:
            divisors |= {i, a//i}
    if used & divisors:
        continue
    ans += 1
    used.add(a)
print(ans)

Submission status: Wrong Answer

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

def henkan(LIST):
    ANS=[]
    for i in range(len(LIST)):
        if LIST[i]%LIST[0]==0:
            pass
        else:
            ANS.append(LIST[i])
    return ANS
cnt=0
if len(A)==1:
    print(0)
    exit()
for i in range(10**9):
    cnt+=1
    A=henkan(A)
    if A==[]:
        print(cnt)
        exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, *A = map(int, open(0).read().split())
c = 0
A.sort(reverse=1)
for i, a in enumerate(A[:-1]):
    c += all(a%j for j in A[i+1:])
print(c + all(A[-1]%i for i in A[:-1]))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=list(set(a))
a.sort(reverse=True)
ans=0
n=len(a)
for i in range(n):
    p=a[i]
    c=True
    for j in range(i+1,n):
        if p%a[j]==0:
            c=False
            break
    if c:
        ans+=1
print(ans)