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 sympy
from collections import defaultdict, Counter
# def factors(N): #約数を全て求める。ただし、順不同
#     from collections import deque
#     ret = deque()
#     middle = int( N**(1/2))
#     for i in range(1, middle):
#         if N%i == 0:
#             ret.append(i)
#             ret.append(N//i)
            
#     if N%middle == 0:
#         ret.append(middle)
#         if middle != N//middle:
#             ret.append(N//middle)
#     return ret

def make_divisors(n, CA, d):
    # divisors = []
    if CA[n] > 1:
        return False
    if n == 1:
        if CA[1] > 1:
            return False
        else:
            return True
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            if d[i]:
                return False
            if i != n // i:
                if d[n//i]:
                    return False
    return True

def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    for a in A:
        d[a] = True
    ans = 0
    for a in A:
        if make_divisors(a, CA,d):
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
asor = sorted(a)
cnt = 0
cnt2 = []
aho = 0
while True:
    if asor == []:
        break
    if len(asor) == 1:
        cnt +=1
        break
    num = asor[0]
    big = asor[-1]
    if asor[1] == num:
        cnt2.append(num)
    cnt += 1
    asor.pop(0)
    for i in range (1,big//num +1):
        try :
            asor.pop(asor.index(num*i))
        except ValueError:
            aho +=1
cnt3 = len(cnt2)
print(cnt-cnt3)

Submission status: Wrong Answer

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

ok = []
ng = []

for i in range(n):
  for j in range(n):
    
#    print(i, j)
#    print("a[i]:",a[i])
#    print("a[j]:",a[j])
    
    if i == j:
      continue
    else:
      if a[i] % a[j] != 0:
        ok.append(a[i])
      else:
        ng.append(a[i])
        
result = list(set(ok) - set(ng))
        
print(len(result))

Submission status: Wrong Answer

Solution code:
N = int(input())
Alist = list(map(int, input().split()))
ret = 0

for i in range(N):
  for j in range(N):
    if (Alist[i] % Alist[j]) != 0:
      break
  if j + 1 == N:
  	ret += 1

print( ret )

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
count=0
for i in range(1,n+1):
    for x in range(1,n+1):
        if i!=x and a[i-1]%a[x-1]==0:
            count+=1
            break

if count==0:
    print(0)
else:
    print(n-count)

Submission status: Wrong Answer

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

a.sort()
d = {}

ans = 0
for i in range(n):
    #print(d)
    if a[i] not in d.keys():
        if a.count(a[i]) == 1:
            ans += 1
        for j in range(1,1000):
            d[a[i]*j] = 0

print(ans)

Submission status: Wrong Answer

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

def solve():
    ans = 0
    count = 0
    for i in range(1, 1000001):
        if i in a_i:
            for j in range(n):
                if i != a_i[j] and i % a_i[j] == 0:
                    break
            else:
                ans += 1
            count += 1
        if count == n:
            break
    return ans

print(solve())

Submission status: Wrong Answer

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

for i in range(n):
  for j in range(n):
    if i == j:pass
    elif li[i]%li[j] == 0:break
    elif j == n-1:count +=1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
cnt = 1
flg = True
a.sort()
for i in range(1,N):
  for j in range(i):
    if i != j and a[i] % a[j] == 0:
      flg = False
      break
  if flg:
    cnt += 1
  flg = True
print(cnt)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
d = list(map(int, input().strip().split()))

# 重複しているやつは削除
counts = collections.Counter(d)
d = []
for a, c in counts.items():
    if c == 1:
        d.append(a)

d = sorted(d)
dic = {a: True for a in d}
if len(dic) == 0:
    print(0)
    exit(0)

last = d[-1]
keys = dic.keys()

for k in keys:
    if dic[k]:
        n = 2
        while k * n <= last:
            if k * n in dic:
                dic[k * n] = False
            n += 1

count = len([True for v in dic.values() if v])
print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
a = list(map(int, input().split()))
p = []

a.sort()
p.append(a[0])
for i in range(1,N):
    flag = True
    for j in range(len(p)):
        if j**2>i:
            break
        if a[i]%p[j]==0:
            flag =False
            break
    if flag:
        p.append(a[i]) 

print(len(p))

Submission status: Wrong Answer

Solution code:
def check(s, a, next):
    if a==next:
        return False
    if 1 in s or a in s:
        return False
    while a%2==0:
        if 2 in s:
            return False
        a //= 2
        if a in s:
            return False
    x = 3
    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:
N = int(input())
A = sorted(list(map(int,input().split())))

if A.count(A[0])==N:
    print(0)
    exit(0)

flag = [0 for _ in range(N)]
for n in range(N):
    if flag[n] == 1: continue
    for i in range(n+1,N):
        if flag[i] == 1: continue
        if A[i]%A[n] == 0:
            flag[i] = 1

print(N-sum(flag))

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    def eratos(n):
        flag = [True] * (n + 1)
        for i in range(2, int(n**0.5) + 1):
            if flag[i]:
                for j in range(2*i, n + 1, i):
                    flag[j] = False
        return [i for i, x in enumerate(flag) if x and i >= 2]
    n = int(input())
    A = sorted(list(map(int, input().split())))
    c = Counter(A)
    result = 0
    piyo = []
    prime = eratos(1001)
    for k, v in c.items():
        if v > 1:
            piyo.append(k)
            for _ in range(v):
                A.remove(k)
    for a in A:
        flag = False
        if a in prime:
            piyo.append(a)
            result += 1
            continue
        for hoge in piyo:
            if a % hoge == 0:
                flag = True
                break
        if not flag:
            piyo.append(a)
            result += 1
    print(result)
main()

Submission status: Wrong Answer

Solution code:
import collections

n= int(input())
a= list(map(int, input().split()))
a=collections.Counter(a)
a=a.most_common()
b=[]
for i in range(len(a)):
    if a[i][1]==1:
        b.append(a[i][0])

v=[0]*(pow(10,6)+1)
b.sort()
ans=0
for i in b:
    if v[i]==0:
        ans+=1
        x = pow(10, 6) // i
        for j in range(1,x + 1):
            v[i*j]=1
print(ans)

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:
    print(0)
    exit()

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

ans=0
for i in range(N):
    if dic[A[i]]>1:
        continue
    f=False
    div=make_divisors(A[i])
    for d in div:
        if d in dic:
            f=True
    if f:
        continue
    ans+=1

print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)
cnt=len(A)

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

if len(A) >= 2 and A[-1] == A[-2]:
    print(cnt-1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
num_list = set(sorted(list(map(int, input().split()))))
cnt = 0

for num in num_list:
  div_list = [num%x == 0 if x != num else False for x in num_list]
  if not any(div_list) and len(div_list) != 1:
    cnt += 1
print(cnt)

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):
    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
print(num + 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from typing import List
from bisect import bisect


def not_divisible(A: List[int]) -> int:
    A = sorted(A)
    B = []
    for a in A:
        for b in B:
            # print("{} % {} = {}".format(a, b, a % b))
            if not (a % b):
                # print("break")
                break
        else:
            B.append(a)

    ans = len(B)
    for b in B:
        i = bisect(A, b, 0, len(B))
        if i < len(B) and A[i] == b:
            ans -= 1
    return ans


if __name__ == "__main__":
    _ = int(input())
    A = [int(a) for a in input().split()]
    ans = not_divisible(A)
    print(ans)

Submission status: Wrong Answer

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

def mp(): return map(int, input().split())
def lmp(): return 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, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

n = int(input())
a = lmp()
a.sort()
p = set()
cnt = 0
for i in range(n):
    flag = True
    for j in range(i+1):
        if i == j:
            continue
        elif a[i] % a[j] == 0:
            flag = False
            break
    if flag:
        cnt += 1
for i in range(1, n):
    if a[0] % a[i] == 0:
        cnt -= 1
        break
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
An = list(map(int, input().split()))
ans = 0
ng = set()
a_An = np.array(An)
for i, a in enumerate(An):
    temp = a_An / a
    temp[i] = 0.1
    check = np.where(temp % 1 == 0)
    check = np.delete(check, np.where(check == i))
    # check = check[check != i]
    print(check)
    if len(check) > 0:
        ng = ng | set(check)
print(N-len(ng))

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()))
sort_A = sorted(A)
reve_A = sorted(A, reverse=True)
if A.count(A[0]) == len(A):
    print(0)
    exit()
