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 collections import Counter
n = int(input())
A = list(map(int,input().split()))
A = sorted(A)

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table
  
is_prime, _ = sieve(10**6)  

s = set()
for a in A:
  if is_prime[a-1]:
    s.add(a)
  else:
    for si in s:
      if a%si==0:
        break
    else:
      s.add(a)
      
ans = 0
C = Counter(A)
for si in s:
  if C[si]==1:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

a.sort()
sub = [-1] * n
sub[0] = a[0]
index = 1
count = 1
for i in range(1, n):
    flag = True
    for j in sub[:index]:
        if a[i] // 2 < j:
            break
        if a[i] % j == 0:
            flag = False
    if flag:
        sub[index] = a[i]
        index += 1
        count += 1
print(count)

Submission status: Wrong Answer

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

A = sorted(A)
num = len(A)

res = 1
if len(A) > 1 and A[0] == A[1]:
  res = 0

for i in range(1, num):
  divisible = False
  for j in range(i):
    if A[i] % A[j] == 0:
      divisible = True

  if not divisible:
    res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
A.sort()
results = 0
while(A):
  a = A.pop(0)
  AA = [i for i in A if i!=a]
  AAA = [i for i in A if i%a!=0]
  N-= (len(A)-len(AA)+1)
  results += (len(AAA)-len(AA))
  A = AAA
print(N-results)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def prime_factors(n):
    c = collections.Counter()
    while n > 1:
        for i in range(2, n + 1):
            if n % i == 0:
                c.update([i])
                n //= i
                break
    return c


def solve(N, As):
    As.sort()
    count = collections.Counter(As)
    past_primes = {}
    past_primes_keys = {}
    ans = 0
    for a in As:
        prime = prime_factors(a)
        if count[a] > 1:
            continue
        success = True
        for k in prime.keys():
            if k not in past_primes:
               continue
            if past_primes[k] <= prime[k]:
                another_check = past_primes_keys[k]
                for past_a in another_check:
                    if a % past_a == 0:
                        success = False
                        break
        # print(prime)
        if success:
            # print(a)
            ans += 1

        for k in prime.keys():
            if k not in past_primes:
                past_primes[k] = prime[k]
                past_primes_keys.setdefault(k, []).append(a)

    return ans

assert(solve(5, [24, 11, 8, 3, 16]) == 3)
assert(solve(10, [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]) == 5)

if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))

    print(solve(N, As))

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()
A.sort()

cc = collections.Counter(A)
# print(cc)
a = []
for key in cc.keys():
    if cc[key] > 1:
        continue
    else:
        a.append(key)
a.sort()
chosen = []
if len(a) > 0:
    chosen = [a[0]]
else:
    print("0")
    sys.exit()

for a_i in a:
    for c in chosen:
        if a_i % c == 0:
            break
    else:
        chosen.append(a_i)
print(len(chosen))

Submission status: Wrong Answer

Solution code:
def LI():return list(map(int,input().split()))
def MI():return map(int,open(0).read().split())
def I():return int(input())
def yes():print("Yes")
def no():print("No")

from collections import deque, Counter
# from heapq import heappop, heappush
# INF=float("inf")
# import math
# pi=math.pi
# from pprint import*
# import numpy as np

def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return sorted(ass)[:-1] #sortされていない
    # 自分以外の約数を返す

n,*a=MI()
cnt=0
a.sort(reverse=True)
b=deque(a)
# print(a,b)
# ans=[]
while b:
    q=b.popleft()
    qt=divisor(q)
    if len(set(qt)&set(b))==0:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from math import sqrt
input = stdin.readline

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

is_prime = [False] * n
is_continue = [False] * n

A.sort()
ans = 0

for i, a in enumerate(A):
    if a == 2:
        is_prime[i] = True
    tmp = a
    for j in range(2, int(sqrt(n)) + 1):
        if tmp % j == 0:
            tmp //= j
    if tmp == a:
        is_prime[i] = True

k = 0

for i in range(k, n - 1):
    if is_continue[i]:
        k += 1
        continue
    elif A[i] == A[i + 1]:
        is_continue[i] = True
        is_continue[i + 1] = True
        k += 1
        continue
    else:
        ans += 1
        for j in range(i + 1, n):
            if A[j] % A[i] == 0:
                is_continue[j] = True

