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)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
A = sorted(A)
if A[0] == 1:
    print(1)
    exit()

from collections import Counter

c = Counter(A)

a = 0
D = []
for i in c.keys():
    D.append(i)
    if c[i] >= 2:
        a += 1

D = sorted(D)

ans = 0
B = [0]*(10**6+1)
for i in range(len(D)):
    if B[D[i]] == 0:
        ans += 1
    B[i] = 1
    if D[i]*2 <= 10**6:
        for j in range(D[i]*2,10**6+1,D[i]):
            B[j] = 1

print(ans-a)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
for i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    idx = bisect.bisect_left(A, pow(A[i],0.6))
    J = min(idx+1,i)
    #J = i
    ok = True
    for j in range(J):
        #print(i,j)
        if A[i] % A[j] == 0:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

Submission status: Wrong Answer

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

#A.sort(reverse=True)
A.sort()
cnt = 0
P = [1]*N

for i in range(N):
	for j in range(i+1,N):
		if P[j] != 0:
			 if A[j] % A[i] == 0:
			 	P[j] = 0

if A[0] in A[1:]:
	P[0] = 0

print(P.count(1))

Submission status: Wrong Answer

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

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

b = [True]*n
fix = [False]*n
for i in range(n):
    if not b[i] or fix[i]:
        continue
    if i < n-1 and a[i] == a[i+1]:
        b[i] = False
        fix[i] = True
    for j in range(i+1, n):
        if fix[j]:
            continue
        if a[i] < a[j] < a[i]*2:
            fix[j] = True
            continue
        if a[j] % a[i] == 0:
            fix[j] = True
            b[j] = False
for i in range(n-1):
    if a[i] == a[i+1]:
        b[i] = False
        b[i+1] = False
print(sum(b))

Submission status: Wrong Answer

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

def main():
    ans = 0
    if N == 1:
        print(1)
        return
    else:
        if A[0] != A[1]:
            ans += 1
    for i in range(1, N):
        flag = True
        if A[i] == A[i-1]:
            continue
        for j in range(i):
            if A[i]%A[j] == 0:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(each) for each in input().split()])
if len(set(a)) == 1:
    print(0)
else:
    counter = 1
    for i in range(1, n):
        for j in range(i):
            if i == j:
                continue
            if a[i]/a[j] == a[i]//a[j]:
                break
        else:
            # print(i, j)
            counter += 1

    print(counter)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
*a,=map(int, input().split())
sa=Counter(a)

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

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ans+=1
    if ai%2==0:
        for i in range(2,min(int(ai**(1/2)+7),ai)):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
    else:
        for i in range(3,min(int(ai**(1/2)+7),ai),2):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
print(ans)

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):
    if d[a[i]] == 0:
        d[a[i]] = 1
    else:
        d[a[i]] = -1