for i in range(n):
    chk = True
    for j in range(n-i-1):
        if reve_A[i] % sort_A[j] == 0:
            chk = False
            break
        #print(sort_A[i], reve_A[j])
    if chk == True:
        ans += 1
    else:
        pass
print(ans)

Submission status: Wrong Answer

Solution code:


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

ma = max(A)
first = [0]*(ma+3)
seen = [False]*(ma+3)

for i in range(N):
    a = A[i]
    if first[a] == 0:
        first[a] += 1
    elif first[a] == 1:
        ans -= 1
        first[a] += 1
    else:
        first[a] += 1


    if not seen[a]:
        #print(i+1,a)
        ans += 1
    for j in range(a,ma+3,a):
        seen[j] = True
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

a.sort(reverse = True)

count = 0
ans = 0

if len(set(a)) == 1:
    print(0)
else:
    
    for i in range(n):
        count += 1
        for j in range(count, n):
            if a[i] % a[j] == 0:
                ans += 1
                break
    
    
    print(n - ans)

Submission status: Wrong Answer

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

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]

ans = 0
num = []
suuji = 0

for i in range(N):
  num = make_divisors(A[i])
  suuji = A[i]
  A.pop(i)
  if len(set(A) & set(num)) >= 1:
    ans += 1
  A.append(suuji)

