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 heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


# def gcd(a, b):
#     if b == 0:
#         return a
#     return gcd(b, a % b)


# def lcm(a, b):
#     return a*b // gcd(a, b)


# def good(A, N):
#     # A = sorted(A)
#     ans = A[0]
#     # for i in range(1, N):
#     #     ans = fractions.gcd(A[i], ans)
#     for i in range(1, N):
#         ans = lcm(ans, A[i])
#     return ans

def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return is_prime


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


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def coprime(a, b):
    return gcd(a, b) == 1


def factorization(n):
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def main():
    N = I()
    A = LI()
    MX = 2 * 10**6
    ans = []

    if N == 1:
        print(0)
        return

    # for i in range(N):
    #     n = []
    #     for j in range(N):
    #         if i == j:
    #             continue
    #         n.append(A[i] % A[j] != 0)
    #     if all(n):
    #         ans.append(i+1)

    # print(len(ans))
    # print([A[i-1] for i in ans])

    a_map = Counter(A)

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

    ans = 0
    for i in range(N):
        if is_prime[A[i]] and a_map[A[i]] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# Problem D - Not Divisible

# input
N = int(input())
a_nums = list(map(int, input().split()))
a_nums = sorted(a_nums)

# initialization
fact_nums = {}
pattern = []
left = 0
right = N+1

# binary search
while right-left>1:
    mid = (right + left) // 2
    is_success = False

    # check
    tmp_count = 0
    for i in range(N):
        is_ok = True
        for j in range(i+1):
            if i==j:
                continue
            if a_nums[i]%a_nums[j]==0:
                is_ok = False
                break
        if is_ok:
            tmp_count += 1
            if tmp_count>=mid:
                is_success = True
                break

    if is_success:
        left = mid
    else:
        right = mid

if len(list(set(a_nums)))==1:
    left = 0

# output
print(left)

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections
input()

def no_Divisible(num,num_set):
    for row in num_set:
        if num%row==0:
            return 0
    return 1

count = 0
input_list = map(lambda x:int(x),input().split(" "))
koho = {key for key,value in collections.Counter(input_list).items() if value==1}
visi = set(input_list)

for num in koho:
    if no_Divisible(num,visi):
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
L = list(map(int,input().split()))
d = list(set(L))
l = len(d)
if l == 1:
    print(0)
    exit()
L.sort()
#print(L)
dp = [0]*(L[-1]+1)

for i in range(n):
    j = 1
    while L[i]*(j+1) < len(dp):
        #print(L[i],(j+1),len(dp))
        if not dp[L[i]*(j+1)]:
            dp[L[i]*(j+1)] = 1
        j +=1
#print(dp)
cnt = 0
for i in range(n):
    if dp[L[i]] == 0:
        cnt +=1
print(cnt)

Submission status: Wrong Answer

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



flag == 0
for i in range(N):
    C = []
    flag = 0
    for j in range(len(B)):
        if B[j] == A[i]:
            if flag == 0:
                C.append(B[j])
                flag = 1
        elif B[j] < A[i]:
            C.append(B[j])
        elif B[j] // A[i] != 0 and B[j] % A[i] != 0:
            C.append(B[j])
    B = C

if len(B) > 1:
    print(len(B))
else:
    print(0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline().rstrip("\n"))
a = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
a.sort()
a_true = [True]*n
a_set = set(a)
if 1 in a or len(a_set) == 1:
    print(0)
else:
    a_max = a[n-1]
    i = 0
    while a[i]*2 <= a_max:
        for j in range(i+1,n):
            if a[j] % a[i] == 0:
                a_true[j] = False
        i += 1
    while i < n-1:
        if a[i] == a[i+1]:
            a_true[i] = False
            a_true[i+1] = False
        i += 1
    print(len([i for i in range(0, n) if a_true[i]]))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
from collections import defaultdict
d = defaultdict(int)
ans = 0
for i in range(N):
    d[a[i]] += 1