if not is_continue[n - 1]:
    ans += 1

print(ans)
# print(A)
# print(is_prime)
# print(is_continue)

Submission status: Wrong Answer

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

A.sort()

ls = []

count = 0

while A:
    a = A[0]

    if len(A) >= 2 and a == A[1]:
        A = [x for x in A[1:] if x != a]
        continue

    else:
        A = [x for x in A[1:] if x % a != 0]
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import collections
import math as mt 
def divisibilityCheck(arr, n): 
    s = dict() 
    max_ele = -10**9
    for i in range(n):  
        s[arr[i]] = 1
        max_ele = max(max_ele, arr[i]) 
    res = dict() 
    for i in range(n):  
        if (arr[i] != 0): 
            for j in range(arr[i] * 2, max_ele + 1, arr[i]): 
                if (j in s.keys()): 
                    res[j] = 1
    return n-len(res)
n=int(input())
l=list(map(int, input().split()))
d=collections.Counter(l)
num=divisibilityCheck(l,n)
for i in l:
    if d[i]>1:
        num=num-1
print(num)

Submission status: Wrong Answer

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

ea = enumerate(a)
sa = sorted(ea, reverse = True, key = lambda x:x[1])

c = 0
for i in range(n):

    flg = True

    for j in range(1,n-i):
        # if i+j >= n:
        #     break
        if sa[i][1] % sa[i+j][1] == 0:
            flg = False
            break

    if sa[i][1] == sa[i-1][1]:
        flg = False

    if flg == True:
        c += 1
        # print(i)

print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
p = 0
if 1 in a:
    if a.count(1) >= 2:
        print(0)
        exit(0)
    else:
        print(1)
        exit(0)

for i in range(n):
    if a.count(a[i]) >= 2:
        pass
    else:
        for j in range(a[i])[2:]:
            if a[i] % j == 0:
                if j in a:
                    break
            if j == a[i] - 1:
                p += 1

print(p)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
C = []
ans = 0
for i in range(N):
    check = 0
    for j in C:
        if A[i] % j == 0:
            check = 1
            break
    #print(check,ans,A[i],C)
    if check == 0 :
        if A[i] < 5 * (10**5) + 2:
            C.append(A[i])
        if i < N-1:
            if A[i] != A[i+1]:
                ans += 1
        else:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:

import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n): return [0] * n
def array2(n, m): return [[0] * m for x in range(n)]
def array3(n, m, l): return [[[0] * l for y in xrange(m)] for x in xrange(n)]

N = n1()
A = nn()

A.sort(reverse=True)
#print(A)

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
cnt=0
for i in A:
  num=A.index(i)+1
  for j in range(num,N):
    if  math.gcd(i,A[j])==min(i,A[j]) and i!=A[j]:
      cnt+=1
ans=N-cnt
print(ans)

Submission status: Wrong Answer

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

flg = [1] * n
cnt = 0
for i in range(1, n):
    for j in range(i):
        if not flg[j]:
            continue
        elif A[i] == A[j]:
            flg[i] = 0
            flg[j] = 0
        elif A[i] % A[j] == 0:
            flg[i] = 0
            break
print(sum(flg))

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()
if N == 1:
    print(0)
cnt = Counter(A)
A = []
for k, v in cnt.items():
    if v == 1:
        A.append(k)

A.sort()
AMAX = 10**6 + 10
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):
            # print(j)
            is_first[j] = False
print(cnt)

Submission status: Wrong Answer

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

count = 0

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

Submission status: Wrong Answer

Solution code:
import math

n=int(input())
l=list(map(int, input().split(' ')))

l=sorted(l)
if l[0]==l[-1]:
    print(0)
else:
    index = 1
    ans=1
    while index<n:
        sindex=0
        tindex=index
        while sindex<tindex:
            if l[index]%l[sindex]==0:
                l.pop(index)
                index-=1
                n-=1
                break
            sindex+=1
        if sindex==tindex:
            ans+=1
        index+=1
    print(ans)

Submission status: Wrong Answer

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