print(N - ans)

Submission status: Wrong Answer

Solution code:
import sys
import math

x=int(input())
l=list(map(int,input().split()))
l.sort()
l.append(-1)
count=0
l2=[]
t=-1
for i in range(len(l)):
    if l[i]!=t and count==1:
        l2.append(t)
        count=0 
    t=l[i]
    count+=1
count=0
for i in range(len(l2)):
    count+=1
    for j in l2[:i]:
        if l2[i]%j==0:
            count-=1
            break
print(count)

Submission status: Wrong Answer

Solution code:
def calc():
    n, *a = map(int, open(0).read().split())
    appear = {}
    for x in a:
        if x in appear:
            appear[x] = False
        else:
            appear[x] = True

    r = set(a)
    count = 0
    for x in r:
        s = r & divs(x)
        if not s and appear[x]:
            count += 1
    return count

def divs(x):
    ds = set()
    for i in range(2, x):
        if x % i == 0:
            ds.add(i)
    return ds

print(calc())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
 
## input
 
# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]

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
 
N=int(input())
A=list(map(int, input().split()))


A.sort()
count = 0
print(A)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
if n == 1:
    print(0)
    quit()
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
M = max(a)
cnt = [0]*(M+1)
ans = 0
for i in range(n):
    if cnt[a[i]]:
        continue
    j = a[i]
    if i == 0:
        if a[i] == a[i+1]:
            1
        else:
            ans += 1
    elif i == n-1:
        if a[i-1] == a[i]:
            1
        else:
            ans += 1
    elif a[i] == a[i+1] or a[i-1] == a[i]:
        1
    else:
        ans += 1
    while j <= M:
        cnt[j] = 1
        j += a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
alist = list(map(int, input().split(" ")))
settle = list(set(alist))

for i in settle:
  for j in alist:
    if j%i==0 and j//i>=2:
      alist.remove(j)

for m in alist:
  if alist.count(m)>=2:
    for k in range(alist.count(m)):
      alist.remove(m)
print(len(alist))

Submission status: Wrong Answer

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 1:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]





n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
count = 0
data = a.copy()
prime = []
limit = a[-1]/2
while len(data) > 0:
  p = data[0]
  if len(data) > 1 and p == data[1]:
    count += 1
  if limit <= p:
    prime = prime + list(set(data))
    break
  prime.append(p)
  data = [e for e in data if e % p != 0]
  #print(data)
