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 numpy as np
n = int(input())
a3 = list(map(int, input().split()))
a2 = set(a3)
a = sorted(a2)
aa = np.array(a)
# print(aa[0])
check = [0] * n
# print(aa[0])

cc = 0
while True:
    tt = int(aa[0])
    #print('tt', tt)
    tar = aa[aa % tt != 0]
    if (len(tar) == 0):
        print(cc)
        break

    cc += 1

    if (len(tar) == 1):
        cc += 1
        print(cc)
        # print('zzz')
        break

    aa = tar
    #print('aa: ', aa)
'''
ans = n - sum(check)
print(ans)
'''

Submission status: Wrong Answer

Solution code:
from time import time


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


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

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

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

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

        if time() - now >= 1.9:
            print(n)
            exit()

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
    C = Counter(A)
    U = [0]*(max(A)+1)
    ans = 0
    for e in C:
        if C[e] > 1:
            U[e] = 1
        else:
            f = 1
            for k in range(2,math.floor(math.sqrt(e))+1):
                if e % k == 0:
                    if U[k] == 1 or U[e//k] == 1:
                        f = 0
                        break
            if f == 1:
                ans += 1
            U[e] = 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ok = [1]*n
a.sort()

for i in range(n):
    if ok[i]==1:
        for g in range(i+1,n):
            if a[g]%a[i]==0:
                ok[g]=0
if sum(ok)==1:
    print(0)
else:
    print(sum(ok))

Submission status: Wrong Answer

Solution code:
#E
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
count = 0
K = sorted(A,reverse = True)
for i in K:
    A.remove(i)
    for j in A:
        if i%j == 0:
            count = count-1
            break
        else:
            pass
    count = count+1
print(count)

Submission status: Wrong Answer

Solution code:
#<D>
n = int(input())
a = list(map(int,input().split()))
c=a
ans=0
b=0
for i in range(n):
    b=a[i]
    a=set(a)
    a=[b%x for x in a]
    if a.count(0) > 1:
        ans+=1
    a=c
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=1)
bl=[0]*(10**6+1)
B=[]
while A:
    x=A.pop()
    if A:
        if x!=A[-1]:
            B.append(x)
        else:
            bl[x]
            while A:
                y=A.pop()
                if y!=x:
                    A.append(y)
                    break
    else:
        B.append(x)