if len(set(a))==1:
    print(0)
    exit()
c=0
l=[]
while True:
    k=a.pop(0)
    l.append(k)
    a=[i for i in a if i % l[c] != 0]
    c+=1
    if len(a)==0:
        print(len(l))
        exit()

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
N = int(input())
A = [int(i) for i in input().split()] 
A.sort()

d = deque(A)

ans = 0
while len(d) > 0:
  div = d.popleft()
  ans += 1
  dup_flag = False
  first_flag = True
  first = 1000000000
  while len(d) > 0:
    num = d.popleft()
    if num == first:
      d.appendleft(num)
      break
    if num == div:
      dup_flag = True
    elif num % div != 0:
      d.append(num)
      if first_flag:
        first = num
        first_flag = False
    
  if dup_flag:
    ans -= 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    i = 1
    flg = 1
    while i*i <= n:
        if n % i == 0:
            if i in s and i != n:
                flg = 0
                break
            ii = n//i
            if i != ii:
                if ii in s and ii != n:
                    flg = 0
                    break
        i += 1
    return flg

def prime(x):
    if x < 2   : return 0
    if x == 2  : return 1
    if x%2 == 0: return 0
    for i in range(3, x, 2):
        if i*i > x:
            break
        if x%i == 0:
            return 0
    return 1

def main():
    cnt = 0
    from collections import Counter
    c = Counter(a)
    for i in range(n):
        if c[a[i]] > 1:
            continue
        if prime(a[i]):
            cnt += 1
        elif make_divisors(a[i]):
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int,input().split()))
    s = set(a)
    main()

Submission status: Wrong Answer

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

M = 10 ** 6
sieve = [True] * (M + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, int(M ** 0.5) + 1):
    if not sieve[i]:
        continue
    for j in range(i * i, M + 1, i):
        sieve[j] = False

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

b = sorted(d)
result = 0
for i in range(len(b)):
    if d[b[i]] > 1:
        continue
    if sieve[b[i]]:
        result += 1
        continue
    for j in range(i):
        if b[i] % b[j] == 0:
            break
    else:
        result += 1
print(result)

Submission status: Wrong Answer

Solution code:
def resolve():
    import bisect
    import math
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)
    maxa = a[-1]
    maxi = bisect.bisect_left(a, math.ceil(maxa**0.5))

    ans = [1]*n
    for i in range(0, maxi+1):
        if ans[i] == 1:
            for j in range(i+1, n):
                if ans[j] == 0:
                    continue
                if a[j] == a[i]:
                    ans[i] = 0
                if a[j] % a[i] ==0:
                    ans[j] = 0
    print(sum(ans))
resolve()

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    if n == 1:
        print(0)
        return
    nums.sort()
    #nums = list(reversed(nums))
    checkList = [True] * n
    if nums[0] == nums[1]:
        checkList[0] = False
    
    for i in range(n):
        if not checkList[i]:
                continue
            
        for j in range(i + 1, n):
            #print(nums[j], nums[i])
            if nums[j] % nums[i] == 0:
                if nums[j] == nums[i]:
                    checkList[i] = False
                checkList[j] = False
        #print(nums)
        #print(checkList)
    print(sum(checkList))


    
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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]


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

    A.sort()

    aset = list(set(A))

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

    c = collections.Counter(A)
    for x in c.most_common():
        if x[1] > 1:
            ans -= 1
        else:
            break

    print(ans)


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):
  for j in range(n):
    if a[i] != a[j]:
      if a[i]%a[j] == 0:
        ans += 1
        break
print(ans)

Submission status: Wrong Answer

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

if n >= 2 and a[0] == a[1]:
    num = n-1
else:
    num = n

for i in range(1, n):
    for j in range(i):
        if a[i] % a[j] == 0:
            num -= 1
            break
print(num)

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
C=collections.Counter(A)
B=sorted(A)
A=list(set(B))
D=[]
counter=N
for i in range(0,len(A)):
    for j in range(0,i):
        if A[i]%A[j]==0:
            N-=1
            D.append(A[i])
            break
K=list(C.values())
for i in range(0,len(K)):
    if K[i]>1:
        N=N-(K[i])
        if D.count(K[i])==1:
            N+=1