print(len(prime)-count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
if n == 1:
	print(1)
	exit()
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)

if 1 in bset:
	if t[1] == 1:
		print(1)
		exit()
	else:
		print(0)
		exit()

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(10000)

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

table=[0]*(10**6+1)
for i in range(n):
    table[A[i]]+=1

for i in range(n):
    if table[A[i]]==1:
        j=2
        while A[i]*j<10**6+1:
            if table[A[i]*j]>0:
                table[A[i]*j]=2
            j+=1

cnt=0
for x in table:
    if x==1:
        cnt+=1
print(cnt)
#print(table)

Submission status: Wrong Answer

Solution code:
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]

n=int(input())
A=list(map(int,input().split()))
tmp = {}
for a in A:
  tmp[a]=tmp.get(a,0)+1
A = set([i for i in tmp if tmp[i]==1])
cnt = 0
for a in A:
  ds = make_divisors(a)[:-1]
  isOK = True
  for d in ds:
    if d in A:
      isOK = False
      break
  if isOK:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys


n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
y = [0 for i in range(max(a) + 1)]
same = [0 for i in range(max(a) + 1)]
for i in a:
    same[i] += 1

# 約数
def divisor(x):
    ret = []
    for i in range(1, int(x ** 0.5) // 2 + 1):
        if x % i == 0:
            if y[i] == 1 or y[x // i] == 1:
                return False
    return True


ans = 0
for i in a:
    if divisor(i) and same[i] <= 1:
        ans += 1
    y[i] = 1


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    l = sorted([int(i) for i in input().strip().split()])
    same = set()
    for i, n in enumerate(l):
        if n == -1:
            continue
        if i < len(l)-1:
            for j, m in enumerate(l[i + 1:]):
                if m == n:
                    same.add(n)
                if m % n == 0:
                    l[i + j + 1] = -1
    ans = len(set(l)) - 1 - len(same)

    return ans


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

Submission status: Wrong Answer

Solution code:
from collections import deque


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

    targets = [x for x in set(targets) if targets.count(x) == 1]
    if len(targets) == 0:
        print(0)
        return
    targets.sort()
    targets = deque(targets)

    ans = []

    while len(targets) > 0:
        target = targets.popleft()
        canAdd = True
        for x in ans:
            if target % x == 0:
                canAdd = False
                break
        if (canAdd):
            ans.append(target)

    print(len(ans))

resolve()

Submission status: Wrong Answer

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

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

print(n-a.count(0))

Submission status: Wrong Answer

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

A.sort()
checked = []
ans = 0
before = 0
first = True
for i in A:
    if before == i and first:
        if flag:
            ans -= 1
        first = False
        break
    else:
        first = True
    flag = True
    for l in checked:
        if i % l == 0:
            flag = False
            break
    if flag:
        checked.append(i)
        ans += 1
    before = i

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = deque(sorted(map(int, input().split())))
sub = deque()

ans = []
if len(set(A)) == 1:
    print(0)
else:
    while len(A):
        x = A.popleft()
        for a in A:
            if a % x != 0:
                sub.append(a)

        ans.append(x)
        A = sub
        sub = deque([])
    print(len(ans))

Submission status: Wrong Answer

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

A.sort()
ans = 0

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
A = list(map(int,(input().split())))
A.sort()
l = []
ans = 0
tmp = A[0]
for i in range(N):
    if i != N-1:
        tmp = A[i-1]
        if A[i] != A[i+1]:
            now = A[i]
            for j in range(len(l)):
                if now % l[j] == 0:
                    break
            else:
                l.append(now)
                if i == 0 or now != tmp:
                    ans += 1
    else:
        tmp = A[i-1]
        now = A[i]
        for j in range(len(l)):
            if now % l[j] == 0:
                break
        else:
            l.append(now)
            if now != tmp:
                ans += 1
print(ans)

Submission status: Wrong Answer

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

while i < len(A):
    j = 1
    while i+j < len(A)-1 and A[i] == A[i+j]:
        j += 1
    if j > 1:
        ans += j 
        A = A[:i+1] + A[i+j:]
    else:  
        border = A[i] // 2
        for j in range(i):
            if A[i] % A[j] == 0:
                ans += 1
                del A[i]
                i -= 1
                break
            elif A[j] > border:
                break
    i += 1

print(N - ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
al = [int(i) for i in input().split()]  
al.sort()
from collections import Counter
c = Counter(al)

if n == 1:
  print(0)
else:
  total = 0
  l = len(al)
  while l > 0:
    num = al.pop(0)
    if c[num] == 1:
      total += 1
    al = list(filter(lambda x: x % num != 0, al))
    l = len(al)
  print(total)

Submission status: Wrong Answer

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

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

print(n-f-1)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

ans = [a[0]]

for i in range(1, n):
    flag = True
    for j in ans:
        if a[i] == j:
            if i < n-1:
                if a[i] != a[i+1]:
                    ans.remove(j)
            elif i == n-1:
                ans.remove(j)
            flag = False
            break
        elif a[i] % j == 0:
            flag = False
            break
        else:
            continue
    if flag:
        ans.append(a[i])
        
print(len(ans))

Submission status: Wrong Answer

Solution code:
# coding:utf-8

N = int(input())
A = sorted(list(map(lambda x:int(x), input().split())))

count = 0
for i in range(N):
  flag = True
  for j in range(0, i):
    if(i == j):
      continue
    if(A[i] % A[j] == 0):
      flag = False
      break
  if(flag):
    count +=1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
set_A = set(A)
if len(A) != len(set_A):
    print(0)
else:
    factors = {}
    for a in A:
        a_orig = a
        for i in range(2, int(a**(1/2))+1):
            cnt = 0
            while a % i == 0:
                a /= i
                cnt += 1
            if cnt > 0:
                factors[i] = cnt
        if a != 1:
            factors[a] = 1
    print(len(factors))

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
if 1 in arr:
    print(1)
    quit()
d={}
ans=0
for i in arr:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
for i in range(n):
    x=arr[i]
    if d[x]==1:
        f=1
        for j in range(2,int(x**0.5)+1):
            y=x//j
            if (j in d and x%j==0) or ( y in d and x%(y)==0):
                f=0
                break
        if f==1:
             ans+=1
print(ans)

Submission status: Wrong Answer

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

A.sort()
ans=0

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

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

if A[0]==1 and A[1]==1:
    print(0)
    exit()
elif A[0]==1 and A[1]!=1:
    print(1)
    exit()

for i in range(1,N):
    if A[i]==A[i-1] or ((i!=N-1) and (A[i]==A[i+1])):            
        continue
    for j in range(i):
        if A[i]%A[j]==0 or A[i]>A[j]*2:
            break
        if j==i-1:
            ans+=1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def solve():
    ans = 0
    count = 0
    for i in range(1, 1000001):
        if i in a_i:
            for j in range(n):
                if i != a_i[j] and i % a_i[j] == 0:
                    break
            else:
                ans += 1
        count += 1
        if count == n:
            break
    return ans

print(solve())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

nums.sort()

t = [nums[0]]

for num in nums:
    is_add = True
    for n in t:
        if num % n == 0:
            is_add = False
            break
    
    if is_add:    
        t.append(num)
          
if n >= 2 and len(set(nums)) == 1:
    print(0)
else:
    print(len(t))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 21:14:26 2020

@author: NEC-PCuser
"""

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

A.sort()


li = []
before_value = 0
next_flg = False
for n in A:
    if len(li) == 0:
        li.append(n)
        next_flg = True
    if before_value == n:
        if li[len(li) - 1] == n:
            li.pop(len(li) - 1)
        next_flg = False
        before_value = n
        continue
    before_value = n
    if next_flg is True:
        next_flg = False
        continue
    """
    for i in range(0, len(li)):
        if (n % li[i] == 0):
            break
        if (n < li[i] * 2):
            li.append(n)
            break
    else:
        li.append(n)
    """

print(len(li))