for i in range(1,1001):
    if d[i] == 1:
        ans += 1
        for j in range(2,1+10**6//i):
            d[j*i] = 0
    elif d[i] == -1:
        for j in range(2,1+10**6//i):
            d[j*i] = 0
for i in range(1001,1000000):
    if d[i] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter


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

c = Counter(a)
new = []
for key, val in c.most_common():
    if val == 1:
        new.append(key)

div = [make_divisors(i) for i in new]

ans = 0
for i in range(len(new)):
    val = set(div[i]) & set(new)
    if len(val) == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

n=ni()
a=sorted(nl())


ans=0

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

a_list = sorted(list(a_list), reverse=True)
if len(a_list) == 1:
    print(0)
    sys.exit()
elif 1 in a_list:
    print(1)
    sys.exit()

counter = 0
while True:
    ai = 0
    rai = len(a_list) - 1
    while True:
        if rai <= 0:
            a_list.pop(ai)
            counter += 1
            break
        if a_list[ai] % a_list[rai] == 0:
            a_list.pop(ai)
            break
        rai -= 1
    if len(a_list) == 0:
        print(counter)
        break

Submission status: Wrong Answer

Solution code:
n=int(input())
a = list(map(int,input().split()))
que = []
flg = []
p3flg = True
for ai in a:
    #print("------"+str(ai))
    if len(que) == 0:
        que.append(ai)
        flg.append(0)
    else:
        j = 0
        p3flg = True
        while True:
            #print(que)
            if len(que) == j:
                if p3flg:
                    que.append(ai)
                    flg.append(0)
                break
            #print(que[j])
            if ai == que[j]:
                flg[j] = 1
                #print("p1")
                break
            if ai % que[j] == 0:
                #print("p2")
                break
            if que[j] % ai == 0:
                if p3flg:
                    que[j] = ai
                    flg[j] = 0
                    #print("p3")
                else:
                    #print("p4")
                    que.pop(j) 
                    j -= 1
                p3flg = False

            j+= 1
            
print(len(que)-sum(flg))

Submission status: Wrong Answer

Solution code:
#D
n = int(input())
a = input().split()
a = [int(i) for i in a]
a.sort(reverse=True)


if n == 1:
    print(0)
else:
    if a[-1] == a[-2]:
        cnt = 0
    else:
        cnt = 1
    for i in range(n-1):
        if a[i] == a[i-1]:
            flg =True
        else:
            flg = False
            for j in range(i+1,n):
                if a[i] % a[j] == 0:
                    flg = True
                    break
        if flg == False:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

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

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

while i < num:
  for j in range(i):
    if A[i] % A[j] == 0:
      A.pop(i)
      num -= 1
      i -= 1
      break
  i += 1
print(num+ res)

Submission status: Wrong Answer

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

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

arr.sort()
if n >1 and arr[0] == arr[1] :
    ans = 0
else :
    ans =1
for i in range (1,n) :
    res = True
    for j in range(i):
        if (arr[i] %arr[j] == 0) or arr[i]//arr[j]  <1 :
            res = False
            break
    if  res == True :
        ans +=1

print(ans)

Submission status: Wrong Answer

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

dep = len([x for x in set(a) if a.count(x) > 1])
a = list(set(a))

a.sort()
n = len(a)

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

Submission status: Wrong Answer

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


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

print(count)

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 = math.sqrt(10**6)
while len(data) > 0:
  p = data[0]
  if len(data) > 1 and p == data[1]:
    count += 1
  if limit <= p:
    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:
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    if len(set(A)) == 1:
        print(0)
        return

    def div(x, y):
        return x % y

    A.sort()
    group = []
    for i, a in enumerate(A):
        if i == 0:
            group.append(a)
        else:
            arr = [a for i in range(len(group))]
            d = map(div, arr, group)
            if 0 not in list(d):
                group.append(a)

    print(len(group))

resolve()

Submission status: Wrong Answer

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

A.sort()
if A[0] == A[-1]:
  print(0)
else:
  for j in range(N):
    if j >= len(A):
      break
    B = list()
    B.append(A[j])
    for i in range(N):
      if i >= len(A):
        break
      if i == j :
        continue
      if A[i] % A[j] > 0:
        B.append(A[i])
    A = B.copy()
  print(len(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a = sorted(a, reverse=True)
count = 0
for i in range(len(a)):
    flag = 0
    for j in range(i+1,len(a)):
        if a[i] % a[len(a)-j+i] == 0:
            flag += 1
            break
    if i == len(a)-1:
        if a[i] % a[i-1] == 0:
            flag +=1
    if flag ==0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = [True] * len(A)


A.sort()

for i in range(len(A)):
        if A[i] > 450:
                break
        for j in range(len(A)):
                if i == j:
                        continue
                if ans[j]:
                        if A[j] % A[i] == 0:
                                ans[j] = False


count = 0
for i in ans:
        if i:
                count += 1
print(count)

Submission status: Wrong Answer

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

box={}

ans=0
for i in range(n):
    check=True
    for k in box:
        if A[i]%k==0:
            check=False
            break
    if i!=n-1:
        if A[i]==A[i+1]:
            check=False
    else:
        if A[i]==A[i-1]:
            check=False
    if check:
        box[A[i]]=1
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n == 1:
        print(0)
        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():
                print(l[i], d, "count")
                num += 1
                break
    if l[-2]==l[-1]:
        num += 1
    print(len(l)-num)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce


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


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))


def ZIP(n): return zip(*(MAP() for _ in range(n)))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()
    
    A.sort()
    i = 1
    dic = defaultdict(int)

    for x in A:
        dic[x] += 1

    div = [A[0]]
    for i in range(1, N):
        for j in div:

            if j > A[i]//2:
                div.append(A[i])
                break

            if A[i]%j == 0:
                break
        else:
            div.append(A[i])
    
    p = sum([1 for x in dic.values() if x>1])
    # print(p)
    # print(div)
    print(len(div)-p)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in 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]


divisors_list = {}
for i in range(1,1000001):
  divisors_list[i] = []

for k,i in enumerate(A):
  for j in make_divisors(i):
    divisors_list[j].append(k)

pass_li = {}
for i in range(N):
  pass_li[i] = 1

#for i in range(N):
 # tmp = pass_li[i]
  #for j in divisors_list[A[i]]:
   # pass_li[j] = 0
  #pass_li[i] = tmp 
  
  
print(sum(pass_li.values()))

Submission status: Wrong Answer

Solution code:
import itertools

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

total = 0

B = set()
for c in itertools.permutations(A, 2):
    if c[0] % c[1] == 0:
        B.add(c[0])

print(len(A) - len(B))

Submission status: Wrong Answer

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

count = 0

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

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

print(count)

Submission status: Wrong Answer

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

k = 0
b = 0
for l in range(n):
    if a[l] == 1:
        b = b + 1
        
if b == 0:
    for i in range(n):
        for j in range(n):
            if a[j] != 0:
                if i != j:            
                    if a[i] % a[j] == 0:
                        a[i] = 0
                        break
                if j == n-1:
                    k = k + 1          
    print(k)
elif b == 1:
    print('1')
else:
    print('0')

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int,input().split()))
li.sort()
if len(set(li)) == 1:
    print(0)
    exit()