for i in range(1,1001):
    if d[i] == 1:
        ans += 1
        for j in range(2,2+10**6//i):
            d[j*i] = 0
    elif d[i] >= 2:
        for j in range(2,2+10**6//i):
            d[j*i] = 0
for i in range(1001,1000001):
    if d[i] == 1:
        ans += 1
print(ans)

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, N):
        if i != j and A[i] % A[j] == 0:
            break
        if j == N-1:
            count += 1
    if i == N-1 and A[N-1] in A[:N-1]:
        count -= 1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [a[0]]
for i in range(1,n):
    v = 1
    for j in range(len(p)):
        if a[i] % a[j] != 0 :
            if a[i] < 2*a[j]:
                break
        else :
            v = 0
            break
    if v == 1:
        p.append(a[i])
ans = len(p)
for i in range(n-2):
    if a[i] == a[i+1] and a[i+1] != a[i+2] and a[i] in p:
        ans -= 1
if n > 1:
    if a[-1] == a[-2] and a[-1] in p:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
ans = 0
maxB = 0
for i in range(0, n, 1):
    if (arr[i] > maxB):
        maxB = arr[i]

mark = [0 for i in range(maxB+1)]
for i in range(0, n, 1):
    for x in range(2*arr[i], maxB, arr[i]):
        mark[x] += 1
ans = 0
for i in range(0, n, 1):
    if (mark[arr[i]] != 0):
        ans += 1
print(ans)

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 set(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 bisect

n = int(input())

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

a_i.sort()

s = set()

answer = 0

for i in range(n):
    if i not in s:
        a = a_i[i]
        plus = 0
        while a == a_i[i+plus]:
            s.add(i + plus)
            plus += 1
            if i + plus >= n:
                break
        if plus == 1:
            answer += 1
            times = 2
            while times * a < a_i[-1]:
                times_point = bisect.bisect_left(a_i, a * times)
                if a_i[times_point] % a == 0:
                    s.add(times_point)
                times += 1

print(answer)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()

a.sort()

if a.count(a[0])==n:
	print(0)
	exit()

maxa = max(a)+1

ans = [0]*maxa
for i in a:
	ans[i] = 1



for j in a:
	if ans[j]==0:
		pass
	for i in range(j*2,10**6+1,j):
		if i>maxa-1:
			break
		ans[i] = 0

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
def resolve():
    n = int(input())
    aaa = list(map(int, input().split()))
    aaa.sort()
    judge = [1] * len(aaa)
    for i in range(len(aaa) - 1):
        if judge[i]:
            for j in range(i + 1, len(aaa)):
                if aaa[j] % aaa[i] == 0:
                    judge[j] = 0
            if aaa[i] == aaa[i + 1]:
                judge[i] = 0
        else:
            continue
    print(sum(judge))


import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(input, output)


if __name__ == "__main__":
    unittest.main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
count=0
for i in range(n-1):
    t=0
    if a[i]==a[i-1]:
        continue
    for j in reversed(range(i+1,n)):
        if a[i]%a[j]==0:
            break
        if a[i]//2<a[j]:
            t=1
            break
    else:
        count+=1
    if t==1:
        count+=1
if a[n-1]==a[n-2]:
    print(count)
else:
    print(count+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
A = list(sorted(A))
result = [True for i in range(N)]
for i in range(N):
    if not result[i]:
        continue
    A_i = A[i]
    for j in range(i+1, N):
        if not result[j]:
            continue
        A_j = A[j]
        if A_j % A_i == 0:
            result[j] = False

# 結果出力
print(sum(result))

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

A.sort()

for i in range(N):
    if len(A) == i+1:
        break
    try:
        if A.count(A[i])>=2:
            for t in range(A.count(A[i])):
                A.remove(A[i])
    except: pass
    k=i+1
    for j in range(i+1,len(A)):
        if A[k]%A[i]==0:
            A.remove(A[k])
        else:
            k += 1

print(len(A))

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    if i == 0 and n > 1:
        if A[i] != A[i+1]:
            ans += 1
    for j in range(i):
        if A[i] % A[j] == 0:
            break
        if j == i - 1:
            if j + 2 < n:
                if A[i] != A[j+2]:
                    ans += 1
            else:
                ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
a = list(map(int, input().split()))
na = np.array(a)
cnt = 0
for i in range(n):
    l = na % na[i] == 0
    m = np.count_nonzero(na % na[i] == 0)
    if m == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

count = 0
for Ai in A:
  flag = 0
  double = 0
  for Aj in sortedA:
    if Aj > Ai / 2:
      break
    if Ai == Aj:
      double += 1
      continue
    if (Ai % Aj) == 0:
      flag = 1
      break
  if flag == 0 and double < 2:
    count += 1

print(count)

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

n = inp()
x = ip()
if len(set(x)) == 1:
    print(0)
elif len(x) == 1 or 1 in x:
    print(1)
else:
    x.sort(reverse= True)
    ct = 1
    for i in reversed(range(n-1)):
        flag = 1
        for j in reversed(range(i+1,n)):
            if x[i]%x[j] == 0:
                flag = 0
                break
        if flag:
            ct += 1
    print(ct)

Submission status: Wrong Answer

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

A.sort()

ans_list=[]
for i in range(N):
  for j in range(i+1,N):
    if math.sqrt(A[i])>A[j]:
      break
    else:
      temp=math.gcd(A[i],A[j])
      if A[i]==temp:
        ans_list.append(j)  
      

print(N-len(set(ans_list)))
#print(gcd_list)

Submission status: Wrong Answer

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

if n==1 or 1 in a:
    print(1)
    exit()

if a[0] in a[1:]:
    ans = 0
else:
    ans = 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]

div = set([a[0]])
for i in a[1:]:
    x = set(make_divisors(i))
    if not x&div:
        ans += 1
    div.add(i)
print(ans)

Submission status: Wrong Answer

Solution code:
def 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 main():
    n = int(input())
    a = list(map(int,input().split()))
    mx = max(a)
    a.sort()
    if a[0] == 1:
        print(0)
        return
    ary = primes(mx)
    # import heapq
    # heapq.heapify(a)
    import collections
    cnt = collections.Counter(a)

    now = ary[0]
    idx = 0
    ans = []
    tmp = []
    for i, aa in enumerate(a):
        flg = False
        while idx < len(ary):

            if ary[idx] == aa:
                if cnt[aa] == 1:
                    ans.append(aa)
                    flg = True
                    idx += 1
                    # now = ary[idx]
                    break
            if ary[idx] > aa:
                break
            idx += 1


        if not flg:
            tmp.append(aa)
    

    from collections import deque
    dq = deque(tmp)
    for i in range(n):
        if len(dq) == 0:
            break

        tmp1 = dq.popleft()
        flg = False
        for j in range(n):
            tmp2 = a[j]
            if tmp1 <= tmp2:
                break
            if tmp1 % tmp2 == 0:
                flg = True
                break
            # dq.append(tmp2)
        if cnt[tmp1] > 1:
            continue
        if flg:
            continue
        ans.append(tmp1)

    print(len(ans))





if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
A=list(map(int, input().split()))
A.sort()
A=np.array(A)
u, counts = np.unique(A, return_counts=True)
B=u[counts != 1].size
j=0
C=0
while True:
  try:
    A=A[A%A[0]!=0]
    C=C+1
  except:
    break
C=C-B
print(C)

Submission status: Wrong Answer

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

if A.count(1) >= 1:
    print(A.count(1))
    exit()

num = [0]*1000005
for a in A:
    num[a] += 1

b = [False]*1000005
seen = [False]*1000005
cnt = 0
A = list(set(A))
A.sort()
for a in A:
    if seen[a]:
        continue

    seen[a] = True
    if b[a] == False:
        cnt += 1
        if num[a] > 1:
            cnt -= 1

    for i in range(a, 1000005, a):
        b[i] = True
print(cnt)

Submission status: Wrong Answer

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

s = set()
x = a[0]

count = 0
for i in range(n):
    flg = True
    flg2 = False
    if i < n - 1 and a[i] == a[i + 1]:
        flg = False
        flg2 = True
    if a[i] in s:
        flg = False

    if flg:
        count += 1
    if flg or flg2:
        x = a[i]
        while x < 10 ** 6:
            s.add(x)
            x += a[i]
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
ok=False
ans=0
val=a[0]
for i in range(1,n):
    if val%a[i]!=0:
        ans+=1
    val*=a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
#x,n=map(int,stdin.readline().split())
n=int(stdin.readline());ans=1
a=sorted(map(int,stdin.readline().split()))
if len(set(a))==1:
    print(0)
    exit(0)
for i in range(n):
    for j in range(i):
        if a[i]%a[j]==0:
            break
        if j==i-1:ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = LI()
    A = LI()

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


    z = []
    for i in range(1001):
        if y[i] > 0:
            z.append(i)

    ans = 0
    for i in A:
        if i > 1:
            if y[1] : continue
        if y[i] > 1: continue


        f = 1
        for j in z:
            if i == j: continue
            if i % j == 0 and (y[j] or y[i//j]):
                f = 0
                break

        ans += f

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
arr = []
du = set()
t = 0

for i in range(n):
    if a[i] == t:
        if arr and arr[-1] == t:
            du.add(a[i])
        continue
    t = a[i]
    q = a[i] ** 0.5
    for tmp in arr:
        if a[i] % tmp == 0:
            break
        if tmp > q:
            arr.append(a[i])
            break
    else:
        arr.append(a[i])

print(len(arr) - len(du))

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

temp = dict(map(lambda x: (x, x[0] % x[1]), permutations(set(nums), 2)))
not_ans = set(map(lambda x: x[0], filter(lambda x: temp[x] == 0, temp)))

ans = list(filter(lambda x: not x in not_ans, nums))

print(len(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
for num, i in enumerate(a):
    if(num<len(a)-1):
        if(i == a[num+1]):
            a = list(set(a) - set([i])) 
b = set(a)
for i in a:
    for j in range(2, (a[-1]//i+1)):
        b = b - set([i*j])
print(len(b))

Submission status: Wrong Answer

Solution code:
n = int(input())

from collections import defaultdict

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

d = defaultdict(int)

for el in a:
    d[el] += 1

count = 0

d = sorted(d.items(), reverse=True)
# wm = d[0][0]

while len(d):
    a, c = d.pop()
    if c == 1:
#         print(f'count {a=}, {c=}, {count=}, {d=}')
        count += 1
    if a == 1:
        break
    if len(d):
        m = d[0][0]
    else:
        m = a - 1
    if a * 2 <= m and a * a <= 10 ** 6:
        d = [elm for elm in d if elm[0] % a]
    else:
        d = [elm for elm in d if elm[1] == 1]
        count += len(d)
        break

print(count)

Submission status: Wrong Answer

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

p = sorted(wklst,reverse=True)

res = 0
wk = 0
pp = 1
for i in range(n):
    if wk == p[i]:
        res += pp
        continue
    pp = 1
    lmt = p[i]//p[n-1]
    for j in range(n-1,i,-1):
        if p[i] % p[j] == 0:
            pp = 0
            break
        if p[j] > lmt :
            break
    wk = p[i]
    res += pp

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
i = 0
ans = 0 
A.sort()
A.reverse()
if A[n-1] == 1:
    if A[n-2] != 1:
        print(1)
        exit()
    else:
        print(0)
        exit()
while i <= n-2:
    for j in range(i+1,n):
        if A[i] % A[j] == 0:
            break
        elif j == n - 1:
            ans = ans + 1
    i = i + 1
if A[n-1] == A[n-2]:
    print(ans)
else:
    print(ans+1)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n == 1:
        print(1)
        return
    l = list(map(int,input().split()))
    l.sort(reverse=True)

    num=0
    for i in range(len(l)-1):
        for d in l[i+1:]:
            if (l[i]/d).is_integer():
                num += 1
                break
    if l[-2]==l[-1]:
        num += 1
    print(len(l)-num)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def prime_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())
l = list(map(int,input().split()))
l.sort()

#全部同じ時
if l[0] == l[n-1]:
    print(0)
    exit()

#1が入っている時
if l[0] == 1:
    print(0)
    exit()

d = {}
ans = n

for i in range(n):
    if i == 0:
        for j in prime_factorization(l[0]):
            d[j[0]] = j[1]
    else:
        count = 0
        A = prime_factorization(l[i])
        for j in A:
            if j[0] not in d.keys():
                d[j[0]] = j[1]
            if d[j[0]] <= j[1]:
                d[j[0]] = j[1]
                count += 1
            else:
                count += 1
        if count == len(A):
            n -= 1
print(n)

Submission status: Wrong Answer

Solution code:
import os

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

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)
if answer==1:
    print(0)
else:
    print(answer)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


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

    return sorted(ans)


def main():
    N = int(input())

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

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

    for a in A:
        is_in_A_flag[a] += 1

    # B = [None] * N
    # for i in range(N):
    #     B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        # ys = yakusu(A[i])

        for k in range(1, int(A[i]**0.5) + 1):
            if A[i] % k == 0:  # kはA[i]の約数]
                # ans.append(i)
                if is_in_A_flag[k] > 0:
                    is_ans = False
                    break

                q = A[i] // k

                if q != k:
                    if q == A[i]:
                        if is_in_A_flag[q] > 1:
                            is_ans = False
                            break
                    elif is_in_A_flag[q] > 0:
                        is_ans = False
                        break
        if is_ans:
            ans += 1

        # for j in range(len(ys)-1):
        #     b = ys[j]
        #     if is_in_A_flag[b] > 0:
        #         is_ans = False
        #         break

        # if is_ans:
        #     if is_in_A_flag[ys[-1]] > 1:
        #         is_ans = False

        # if is_ans:
        #     ans += 1

    return ans


print(main())

Submission status: Wrong Answer

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

    return_count = 0
    for i in A:
        break_flag = True
        for j in A:
            if i % j == 0 and i != j:
                break_flag = False
                break
        if break_flag:
            return_count += 1

    return return_count

print(Not_Divisible())

Submission status: Wrong Answer

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

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

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

b = []
pre = a[0]
if a[0] != a[1]:
    if pre == 1:
        print(1)
        sys.exit()
else:
    if pre == 1:
        print(0)
        sys.exit()
c = collections.Counter(a)
for k,v in c.items():
    if v == 1:
        b.append(k)

judge = [False for i in range(10**6+1)]
for num in b:
    judge[num] = True
for i in range(1,(10**6)):
    if judge[i]:
        for j in range(i*2,10**6+1,i):
            judge[j] = False
ans = 0
for i in range(1,10**6+1):
    if judge[i]:
        ans+=1
print(ans)