print(N)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline


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

    A.sort()
    c = Counter(A)
    keys = list(c.keys())
    ans = 0
    for i, (k, v) in enumerate(c.items()):
        if v > 2:
            continue
        is_ok = True
        for key in keys[:i]:
            if k % key == 0:
                is_ok = False
                break
        ans += v * is_ok

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    mx=10**6
    aa=LI()
    ac=Counter(aa)
    aa=[]
    for a,c in sorted(ac.items()):
        if c==1:aa.append(a)
    #print(aa)

    ok=[True]*(mx+1)
    ans=0
    for a in aa:
        if ok[a]:
            ans+=1
            for b in range(a*2,mx+1,a):
                ok[b]=False
    print(ans)

main()

Submission status: Wrong Answer

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

seen = set()
A_set = set()
A_largest = 0
for a in A:
    if a > A_largest:
        A_largest = a
    if a not in seen:
        A_set.add(a)
        seen.add(a)
    else:
        if a in A_set:
            A_set.remove(a)

for b in range(1, A_largest+1):
    if b in A_set:
        n = 2
        c =b*n
        while c <= A_largest:
            if c in A_set:
                A_set.remove(c)
            c += b

print(len(A_set))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
multi = [x for x in set(a) if a.count(x) > 1]
a = list(set(a))
ans = 0
dec = 0
i = 0
while i < len(a):
    if a[i] in multi:
        dec += 1
    j = i + 1
    while j < len(a):
        if a[j] % a[i] == 0:
            a.pop(j)
            continue
        j += 1
    i += 1
ans = len(a) - dec
print(ans)

Submission status: Wrong Answer

Solution code:
from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(2)
            exit()

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A = list(set(A))
A = sorted(A, reverse=True)
num = 0
N = len(A)
for i in range(N - 1):
    flag = True
    for j in range(i+1, N):
        if A[i] % A[j] == 0:
            flag = False
            break
    if flag == True:
        print(A[i])
        num += 1
if N == 1:
    print(0)
else:
    print(num + 1)

Submission status: Wrong Answer

Solution code:
import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


N=int(input())
A=nl()
A.sort()
A_MAX=10**6+5
p_l=[0]*(A_MAX)
c=0
if(len(A)==1):
    print(1)
    sys.exit(0)

for i in range(len(A)):
    if(i==0):
        if(A[i]==A[i+1]):
            continue
    elif(i==(len(A)-1)):
        if(A[i]==A[i-1]):
            continue
    else:
        if(A[i]==A[i-1] or A[i]==A[i+1]):
            continue 
    if(p_l[A[i]]==0):
        c+=1
        if(A[i]*2<A_MAX):
            for k in range(A[i]*2,A_MAX,A[i]):
                if(p_l[k]):
                    continue
                p_l[k]=1

print(c)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

def solve(arr, n): 
    s = {}
    max_ele = float('-inf')
    for i in range(n): 
        s[arr[i]] = 1
        max_ele = max(max_ele, arr[i]) 
    res = {}
    for i in range(n): 
        if arr[i] != 0: 
            for j in range(arr[i] * 2, max_ele + 1, arr[i]): 
                if j in s: 
                    res[j] = 1
    return n-len(res)

n = inp()
x = ip()
if len(set(x)) == 1:
    print(0)
else:
    print(solve(x,n))

Submission status: Wrong Answer

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

count = 0

for i1,v1 in enumerate(A):
    for i2,v2 in enumerate(A):
        if i1 != i2 and v1 != v2 and v1 % v2 == 0:
            #print(v1,"%",v2,v1 % v2)
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import itertools
import copy
from collections import deque
import heapq
n = int(input())
ans = 0
a = list(map(int,input().split()))
a.sort()
a = a[::-1]
mod = 0
flag = True
check = {}
p = {}
for i in a:
    if i in check:
        if check[i] == 0:
            p[i] = 0
            check[i] = 1
        continue
    else:
        check[i] = 0
for i in a:
    #print(mod,i,n)
    if mod % i == 0:
        if not i in p:
            ans += 1
    else:
        mod *= i
    if flag:
        flag = False
        mod = i
        continue