for i in range(10^5):
    li.append(1122887)
count = 0
for i in range(n):
    if li[i] == 1122887:
        break
    j = i + 1
    while True:
        if li[j] == 1122887:
            break
        if li[j] % li[i] == 0:
            li.remove(li[j])
            count += 1
        else:
            j += 1
print(n - count)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N = i()
A = l()
A.sort(reverse=True)
ans = 0
num = 0
def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
for i in range(N):
    a = A[0]
    divs = dv(a)
    A.pop(0)
    if a in A:
        continue
    if divs:
        for d in divs:
            if d in A:
                num = 1
        if num :
            ans += 1
        num = 0
print(N-ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

def main():
    n = int(input())
    #x,n = map( int, input().split())
    a = list(map( int, input().split()))
    a.sort()
    print(a)
    ans = 1
    for i in range(1,len(a)):
        l = a[:i]
        print(l)
        if len(list(set(l)&set(make_divisors(a[i]))))==0:
            print(a[i])
            ans+=1
    print(ans)

        
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A.sort()


def div_by_min(a: list, start: int):
    del_list = []
    for i in range(start+1, len(a)):
        if A[i] % A[start] == 0:
            del_list.append(A[i])
    ans_list = []
    for num in a:
        if num not in del_list:
            ans_list.append(num)
    return ans_list


Start = 0
prev_len = 1000000
tmp = A

while True:
    if Start >= len(tmp)-1:
        break
    else:
        tmp = div_by_min(tmp, Start)
        if prev_len == len(tmp):
            Start += 1
        else:
            prev_len = len(tmp)
            Start = 0

print(len(tmp))

Submission status: Wrong Answer

Solution code:
import collections

def factorization(n):
    pf_cnt = {1:1}
    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
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt



def main():
    n = int(input())
    al = list(map(int, input().split()))

    al_not_multi = []
    cnt = collections.Counter(al)
    for i,v in cnt.items():
        if v == 1:
            al_not_multi.append(i)

    if not al_not_multi:
        print(0)
        return

    al_not_multi.sort()
    primes = []
    for a in al_not_multi:
        for prime in primes:
            if a%prime == 0: break
        else:
            primes.append(a)
    # print(primes)
    print(len(primes))


    # primes = {}
    # for a in al:
    #     fac = factorization(a)
    #     for prime,cnt in fac:
    #         primes.setdefault(prime,10000)
    #         primes[prime] = min(cnt, primes[prime])




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
l=list(map(int,input().split()))
l=[x for x in set(l) if not l.count(x) > 1]
l.sort(reverse=True)
count=0
if not l:
    print(0)
else:
    for i in range(len(l)):
        Frag=True
        for j in range(1,len(l)-i):
            if l[i]%l[i+j]==0:
                Frag=False
                break
        if Frag==True:
            count+=1
    print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def D():
    n = int(input())
    a = list(map(int, input().split()))
    b = [x for x in set(a) if a.count(x) < 2]
    b.sort()
    if len(b) == 0:
        print(0)
        return
    prime = [b[0]]
    for tar in b:
        flg = True
        for p in prime:
            if tar % p == 0:
                flg = False
                break
        if flg:
            prime.append(tar)
    print(len(prime))
D()

Submission status: Wrong Answer

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

    A.sort(reverse=True)

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

    if A[N-1] != A[N-2]:
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

ans = 0

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

# エラトステネスの篩っぽく処理
search_list = deepcopy(A)
ans = 0

tmp = min(search_list)
smax = int(max(search_list)**0.5) + 1

while search_list:
    ans += 1
    search_list = [i for i in search_list if i % tmp != 0]
    if len(search_list) == 0:
        break
    else:
        tmp = min(search_list)
        if tmp < smax:
            ans += len(search_list)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  n = int(input())
  li = list(map(int,input().split()))
  li.sort()
  ans_li= []
  for i in li:
    check = True
    for j in ans_li:
      if i % j == 0:
        check = False
      if i == j:
        ans_li.remove(i)
    if check:
      ans_li.append(i)
  print(len(ans_li))


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
n = int(input())
A = list(map(int, input().split()))

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

d = defaultdict(int)

for key in A:
    d[key] += 1

if len(d) == 1: # 全部同じ数
    print(0)
    sys.exit()

B = list(d)
B.sort()

if B[0] == 1: # 1が含まれる場合
    print(d[1])
    sys.exit()

len_B = len(B)
flag = [0 for i in range(len_B)]

for i in range(len_B-1):
    for j in range(i+1, len_B):
        if flag[j] == 0:
            if B[j] % B[i] == 0:
                flag[j] = -1
ans = 0
for i in range(len_B):
    if flag[i] == 0:
        ans += d[B[i]]

print(ans)

Submission status: Wrong Answer

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

TMP = []

for i in range(len(A)):
        flag = 0
        for j in range(len(TMP)):
                if (max(A[i], TMP[j]) % min(A[i], TMP[j])) == 0:
                        TMP[j] = A[i]
                        flag = 1
        if flag == 0:
                TMP.append(A[i])
                
if len(TMP) == 1:
        ans = 0
else:
        ans = len(set(TMP))

print (ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a_li = list(map(int,input().split()))
a_li.sort(reverse=1)
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
ans = 0
for i in range(n):
    flag = "ok"
    if a_li.count(a_li[i]) >= 2:
        continue
    dum = factorization(a_li[i])
    dum_len = len(dum)
    for j in dum:
        if a_li.count(j[0]) >= 1:
            if dum_len == 1 and j[1] == 1:
                break
            else:
                flag = "ng"
                break
    if flag == "ok":
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    
        
    A=list(set(pin()))
    B=sorted(A)
    #print(B)

    ans=1
    if len(B)==1:
        print(0)#what?
        return
    if B[0]<B[1]:ans+=1
    
    must_see=[]
    must_see.append(B[0])
    
    """
    for cnt in range(1,10**7):
        if cnt>=N:break
        temp=B[cnt]
        cond=1
        for i in must_see:
            shit+=1
            if temp%i==0:
                cond=0
                break
        if cond==1:
            ans+=1
            must_see.append(temp)
    print(ans)
    """
    ans=B[:]
    x=[]
    for i in B:

        for j in ans:
        
            if j!=i and j%i==0:
                #iremasen
                continue
            else:
                #iremasu
                x.append(j)
        ans=x[:]
        #print(i,ans)
        x=[]
    print(len(ans))
    


#%%submit!
resolve()