Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    #A=[i+1 for i in range(1,200000)]
    A.sort()
    ma=A[-1]
    l=[0]*(ma+1)
    
    count=0
    pa=0
    f=0
    for a in A:
        if pa==a:
            if f==1:
                count-=1
            f=0
        elif l[a]==0:
            count+=1
            f=1
            i=a
            while i<ma+1:
                l[i]=1
                i+=a
        pa=a
    print(count)

    #print(l)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

count = 0

out = set()
for i in range(N):
    if A[i] in out:
        continue
    for j in range(i + 1, N):
        if A[i] % A[j] == 0:
            out.add(A[i])
            break
        elif A[j] % A[i] == 0:
            out.add(A[j])
            break

for a in A:
    if a not in out:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import math
N = a=int(input())
listP=[]
while True:
    try:
        listP=list(map(int,input().split()))
    except:
        break;
        
listP.sort()
for i in range(N):
  if listP[i]==0:
    break
  for j in range(N):
    if (i!=j) and (listP[i]*listP[j]!=0) and (listP[i]%listP[j]==0):
      listP[i]=0

print(len([i for i in listP if i > 0]))

Submission status: Wrong Answer

Solution code:
from collections import Counter
def main():
    n = int(input())
    A = list(map(int, input().split()))

    # 複数の同じ値がある場合は消去、
    C = Counter(A)
    non_double_num = []
    double_num = []
    for num, cnt in C.items():
        if cnt != 1:
            double_num += [num]
        else:
            non_double_num += [num]

    non_double_num.sort()
    len_n = len(non_double_num)
    memo = [1] * len_n
    mod_num = 0
    # 割り切れる値も消去
    for i in range(len_n - 1):
        for j in range(i + 1, len_n):
            if memo[j] == 0:
                break
            if non_double_num[j] % non_double_num[i] == 0:
                memo[j] = 0
                mod_num += 1

        for d_n in double_num:
            if non_double_num[i] % d_n == 0:
                memo[j] = 0
                mod_num += 1

    print(len_n - mod_num)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

ans = [True] * N
for i in range(N):
    if not A[i]:
        continue
    for j in range(i+1, N):
        if not A[j]:
            continue
        if A[j] % A[i] == 0:
            ans[j] = False

if A[0] == A[1]:
    ans[0] = False

c = 0
for a in ans:
    if a:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np
def make_divisors(n):
    if n < 1:
        return
    i = 1
    while i * i <= n:
        if n % i == 0:
            yield i
            if i * i != n:
                yield round(n / i)
        i = i + 1
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * n
for i, num in enumerate(a):
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        flag[i] = False
        continue
    div = make_divisors(num)
    for d in div:
        if d == num:
            continue
        if d in a:
            flag[i] = False
print(np.count_nonzero(flag))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
t = 1
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        t *= 1
    else:
        t *= 0
if t == 1:
    print(0)
else:
    B =[]
    B.append(A[0])
    s = 1
    for i in range(1,N):
        for j in range(len(B)):
            if A[i] % B[j] == 0:
                s *= 0
            else:
                s *= 1
        if s == 1:
            B.append(A[i])
        s = 1
    print(len(B))

Submission status: Wrong Answer

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

cnt = 0
for i in range(1, len(a)):
  flg = True
  for j in range(i):
    if i == j: continue
    if a[i] % a[j] == 0:
      flg = False
      break
  if flg: cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_str = []
a_str = input().split()
list = []
for i in a_str :
    a = int(i)
    list.append(a)
num = 0
for i in range(n):
    check = []
    for j in range(n):
        if i == j :
            continue
        b = list[i] % list[j]
        if b == 0 :
            continue
        else:
            check.append(b)
    if not 0 in check :
        num += 1
print(num)

Submission status: Wrong Answer

Solution code:
import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

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

count = 0
for i, ai in enumerate(an):
    if is_prime(ai) and an.count(ai) == 1:
        count+=1
    elif an.count(ai) == 1:
#         print(ai)
        factor = factorization(ai)
#         print(factor)
        for fn in factor:
            mat = 1
            is_factor = False
            for f in range(1, fn[1] + 1):
                mat = mat * fn[0]
#                 print(f'mat={mat}')
                if an.count(mat) >= 1 and mat != ai:
                    is_factor = True
                    break
            if is_factor:break
        if not is_factor:
            count+=1
print(count)

Submission status: Wrong Answer

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

from fractions import gcd
from collections import Counter,deque
from heapq import heappush, heappop, heappushpop, heapify

TMP = []

for i in range(len(A)):
        flag = 0
        _TMP = {A[i]}
        for j in range(len(TMP)):
                if (max(A[i], TMP[j]) % min(A[i], TMP[j])) == 0:
                        TMP[j] = min(A[i], TMP[j])
                        flag = 1
        if flag == 0:
                TMP = list(set(TMP) | _TMP)
        else:
                TMP = list(set(TMP))


if len(TMP) == 1:
        ans = 0
else:
        ans = len(set(TMP))

print (ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = list(map(int, input().split()))[0]
A = np.array(list(((map(int, input().split())))))
A = np.sort(A)
B = []

def get_result():
    result = 0
    for i in range(N):
        flag = True
        if i < N - 1 and A[i] == A[i + 1]:
            flag = False
        elif i > 0 and A[i] == A[i - 1]:
            flag = False
        for b in B:
            d, m = divmod(A[i], b)
            if m == 0:
                flag = False
                break
        if flag:
            result += 1
            B.append(A[i])
    return result

print(get_result())

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
*A, = map(int, input().split())
A.sort()
a = []
b = []
last = 0
for i in range(N):
    if last != A[i]:
        a.append([A[i], 0])
        b.append(A[i])
        last = A[i]
    a[-1][1] += 1


def factorList(n):
    # [素因数]=数を出力
    f = {}
    c = 0
    r = int(n**0.5)
    l = []
    for i in range(2, r+2):
        while n % i == 0:
            c += 1
            n = n//i
        if c != 0:
            l.append([i, c])
            c = 0
    if n != 1:
        l.append([n, 1])
    return l


def cmb(a, i, h, t):
    if i >= len(a):
        return h[t]
    for j in range(a[i][1]+1):
        d = cmb(a, i+1, h, t*pow(a[i][0], j))
        if d:
            return True
    return False


h = [False]*(10**6+1)
ans = 0
for n, c in a:
    if c == 1:
        fl = factorList(n)
        if len(fl) == 1 and fl[0][1] == 1:
            ans += 1
        elif not cmb(fl, 0, h, 1):
            ans += 1
    h[n] = True

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = Counter((list(map(int, input().split(' ')))))
ans = 0
for i in A.keys():
    flg = True
    if A[i] > 1:
        continue
    for j in range(1,int(pow(i,0.5))+2):
        print(j,' ',end="")
        if not i%j:
            if A[j] and i != j:
                flg = False
                break
            if j != i//j and A[i//j] and i//j != i:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
a = list(map(int,input().split()))
a.sort()
a = deque(a)
s = [True] * max(a)
cou = 0

if len(a) != 1:
  if a[0] == a[1]:
    cou -= 1
    while a[0] != a[1]:
      a.popleft()
      n -= 1

for i in range(n):
  if s[a[i] - 1] == True:
    cou += 1
    for j in range(max(a) // a[i]):
      s[a[i] * (j + 1) - 1] = False

      
print(cou)

Submission status: Wrong Answer

Solution code:
import pprint
from collections import defaultdict

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


def get_primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def is_prime(n):
    n_sqrt = n ** 0.5
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for num in range(3, int(n_sqrt), 2):
        if n == num:
            return True
        if n % num == 0:
            # 素数ではない
            return False
    return True


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

a_list.sort()
min_a = min(a_list)
max_a = max(a_list)

if min_a == max_a:
    print(0)
    exit()

prime_dict = defaultdict(lambda: int(1e8))

# primes_debug = defaultdict(list)

for a in a_list:
    factors = set(prime_factorize(a))
    # 1つでもこれより小さい素因数の数があればだめ
    flag = True
    for factor in factors:
        # primes_debug[factor].append(a)

        if a > prime_dict[factor]:
            flag = False
            break

    if flag:
        for factor in factors:
            prime_dict[factor] = a


# 複数要素が入っている場合
# 素因数分解して, 別の素因数がその数のみならOK
# 他の数が入っていたらだめ

# pprint.pprint(primes_debug)
# pprint.pprint(prime_dict)
print(len(prime_dict))

Submission status: Wrong Answer

Solution code:
n = int(input())

a=list(map(int,input().split()))
a.sort(reverse = True)
from collections import deque
from collections import Counter as cnt
from math import sqrt
aaa = dict(cnt(a))

maa = round(sqrt(a[0]))
ma = maa+2

ans = []
a = deque(a)
while True:
    if len(a) < 1 :
        break
    i = a.pop()
    ans.append(i)

    b = deque()
    while len(a)>0:
        j = a.pop()
        if j%i !=0:
            b.appendleft(j)
    a = b.copy()

    if i >= ma:
        ans += a
        break


mans = 0
for i,v in aaa.items():
    if (i in ans) & (v == 1) :
        mans+=1

print(mans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter

upper_bound = 200002

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

counter = Counter(nums)
dup = [key for key, value in counter.items() if value >= 2]

if 1 in dup:
	print(0)
	sys.exit()
elif 1 in counter.keys():
	print(1)
	sys.exit()

out = set()
for d in dup:
	if d not in out: # O(1)
		to_add = [d * i for i in range(1, 2 + upper_bound // d) if i not in out] # O(k)
		for y in to_add: # O(k)
			out.add(y)

nums = sorted([x for x in nums if x not in out])

cnt = 0
for x in nums:
	if x not in out:
		cnt += 1
		to_add = [x * i for i in range(1, 2 + upper_bound // x) if i not in out]
		for y in to_add:
			out.add(y)

print(cnt)

Submission status: Wrong Answer

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
                arr.append(i)
            # arr.append([i, cnt])

    if temp!=1:
        # arr.append([temp, 1])
        arr.append(temp)

    if arr==[]:
        # arr.append([n, 1])
        arr.append(n)

    return arr

A.sort()
from collections import defaultdict
# memo = dict()
# memo = defaultdict(int)
memo = set([])
ans = 0
same_dict = dict()
# tmp = factorization(82)
# print(tmp)
for a in A:
    tmp = factorization(a)
    flag = True
    u = []
    if tuple(tmp) in memo and tuple(tmp)not in same_dict:
        ans -= 1
        same_dict[tuple(tmp)] = 1
        continue

    for ele in tmp:
        u.append(ele)
        if tuple(u) in memo:
            flag = False
            break
    #     memo[ele[0]] = ele[1]

    if flag:
        memo.add(tuple(u))
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import random
def is_prime(q, k=3):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q-1)
        t = d
        y = pow(a, t, q)
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q-1 and t & 1 == 0:
            return False
    return True

n = int(input())
a = [int(_) for _ in input().split()]

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

a.sort()
#print(a)

ans = 0
div = []
if a[0] == a[1]:
    pass
else:
    ans += 1

div.append(a[0])

for i in range(1, n-1):
    if a[i] == a[i-1]:
        pass
    elif a[i] == a[i+1]:
        div.append(a[i])
    else:
        if is_prime(a[i]):
            ans += 1
            div.append(a[i])
        else:
            flg = True
            for j in div:
                if j*2 > a[i]:
                    break
                if a[i] % j == 0:
                    flg = False
                    break
            if flg:
                div.append(a[i])
                ans += 1
    #print(i, a[i], div, ans)

if a[n-1] == a[n-2]:
    pass
else:
    if is_prime(a[n-1]):
        ans += 1
    else:
        flg = True
        for j in div:
            if j*2 > a[n-1]:
                break
            if a[n-1] % j == 0:
                flg = False
                break
        if flg:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
a = []
cnt = 0

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

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

print(n-cnt)

Submission status: Wrong Answer

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

dic={}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]]=1
    else:
        dic[A[i]]+=1

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

if 1 in dic:
    if dic[1]>1:
        print(0)
        exit()
    else:
        print(1)
        exit()

ans=0
minn=min(A)
for i in range(N):
    if dic[A[i]]>1:
        continue
    if A[i]<minn*2:
        continue
    f=False
    for j in range(2, int(A[i]**0.5)+1):
        if A[i]%j==0:
            if j in dic or A[i]//j in dic:
                f=True
                break
    if f:
        continue
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
def calc():
    n, *a = map(int, open(0).read().split())
    a.sort()
    counts = set()
    double = set()
    r = set()
    for x in a:
        if x in counts:
            double.add(x)
            continue
        s = r & divs(x)
        if not s:
            counts.add(x)
        r.add(x)
    return len(counts) - len(double)

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

print(calc())

Submission status: Wrong Answer

Solution code:
# ミラー–ラビン素数判定法
# https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95

def isPrime_MR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1:
        ret[n] = 1
    if rhoFlg:
        ret = {x: ret[x] for x in sorted(ret)}

    return ret


def main():
    from collections import Counter
    n, *a = map(int, open(0).read().split())
    x = Counter(a)
    y = [k for k, v in x.items() if v == 1]
    if len(y) == 0:
        print(0)
        exit()

    z = sorted(y)

    if z[0] == 1:
        print(1)
        exit()

    cnt = 1
    check = [primeFactor(z[0])]
    for x in z:
        p = primeFactor(x)
        f = any(all(p.get(k) is not None for k, v in y.items()) for y in check)
        # print(x, f, check)
        if not f:
            check.append(p)
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

def get_prime_factors(n):
    dd = defaultdict(lambda: 0)
    if n > 1:
        i = 2
        while i * i <= n:
            if n % i == 0:
                dd[i] += 1
                n /= i
                i = 2
            else:
                i += 1
        dd[n] += 1
    return dd

def factor_with(n, A):
    idx = 0
    orig_n = n
    i = A[idx]

    while i * i <= n or idx >= len(A):
        i = A[idx]

        if A[idx] == orig_n:
            idx+= 1
        elif n % i ==0:
            n /= i
            idx = 0
        else:
            idx += 1
    return n

    
def solve(N: int, A: "List[int]"):
    
    A = sorted(list(set(A)))
    A = [a for a in A if a != 1]
    if len(A) <= 1:
        print(0)
        return
    
    count = 0
    for i in range(len(A)):
        div = True
        for j in range(0,i):
            if A[i] % A[j] == 0:
                div = False
                break
        if div:
            count += 1

        
    # dd = defaultdict(lambda: (0, 10**6+1))
    
    # for a in A:
    #     d = get_prime_factors(a)

    #     flag = True
    #     for prime, value in d.items():
    #         dd_val, dd_mn = dd[prime]
            
    #         if a % dd_mn==0:
    #             flag = False
    #             break

    #         dd[prime] = (dd_val + value, min(dd_mn, a))

    #     if flag:
    #         count+= 1

    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(n):
    ok = True
    for g in s:
        if a[i]%g==0:
            ok = False
            break
    if ok:
        s.add(a[i])
if len(s)==1:
    print(0)
else:
    print(len(s))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

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

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)

ans = 0

checks = [False] * (1000009)

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
    for j in range(a, 1000009, a):
        checks[j] = True

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

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

ans = 0
while len(A) > 0:
    ans += 1
    if max(A) < 2 * A[0]:
        ans += len(A[1:])
        break
    A = [a for a in A if a % A[0] != 0]

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
As = input().split()
A = []

for i in range(N):
    A.append(int(As[i]))

rA = sorted(A)

count = 0
dividable = False

if N > 1:
    if rA[0]%rA[1]!=0:
        count += 1
    for i in range(1, N):
        for s in range(i):
            if rA[i]%rA[s] == 0:
                dividable = True
                break
        if dividable==False:
            count += 1
        else:
            dividable = False
else:
    count = 1

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
ans = 0
for i in range(N):
    count = 0
    for j in range(N):
        if A[i]%A[j] != 0 and i != j: 
            count += 1
            if count == N-1:
                ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
alist = list(map(int, input().split()))
count=0

for i in range(n):
    temp_count = 0
    for j in range(n):
        if i == j:
            continue
        if alist[i] == alist[j]:
            continue
        
        if alist[i] % alist[j] != 0:
            temp_count += 1
        if temp_count == len(alist) - 1:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
Al = [int(i) for i in input().split()]

def primes(n):
    ans = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in Al:#range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i] and Al.count(i) == 1:
            ans.append(i)
    return ans

ans = primes(max(Al))
print(len(ans))

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)


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

    # divisors.sort()
    return divisors


N = int(input())
A = list(map(int, input().split()))
setA = set(A)
countA = Counter(A)
if countA[1] == 1:
    print(1)
    exit()
minA = min(A)

count = 0
for num in A:
    if countA[num] >= 2:
        continue
    divisors = make_divisors(minA, num)
    if any((e in setA) for e in divisors):
        continue
    count += 1

print(count)

Submission status: Wrong Answer

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

#Adic = {}

#for i in range(N):
#	Adic[A[i]] = i + 1

Asorted = sorted(A)
divlist = []
dup = [x for x in set(Asorted) if Asorted.count(x) > 1]
Asorterd = set(Asorted)

count = 0
for i in range(len(Asorted)):
	divflag = False
	#for j in range(i):
	for div in divlist:
		#if Asorted[i] % Asorted[i - j - 1] == 0:
		if Asorted[i] % div == 0:
			divflag = True
			break
	if divflag == False and Asorted[i] not in dup:
		divlist.append(Asorted[i])
		count+=1

print(count)

Submission status: Wrong Answer

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

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

else:
    for i in range(len(A)):
        value=A.pop(0)
        if all([value % i !=0 for i in result]):
            result.append(value)    
    print(len(result))

Submission status: Wrong Answer

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

for i in range(N):
    for j in range(1, N-i):
        if A[i]%A[j]==0 or A[j]%A[i]==0:
            count += 1
        # print(i+j)
    # print("---")
print(count-1)

Submission status: Wrong Answer

Solution code:
import os

n = int(input())
an = [int(i) for i in input().split()]
an.sort()
ans = [an[0]]

if len(list(set(an)))==1:
    print(0)
    exit()

for i in range(1,n):
    flag = True
    for j in ans:
        if an[i]%j==0:
            flag = False
            break
    if flag:
        ans.append(an[i])

answer = len(ans)

print(answer)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(map(int,input().split()))
numbers = [0]*(max(A)+1)

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]


answer = 0
for i in range(N):
    yakusu = make_divisors(A[i])
    judge = 1
    for j in range(1,len(yakusu)-1):
        if numbers[yakusu[j]] != 0:
            judge = 0
    if judge == 1:
        answer += 1
    numbers[A[i]]=1
    if A[i]==A[i-1]:
        answer -= 1
    
print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import combinations

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

comb = combinations(a,2)
nums = []
for comb_ in comb:
    comb_ = list(comb_)
    tmp = comb_[1]
    if (comb_[1] > comb_[0]):
        tmp = comb_[1]
        comb_[1] = comb_[0]
        comb_[0] = tmp
    if(comb_[0]%comb_[1] != 0):
        nums.append(comb_[1])
print(len(set(nums)))