print(ans)

Submission status: Wrong Answer

Solution code:
# D

n = int(input())
a_list = [int(x) for x in input().split()]
f_list = [True]*n
a_list.sort(reverse=True)

for i in range(n):
    _q = a_list[i]
    if i > 1 and _q == a_list[i-1]:
        f_list[i] = False
        continue
    for j in range(n-1,i,-1):
        if _q % a_list[j] == 0:
            f_list[i] = False
            break

ans = sum(x for x in f_list)
print(ans)

Submission status: Wrong Answer

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

B = [0 for _ in range(n)]
for i in range(n):
  c = 0
  if i < n-1 and A[i] == A[i+1]:
    B[i] = 1
    B[i+1] = 1
  if B[i] == 1:
    continue
  while(A[i]*c <= A[n-1]):
    c += 1
    for j in range(n)[i+1:]:
      if A[i]*c > A[j]:
        continue
      if A[j] == A[i]*c:
        B[j] = 1
print(n-sum(B))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
t = Counter(a)
b = []
for i, j in t.most_common():
	if j == 1:
		b.append(i)
bset = set(a)

def sieve(n):
	ret = []
	divlis = [-1]*(n+1)  # 何で割ったかのリスト(初期値は-1)
	flag = [True]*(n+1)
	flag[0] = False
	flag[1] = False
	ind = 2
	while ind <= n:
		if flag[ind]:
			ret.append(ind)
			ind2 = ind**2
			while ind2 <= n:
				flag[ind2] = False
				divlis[ind2] = ind
				ind2 += ind
		ind += 1
	#何で割ったかのリストを取得したいとき, divlisも出力する
	return ret

k = sieve(1000000)

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

ans = 0
for i in b:
	t=makediv(i)
	mode = 1
	for l in t:
		if l in bset:
			mode = 0
			break
	if mode:
		ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math


def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True


n=int(input())
As = list(map(int, input().split()))
i=0
j=0
count =0
for a in As:
    for b in As:
        if As.count(a)>=2:
            break
        elif isPrime(a):
            count+=1
            break
        if i!=j:
            if a%b==0:
                break
            elif j==n-1:
                count+=1
        j+=1
    i+=1
    j=0

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
#import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
a=list(map(int,input().split()))
a.sort()
s=10**6
s+=100
sosu_flag=[True for i in range(s)]
#素数であるかどうかの前計算
#素数をn倍していき倍数をどんどん塗りつぶしていくイメージ
ans=0
for i in a:
    if not sosu_flag[i]:
        continue
    ans+=1
    for j in range(i,s,i):
        sosu_flag[j]=False

c=Counter(a)
for key in c.keys():
    if c[key]>1 and sosu_flag[key]:
        ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(1)
            exit()

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if len(a_list) == 1:
    print(0)
else:
    if a_list[0] != a_list[1]:
        ans += 1
    for i in range(1, n):
        for j in range(i):
            if a_list[j] > a_list[i] / 2:
                break
            if a_list[i] % a_list[j] == 0:
                break;
            if j == i - 1:
                ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

a.sort(reverse=True)
cnt = n

for i in range(len(a) - 1):
    for j in range(len(a[i + 1:])):
        if a[i] % a[n - 1 - j] == 0:
            cnt -= 1
            break
if a[-1] in a[:n - 1]:
    cnt -= 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
aa = list(map(int, input().split()))
aa.sort()

from collections import Counter
dic = Counter(aa)
times = np.array(list(dic.keys()))[np.array(list(dic.values())) > 1]

aa = list(set(aa) - set(times))
oks = np.ones(len(aa))
for i in range(len(aa)):
    for j in range(i+1,len(aa)):
        if (aa[j]%aa[i] == 0):
            oks[j] = 0
print(int(oks.sum()))

Submission status: Wrong Answer

Solution code:
n = int(input())
search = list(map(int,input().split()))
ans = []
search.sort(reverse=True)
while search and search[-1]*2 <= search[0]:
    k = search.pop()
    ans.append(k)
    if search and k == search[-1]:
        ans.pop()
    search = [i for i in search if i % k != 0]
ans += search
print(len(ans))