ans=0
for x in B:
    for j in range(1,int(x**0.5)+1):
        if j==1:
            if x==1:
                continue
            else:
                if bl[j]:
                    break
        elif x%j==0:
            if bl[x//j] or bl[j]:
                break
    else:
        ans+=1
    bl[x]=1
print(ans)

Submission status: Wrong Answer

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

if li.count(li[0]) == a:
    print(0)
    quit()

li.sort(reverse=True)
ans = []
kotae = 0
for i in range(a):
    for j in range(i + 1, a):
        if not li[i] % li[j] == 0:
            ans.append(i)
    if ans.count(i) == a - i - 1:
        kotae += 1
print(kotae)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
an = list(map(int, input().split()))

an.sort()
an = deque(an)
ls = deque()
same = -1
while an:
    a = an.popleft()
    t = True
    if same == a:
      continue
    for i in ls:
        if i > a/2:
            break
        if a == i:
            ls.pop()
            same = a
            t = False
            break
        if a % i == 0:
            t = False
            break
    if t:
        ls.append(a)

print(len(ls))

Submission status: Wrong Answer

Solution code:
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
#print(factorization(7),len(factorization(5)))

n = int(input())
a = list(input().split())
a = [int(i) for i in a]
if len(set(a)) == 1:
  print(0)
  exit()

ans=0
for i in range(len(a)):
  #print(i,a[i])
  x=a[i]
  if len(factorization(x)) == 1 and factorization(x)[0][1] == 1:
    ans+=1
    #print("so")
    continue
  l=[a[j] for j in range(len(a)) if int(x/2) >= a[j] or (j != i and a[j] == x)]
  s=0
  #print(l)
  for ii in l:
    #print("check:", ii)
    if x % ii == 0:
      break
    else:
      s+=1
  if s == len(l):
    ans+=1
  #print("ans",ans)

print(ans)

Submission status: Wrong Answer

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

    _max = 10 ** 6 + 1

    flag = [0] * _max
    A.sort()
    for a in A:
        flag[a] += 1
    
    ans = 0
    for a in A:
        if flag[a] == 1:
            ans += 1
        for i in range((_max - 1) // a):
            flag[a*i] += 1
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
# from numba import jit

# def main():
n = int(input().strip())
L = list(map(int, input().strip().split()))
seen = Counter()
# ans=0

for x in L:
    seen[x]+=1

# def loop():
ans=0
for x in L:
    if seen[x]>1 or x!=1 and 1 in seen:
        continue

    tmp=2
    while tmp**2<=x:
        if x%tmp and (tmp in seen or x/tmp in seen):
            break
        tmp+=1
    else:
        ans+=1
#     return ans
# print(loop())
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = []
for i in range(1000):
    t.append([])
for i in range(n):
    j = a[i]//1024
    t[j].append(a[i])
#print(t)
p = n
for i in range(len(t[0])):
    for j in range(len(t[0])):
        if(i != j):
            if(t[0][i] % t[0][j] == 0):
                p -= 1
                #print(t[0][i],t[0][j])
                break
for i in range(1,10):
    for j in range(len(t[i])):
        x = 0
        for k in range(len(t[i])):
            if(j != k):
                if(t[i][j] ==  t[i][k]):
                    p -= 1
                    #print(t[i][j],t[i][k],-1)
                    x = 1
                    break
        if(x == 0):
            for k in range((i+2)//2):
                for l in range(len(t[k])):
                    if(t[i][j] % t[k][l] == 0):
                        p -= 1
                        #print(t[i][j],t[k][l])
                        x = 1
                        break
                if(x == 1):
                    break

print(p)

Submission status: Wrong Answer

Solution code:
from time import time


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


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

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

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

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

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

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

count = 0
for i in range(len(A) - 1):
    is_not_dividable = True
    for j in range(i + 1, len(A)):
        if A[i] % A[j] == 0:
            is_not_dividable = False
            break

    if not is_not_dividable:
        count += 1
        
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=2*10**5
#a=[i+2 for i in range(0,n)]
a.sort()
aa={}
for i in range(0,a[-1]):
  aa[i]=0
for i in a:
  aa[i]=1
  
if a[0]==a[n-1]:
  print(0)
elif a[0]==1:
  print(1)
else:
  ans=0
  while len(a)!=1:
    now=a.pop(0)
    if aa[now]==1:
      ans+=1
      new=0+now
      while a[-1]>=now:
        if aa[now]==1:
          aa[now]=0
        now+=new
  if aa[a[0]]==1:
    ans+=1
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import time
import random


s = time.time()
def make_divisors_exist(n):
    #divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if exists[i]:
                if i != n:
                    return True
            #divisors.append(i)
            i2 = n // i
            if i != i2: # choufuku
                if exists[i2]:
                    if i2 != n:
                        return True
                #divisors.append(i2)

    # divisors.sort()
    #return divisors
    return False



input = raw_input
input()
As_0 = map(int, input().split(" "))

out = 0

counter = Counter(As_0)
As = counter.keys()

max_A = max(As)
exists = [False] * (max_A + 1)

timeover = False
for A in As:
    exists[A] = True

s = time.time()
random.shuffle(As)
for A1 in As:
    num = counter[A1]
    e = time.time()
    tdiff = e-s

    if tdiff >= 1.8:
        #print(tdiff)
        break

    if num >= 2:
        continue
    
    exist = make_divisors_exist(A1)

    if not exist:
        out += 1

print(out)

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]

import collections





n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
# print(c)
data = sorted(list(set(a)))
prime = []
limit = math.sqrt(10**6)
while len(data) > 0:
  p = data[0]
  if limit < p:
    prime += data
    break
  prime.append(p)
  data = [e for e in data if e % p != 0]
  #print(data)
count = 0
for r in prime:
  if c[r] > 1:
    count += 1
print(len(prime)-count)

Submission status: Wrong Answer

Solution code:
#import numpy as np
import sys
#from collections import deque
#import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp




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

a = xnxn()

a.sort()


dp = [0] * n


if a[0] != a[1]:
    dp[0] = 1
else:
    dp[0] = 0

so = [a[0]]


for i in range(1, n):
    c = 1
    dp[i] += dp[i-1]
    for k in so:
        if a[i] % k == 0:
            c = 0
            break
    if c == 1:
        dp[i] += 1
        so.append(a[i])

print(dp[n-1])

Submission status: Wrong Answer

Solution code:
# 幅優先探索（行きがけ）
import collections
import sys
import math
import copy
import collections


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N = I()
    AArry = LI()
    c = 0
    count_dict = collections.Counter(AArry)
    for _, v in count_dict.items():
        if v > 1:
            c += 1

    a = len(AArry)
    AArry = list(set(AArry))
    AArry.sort()
    b = len(AArry)
    count = a-b+c

    while AArry:

        a = AArry.pop(0)
        l1 = len(AArry)
        if len(AArry) == 0:
            break
        AArry = [e for e in AArry if e % a != 0]

        l2 = len(AArry)
        count += (l1-l2)

    print(N-count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
M=max(a)
p=[]
for i in range(n):
    if i+1<=n-1:
        if a[i]==a[i+1]:
            p+=[j for j in range(a[i],M+1,a[i])]
    else:
        p+=[j for j in range(a[i]*2,M+1,a[i])]

print(len(set(set(a)-set(p))))

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = sorted(inpl())
cnt = collections.Counter(a)
ans = 0
dp = [0] * (10**6 + 1)
for i in a:
    if dp[i] == 0:
        for j in range(1, 10**7):
            if i * j > 10**6:
                break
            dp[i * j] = 1
        if cnt == 1:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
# from numba import jit

def main():
    n = int(input().strip())
    L = list(map(int, input().strip().split()))
    seen = Counter()
    # ans=0
    
    for x in L:
        seen[x]+=1
    
    # def loop():
    ans=0
    for x in L:
        if seen[x]>1 or x!=1 and 1 in seen:
            continue
    
        tmp=2
        while tmp**2<=x:
            if x%tmp and (tmp in seen or x/tmp in seen):
                break
            tmp+=1
        else:
            ans+=1
    #     return ans
    # print(loop())
    print(ans)
    
if '__main__' == __name__:
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import sqrt
from bisect import bisect_left
n = int(input())
a = Counter(map(int, input().split()))
nums = sorted(list(a.keys()))
ans = n
for num, count in a.items():
    if count > 1:
        ans -= count
        continue
    index = bisect_left(nums, sqrt(num))
    search_range = nums[:index + 1]
    for i in search_range:
        if num % i == 0 and num != i:
            ans -= count
            break
print(ans)

Submission status: Wrong Answer

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

counter = [0 for _ in range(n)]
for i, num in enumerate(a):
    div = num % np.array(a)
    for j, result in enumerate(div):
        if i == j: continue
        elif result == 0:
            counter[j] += 1
    #print(div)
    #print(counter)
print(counter.count(0))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted([i for i in a if a.count(i) == 1])
    a = np.array(a)
    ans = []
    if len(a) == 0:
        print(0)
    else:
        while a != []:
            ans.append(a[0])
            a = a[a%a[0] != 0]
        print(len(ans)+1)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
A=sorted(map(int,input().split()))
L=[A[0]]
if n==1:
    print(0)
else:
    c=0
    if A[0]!=A[1]:
        c=1
    for i in range(n-1):
        flag=0
        for l in L:
            if A[i+1]%l==0:
                flag=1
                break
            if l>=int(A[i+1]**0.5+1):
                break
        if flag==0:
            L.append(A[i+1])
            c+=1
    print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(map(int, input().split()))
S.sort()
ans = 0
if N > 1:
    if S[0] < S[1]:
        ans += 1
else:
    ans = 1
for i in range(N-1, 0, -1):
    num = S[i]
    M = num//2
    flg = True
    if num%2 != 0 and num > 2:
        for j in range(3, int(num**0.5)+1, 2):
            if num%j == 0:
                break
        else:
            if num == S[i-1]:
                continue
            elif i < N-1:
                if num == S[i+1]:
                    continue
            ans += 1
            continue
        num = S[i]
        M = num//2
        for j in range(i):
            if num%S[j] == 0:
                flg = False
                break
            elif S[j] > M:
                break
        if num == S[i-1]:
            continue
        elif i < N-1:
            if num == S[i+1]:
                continue
        if flg:
            ans += 1
    else:
        for j in range(i):
            if num%S[j] == 0:
                flg = False
                break
            elif S[j] > M:
                break
        if num == S[i-1]:
            continue
        elif i < N-1:
            if num == S[i+1]:
                continue
        if flg:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
B=[]
for i in range(N-1):
    if A[i]==A[i+1]:
        B.append(A[i])
L=len(A)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
rsl = 0
for i in range(N):
    dd = A[i]
    B = A%dd
    num = np.count_nonzero(B)
    if num==N-1:
        rsl=rsl+1

print(rsl)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

def main():
    N = int(input())
    l = [int(x) for x in input().split()]
    dict={}
    l = sorted(l)
    L=[l[0]]
    for i in range(1,N):
        idx = bisect(L,l[i]//2)
        for j in L[:idx+1]:
            if l[i]%j==0:
                if l[i]==j:
                    dict[j]=0
                break
        else:
           # print("i",i)
            L.append(l[i])

    print(len(L)-len(dict))
    
main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

T = A
for i in range(N - 1):
    T = np.append(T, A)
T = T.reshape((N, N))
U = A.reshape((N, 1))

Ans = T % U
print(Ans[0])
count = 0

for i in range(N):
    if np.count_nonzero(Ans[i] == 0) == 1:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
s=set()
ans = 1
if n==1:
    print(ans)
    exit()
if n>=2 and a[0]==a[1]:
    ans=0
s.add(a[0])
for i in range(1,n):
    c=0
    for j in s:
        if a[i]%j==0:
            c=1
            break
    if c==0:
        ans+=1
        s.add(a[i])
print(ans)

Submission status: Wrong Answer

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

A = sorted(set(A))
t = [True] * (10 ** 6 + 1)

for a in A:
    for i in range(a, 10 ** 6 + 1, a):
        t[i] = False

result = 0
for a in A:
    if t[a]:
        result += 1
print(result)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = Counter([i for i in range(1,10**6+1)])
ans = 0
pre= 10**6+1
for i in sorted(A.keys(),reverse=True):
    flg = True
    if A[i] > 1:
        continue
    for j in range(1,min(int(pow(i,0.5))+2,pre)):
        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
    pre = i
print(ans)

Submission status: Wrong Answer

Solution code:
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.extend([i for _ in range(cnt)])

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

    if arr==[]:
        arr.extend([n])

    return arr

class Node:
  def __init__(self, data, num, flag):
    self.data = data
    self.next = []
    self.num = num
    self.flag = flag
  def add_next(self, data, flag):
    self.next.append(Node(data, self.num+1, flag))
    
  def search(self, data):
    for i in range(len(self.next)):
      if(self.next[i].data == data):
        return i
    return -1
      
def set_tree(tree, ss, ind):
  kk = tree.search(ss[ind])
  if(kk != -1):
    if(tree.next[kk].flag):
      return False
    if(ind == len(ss)-1):
      return False
    else:
      return set_tree(tree.next[kk], ss, ind+1)
      
  else:
    if(ind == len(ss)-1):
      tree.add_next(ss[ind], True)
      return True
    else:
      tree.add_next(ss[ind], False)
      return set_tree(tree.next[-1], ss, ind+1)
    
    
      
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [a[0]]
f = True
mm = 0
for i in a[1:]:
  if (b[-1] == i):
    if(f):
      mm += 1
      f = False
    continue
  else:
    b.append(i)
    f = True


if(1 in a):
  print(0)
  exit()

s = []
for i in range(n):
  s.append(factorization(a[i]))


tree = Node(1, 0, False)
count = 0

for i in range(n):
  if(set_tree(tree, s[i], 0)):
    count += 1
print(count-mm)

Submission status: Wrong Answer

Solution code:
import copy 
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())))
new_A=list(set(A))
new_A.sort()
kotei_A=copy.copy(new_A)
tmp_A = copy.copy(new_A)
count=0

for i in kotei_A[:]:
  tmp_A.remove(i)

  yaku=list(set(make_divisors(i)) & set(tmp_A))
  if(len(yaku)==0):
    count+=1
  else:
    new_A.remove(i)
    kotei_A.remove(i)
  tmp_A = copy.copy(new_A)

if(len(new_A)==1):
  print(0)
else:
  print(count)

Submission status: Wrong Answer

Solution code:
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
#print(factorization(7),len(factorization(5)))

n = int(input())
a = list(input().split())
a = [int(i) for i in a]
if len(set(a)) == 1:
  print(0)
  exit()

ans=0
for i in range(len(a)):
  print(i,a[i])
  x=a[i]
  if len(factorization(x)) == 1 and factorization(x)[0][1] == 1:
    ans+=1
    #print("so")
    continue
  l=[a[j] for j in range(len(a)) if int(x/2) >= a[j] or (j != i and a[j] == x)]
  s=0
  print(l)
  for ii in l:
    #print("check:", ii)
    if x % ii == 0:
      break
    else:
      s+=1
  if s == len(l):
    ans+=1
  #print("ans",ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=sorted(map(int,input().split()))
L=[A[0]]
print(L)
if n==1:
    print(0)
else:
    c=0
    if A[0]!=A[1]:
        c=1
    for i in range(n-1):
        flag=0
        for l in L:
            if A[i+1]%l==0:
                flag=1
                break
            if l>=int(A[i+1]**0.5+1):
                break
        if flag==0:
            L.append(A[i+1])
            c+=1
    print(c)

Submission status: Wrong Answer

Solution code:
#D
import collections
n=int(input())
a_list=list(map(int,input().split()))
a_list.sort()
b_list=collections.Counter(a_list)
b_list=b_list.keys()
j_list=[a_list[0]]
if len(b_list)==1:
    ans=0
elif 1 in a_list:
    ans=1
else:
    ans=1
    if a_list[0]==a_list[1]:
        ans-=1
    for i in a_list:
        for j in j_list:
            
            if i in j_list:
                ans-=1
                break
            if i%j ==0:
                break
        else:
            ans+=1
            j_list.append(i)
            #print(i)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
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
  
N= int(input())
A = input().split()
ANS = 0
flag = 0
for i in range(N):
  if is_prime(i) == True:
    C = A[i]
    if A.count(C) == 1:
      ANS += 1
print(ANS)

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 = sorted(list(map(int,input().split())),reverse=True)
cnt = 0

for i in range(n):
    flg = False
    div = make_divisors(a[i])
    if set(div).isdisjoint(set(a[i+1:])):
        flg=True
    if flg:
        if a[i] == a[i-1]:
            flg = False
    cnt += 1 if flg else 0
print(cnt)

Submission status: Wrong Answer

Solution code:

n = int(input())
a_ori = [int(x) for x in input().split()]
a_set = set(a_ori)
a = list(a_set)
a.sort()
count = 0

if len(a)==1:
    print(0)
else:
    while len(a) > 1:
            count += 1
            m = a[0]
            ma = a[-1]
            multi = [m*i for i in range(ma//m + 1)]

            p_set = set(a)
            multi_set = set(multi)
            next_set = p_set - multi_set

            a = list(next_set)
            a.sort()
            
            if len(a) == 1:
                count += 1
                print(count)
                break

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()
maxa = max(a)+1
d = defaultdict(int)
for i in a:
	d[i]+=1
tmp = []
for i in d:
	if d[i]==1:
		tmp.append(i)
a = tmp[:]


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