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:
N = int(input())
A = [int(x) for x in input().split()]

A.sort()

ans = 0

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

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

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

print(ans)

Submission status: Wrong Answer

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

flag = 0
for i in range(n-1):
  if a[i]==a[i+1]:
    flag += 1

if flag==n-1:
  print(0)
else:
  i = 0
  while i < len(a):
    b = []
    for j in range(i+1):
      b.append(a[j])
    for j in range(i+1,len(a)):
      if a[j]%a[i]!=0:
        b.append(a[j])
    a = b
    i += 1
  print(len(a))

Submission status: Wrong Answer

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

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
counter = Counter(A)
s = sorted(set(A))
if len(A) == 1:
    print(1)
else:
    lst = []
    ans = 0
    for i in range(len(s)):
        m = int(s[i]**0.5)+1
        flg = True
        for p in lst:
            if s[i]%p == 0:
                flg = False
                break
            elif m < p:
                break
        if flg:
            lst.append(s[i])
            if counter[s[i]] == 1:
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A)
counter = [A[0]]
for i in range(1,N):
    if not any([A[i] % x == 0 for x in counter]):
        counter.append(A[i])
print(len(counter))

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


N=int(input())
A=list(map(int, input().split()))
x=N
y=0
for i in range(N):
    if A.count(A[i])>1:
        x-=1
        continue
    s=factorization(A[i])
    for j in range(len(s)):
        for k in range(1,s[j][1]+1):
            if pow(s[j][0],k) in A and pow(s[j][0],k)!=A[i] :
                x-=1
                y=1
                break
        if y==1:
            y=0
            break
        
print(x)

Submission status: Wrong Answer

Solution code:
n = int(input())

l = [int(x) for x in input().split()]
l.sort()
mp = [1]*n
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        if(mp[j]==0):
            continue
        if(l[j]==l[i]):
            mp[j] = 0
            continue
        if(l[j]%l[i]==0):
            mp[j] = 0
            continue
print(sum(mp))

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
Alist = np.asarray( list(map(int, input().split())) )
y = np.zeros((N, ), dtype=np.int32)

for i in range(1, N):
  y += (Alist % np.roll( Alist, i ) ) == 0

print( y.sum() )

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(set(sorted(a)))
c = [1]*len(b)
if len(b)==1:
    print(0)
else:
    i = 1
    while i <=len(b):
        for j in range(i,len(b)):
            if b[j]%b[i-1] == 0:
                c[j]=0
            else:
                pass
        i += 1
    print(c.count(1))

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

count = 0

for i in li:
  new_li = li
  new_li.pop(new_li.index(i))
  val = make_divisors(i)
  if not new_li in val:
    count+=1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf)
for i in li:
    isprime[i] = True
for i in range(len(li)):
    if i+1<len(li):
      if li[i] == li[i+1]:
        isprime[li[i]] = False
for i in li:
    if not isprime[i]:
        continue
    for k in range(i+i, inf, i):
        isprime[k] = False
prime_list = []
for i in range(inf):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

Submission status: Wrong Answer

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
def qw(arr,n):
    s = dict()
    c = 0
    max_ele = -10**9
    for i in range(n):  
        s[arr[i]] = 1 
        max_ele = max(max_ele, arr[i])
    res = dict() 
    for i in range(n):  
        if (arr[i] != 0): 
            for j in range(arr[i] * 2,max_ele + 1, arr[i]):
                if (j in s.keys()): 
                    res[j] = 1
    for x in res: 
        c = c + 1
    return(c)
def solve():
    n = inp()
    a = inlt()
    q = counter(a)
    cc = 0
    for i in range(len(q)):
        if q[i] >= 2:
            cc = cc + 1
    print(len(list(set(a))) - qw(list(set(a)),len(list(set(a)))) - cc)
            
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * (max(a) + 1)
    for i in range(len(a)):
        q[a[i]] = q[a[i]] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return(q)

def power_two(n):
    if n == 1:
        return(True)
    sttr = str(n)
    len_str = len(sttr)
    sttr = list(sttr)
    num = 0
    if (len_str == 1 and sttr[len_str - 1] == '1'): 
        return(False)
    while (len_str != 1 or sttr[len_str - 1] != '1'):
        if ((ord(sttr[len_str - 1]) - ord('0')) % 2 == 1):
            return(False)
        j = 0; 
        for i in range(len_str):  
            num = num * 10 + (ord(sttr[i]) - ord('0')); 
            if (num < 2): 
                if (i != 0):  
                    sttr[j] = '0'
                    j += 1
                continue
  
            sttr[j] = chr((num // 2) + ord('0'))
            j += 1; 
            num = (num) - (num // 2) * 2
        len_str = j
    return(True)

def getLeftmostBit(n): 
    m = 0
    while (n > 1) : 
        n = n >> 1
        m += 1
    return(m)
def getNextLeftmostBit(n, m) : 
    temp = 1 << m 
    while (n < temp) : 
        temp = temp >> 1
        m -= 1
    return m
def bitcounter(n) :
    m = getLeftmostBit(n) 
    return _countSetBits(n, m) 
def _countSetBits(n, m) :
    if (n == 0) : 
        return 0
    m = getNextLeftmostBit(n, m)
    if (n == (1 << (m + 1)) - 1) : 
        return ((m + 1) * (1 << m))
    n = n - (1 << m)
    return (n + 1) + bitcounter(n) + m * (1 << (m - 1)) 

def log_two(n): 
    return(math.log(n) / math.log(2))

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
 

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = 0
for i in range(N):
    if A.count(A[i])> 1:
        continue
    for j in range(N):
        if 2 * A[j] > A[i]:
            break
        if A[i] % A[j] == 0:
            cnt += 1
            break
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    a = collections.Counter(a).items()
    b = []
    for x in a:
        if x[1] == 1:
            b.append(x[0])
    b.sort()
    ans = 0
    for i in range(len(b)):
        isDiv = False
        for j in range(i):
            if b[i] % b[j] == 0:
                isDiv = True
                break
        if not isDiv:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

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

a_sorted = sorted(a)
divisible_list = [True] * n
max_num = a_sorted[n-1]
for i in range(n-1):
    # 半分超えたら計算しない
    if max_num // 2 < a_sorted[i]:
        continue
    if not divisible_list[i]:
        continue
    for j in range(i+1, n):
        if a_sorted[j] == a_sorted[i]:
            divisible_list[i] = False
            divisible_list[j] = False
        if a_sorted[j] % a_sorted[i] == 0:
            divisible_list[j] = False
print(sum(divisible_list))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
M=max(a)
num=[0]*M
for x in a:
	num[x-1]+=1
for i in range(M):
	if num[i]!=1:
		num[i]=0
ret=num.copy()
for i in range(M):
	if num[i]:
		j=i+i+1
		while j<M:
			ret[j]=0 
			j+=i+1
print(ret.count(1))

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
N = int(input())
A = list(set([int(i) for i in input().split()]))
A.sort()

d = deque(A)

ans = 0

if len(d) == 1 and N != 1:
  print(0)
  exit()

while len(d) > 0:
  div = d.popleft()
  ans += 1
  first_flag = True
  first = 1000000000
  while len(d) > 0:
    num = d.popleft()
    if num == first:
      d.appendleft(num)
      break
    if num == div:
      dup_flag = True
    elif num % div != 0:
      d.append(num)
      if first_flag:
        first = num
        first_flag = False
    
print(ans)

Submission status: Wrong Answer

Solution code:
from numba import jit


@jit
def solve(N, A):
    ans = 0
    preA = 0
    for i in range(N):
        if A[i] == preA: continue
        for j in range(i+1, N):
            if A[i]%A[j] == 0: break
            if j == N-1: ans += 1
        preA = A[i]
    return ans+1


N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
if N == 1:
    ans = 1
elif len(set(A))==1:
    ans = 0
else:
    ans = solve(N,A)
print(ans)

Submission status: Wrong Answer

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

oks = np.ones(len(aa))
for i in range(len(aa)):
    if i < len(aa)-1:
        if aa[i+1] == aa[i]:
            oks[i] = 0
            continue
    if oks[i] == 0:
        continue
    for j in range(i+1,len(aa)):
        if (aa[j]%aa[i] == 0):
            oks[j] = 0
print(int(oks.sum()))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
As = set((map(int, input().split())))
N = len(As)

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

As = np.asarray(list(As))

Bs = [True]*N

for index, i in enumerate(As):
    Cs = As%i != 0
    Cs[index] = True
    Bs = np.logical_and(Cs, Bs)
print(list(Bs).count(True))

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))
tmp_A = copy.copy(new_A)
count=0

for i in new_A:
  tmp_A.remove(i)
  #print(list(set(make_divisors(i)) & set(tmp_A)))
  if(len(list(set(make_divisors(i)) & set(tmp_A)))==0):
    count+=1
  tmp_A = copy.copy(new_A)
if(len(new_A)==1):
  print(0)
else:
  print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
if np.unique(p).size >1:
    count +=1
for i in range(len(p)):
    for j in reversed(range(i+1,len(p))):
        if p[i]%p[j] ==0:
            break
        if j == i+1:
            count +=1
if count >=1:
    print(count)
else:
    print(count)

Submission status: Wrong Answer

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

l.sort(reverse=True)
cnt = 0
for i in range(len(l)-1):
    for j in reversed(range(i+1, len(l))):
        if l[i] % l[j] == 0:
            break
        if j == len(l)-1:
            cnt += 1
if l.count(l[-1]) == 1:
    print(cnt+1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
arr1 = [int(i) for i in input().split()]
arr = []
Dict = defaultdict(int)
for i in range(N):
    Dict[arr1[i]] += 1
for i in range(N):
    if Dict[arr1[i]] == 1:
        arr.append(arr1[i])
n = int(10 ** 6)
prime = [True for i in range(n + 10)]
for p in arr:
    if prime[p]:
        start = p+p
        for j in range(start, n + 1, p):
            prime[j] = False
count = 0
for i in arr:
    if prime[i]:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())

ans = set([int(x) for x in input().split()])

hoge = set()
cnt = 0

if N == 1:
    print(1)
elif N != 1 and len(ans) == 1:
    print(0)
else:
    for a,b in itertools.combinations(ans,2):
        if b % a == 0:
            hoge.add(b)
    print(len(ans-hoge))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*(2*10**6)
c=0
for i in a:
    b[i]+=1
for i in range(10**6):
    c+=1 if b[i]==1 else 0
    if b[i]==0:
        continue
    for j in range(1,10**6+4):
        if i*j>=10**6+1:
            break
        b[i*j]=0
print(c)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    pool = set()
    count = 0
    for i in range(n):
        t = a[i]
        if t in pool:
            continue
        if i+1 < n and t == a[i+1]:
            pool.add(t)
            continue
        limit = t // 2 +1
        is_ok = True
        for j in pool:
            if j > limit:
                break
            elif t % j == 0:
                is_ok = False
                #print("bad", t, j)
                break
        if is_ok:
            #print("good", t)
            pool.add(t)
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def primes(n):
    if(n==1):
        return []
    m=n**0.5
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=m:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes

def factor(N):
    arr=[]
    for i in li:
        if i**2>N:
            break
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

s=set()
li=primes(max(A))
ans=0
for i in range(N):
    if A[i] in ng:
        continue
    arr=factor(A[i])
    ok=True
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
    s.add(A[i])
print(ans)

Submission status: Wrong Answer

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

A_set = list(set(A))
if len(A_set) == 1:
    print(0)
else:
    A_count = Counter(A)
    for i in range(len(A_set)):
        for j in range(len(A_set)):
            if(j == i): continue
            if(A_set[i]%A_set[j] == 0):
                A_set[i] = A_set[j]
                d_num -= A_count[A_set[i]]
                break
    print(d_num)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = list(set(a))
n = len(a)
ans = 0
for i in range(n):
    flag = True
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            flag = False
            break
    if n != 1 and flag:
        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):
  if a[i] == a[i-1]:
    continue
  if i < n-1 and a[i] == a[i+1]:
    continue
  j = 0
  flag = True
  while j < len(b) and b[j] * 2 <= a[i]:
    if a[i] % b[j] == 0:
      flag = False
      break
    else:
      j += 1
  if flag:
    b.append(a[i])

print(len(b))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
for i in A:
    A.remove(i)
    for j in A:
        if i // j == 0:
            break
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
# D

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

# 降順に並べ替え
A.sort(reverse=True)

ans = 0

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

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

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
num = [0]*int(1e6+1)
for i in range(n):
    if num[a[i]] == 0:
        cnt += 1
        for j in range(a[i], int(1e6+1), a[i]):
            num[j] = 1
for i in range(1,n):
    if a[0] % a[i] == 0:
        cnt -= 1
        break
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
list0=list(map(int,input().split()))
list0 = set(list0)
if len(list0)==1:
  print(0)
else:
  list0 = list(list0)
  list0.sort()
  print(list0)
  t=0
  for i in range(len(list0)):
    for j in range(len(list0)-i-1):
      if list0[-i-1]%list0[-i-j-2]==0:
        break
    else:
      t+=1
  print(t)

Submission status: Wrong Answer

Solution code:
n = int(input())
p_list = [False for  i in range(10**3+1)]
a_list = list(map(int,input().split()))
a_list.sort()
check = [True for i in range(10**6+1)]
for i in range(1,n):
  if a_list[i] == a_list[i-1]:
    check[a_list[i]] = False
  
for i in range(n):
  if  a_list[i] <= 10**3:
    p_list[a_list[i]] = True
 
waru = []    
for p in range(len(p_list)):
  if p_list[p] == True:
    waru.append(p)
   
for w in waru:
  for a in a_list:
    if w != a and a % w == 0:
      a_list.remove(a)
      
count = 0
for a in a_list:
  if check[a] == True:
    count += 1
    
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

ans = 0

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


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

while search_list:
    prime_list.append(search_list[0])
    tmp = search_list[0]
    search_list = [i for i in search_list if i % tmp != 0]

print(len(prime_list))

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:
        du.add(a[i])
        continue
    for tmp in arr:
        if a[i] % tmp == 0:
            break
    else:
        arr.append(a[i])
    t = a[i]

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

Submission status: Wrong Answer

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

a.sort()

for i in range(n):
    flag=False
    for j in range(n):
        if(((a[i]%a[j]) == 0) and (a[i] != a[j])):
            flag=True
    if(flag):
        x += 1
print(x)

Submission status: Wrong Answer

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

a.sort()
ans=0
b=[]
m=1
for i in range(n-1):
    if a[i]!=a[i+1]:
        m+=1
st=[]
while a:
    if len(a)==1:
        if a[0] in st:
            break
        else:
            b.append(0)
            break
    else:
        p=a.pop(0)

        for i in a:
            if i%p==0:
                a.remove(i)
                st.append(p)
                if i!=p:
                    b.append(p)



print(len(b))

Submission status: Wrong Answer

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

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

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.5))
    J = min(idx+1,i)
    ok = True
    for j in range(J):
        if A[i] % A[j] == 0:
            ok = False
    if ok:
        ans += 1
print (ans)

Submission status: Wrong Answer

Solution code:
##### A #####
# x = [int(i) for i in input().split()]
# print(x.index(0)+1)

##### B #####
# x, y = (int(i) for i in input().split())
# sum_foots = 4*x
# while(sum_foots >= 2*x):
#     if sum_foots == y:
#         print('Yes')
#         exit()
#     sum_foots -= 2
# print('No')

##### C #####
# x, n = (int(i) for i in input().split())
# p = [int(i) for i in input().split()]
# 
# if n == 0:
    # print(x)
# else:
    # if x not in p:
        # print(x)
    # else:
        # left = x-1
        # right = x+1
        # while True:
            # if not left in p:
                # print(left)
                # exit()
            # if not right in p:
                # print(right)
                # exit()
            # left -= 1
            # right += 1


##### D #####
# n = int(input())
# A = [int(i) for i in input().split()]
# divs = []
# for a in A:
    # div = []
    # d = 2
    # while True:
        # if d == a:
            # div.append(d)
            # break
        # if a % d == 0:
            # div.append(d)
            # a /= d
            # d = 2
        # else:
            # d += 1 
    # divs.append(div)

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

for i in range(n):
    if i == n-1:
        if A[n-1] != A[n-2]:
            divisible = False
        else:
            divisible = True
    else:
        divisible = False
    for j in range(i+1, n):
        if A[i] % A[j] == 0:
            divisible = True
            break
    if not divisible:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
counter = Counter(A)
s = sorted(set(A))
if len(A) == 1:
    print(0)
else:
    lst = []
    ans = 0
    for i in range(len(s)):
        m = int(s[i]**0.5)+1
        flg = True
        for p in lst:
            if s[i]%p == 0:
                flg = False
                break
            elif m < p:
                break
        if flg:
            lst.append(s[i])
            if counter[s[i]] == 1:
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
num = list(int(x) for x in input().split())
num.sort()
max = num[N-1]
flag = 0
for i in range(N):
    if len(num) <= i:
        break
    no = num[i]
    # 同じ数が複数ある場合
    while 1:
        if len(num) > i+1:
            if num[i+1] == no:
                flag = 1
                num.pop(i+1)
            else:
                if flag == 1:
                    num.pop(i)
                break
        else:
            if flag == 1:
                num.pop(i)
            break
    for j in range(2, max//no + 1):
        # 同じ数が複数ある可能性に対処
        while 1:
            if no*j in num:
                num.remove(no*j)
            else:
                break
print(len(num))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
sa = set(a)
sl = len(sa)
ans = 0
for i in range(sl):
    count = 0
    for j in range(sl):
        if i == j:
            pass
        elif count == 0:
            if a[i] % a[j] == 0:
                count = 1
        else:
            break
    else:
        if count == 0:
            ans += 1
print(ans)

Submission status: Wrong Answer

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

    z = sorted(y)

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

    cnt = 1
    check = [z[0]]
    for x in z:
        f = all(x % i != 0 for i in check)
        if f:
            cnt += 1
            check.append(x)

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
Alist = np.asarray( list(map(int, input().split())) )
y = np.zeros((N, ))

for i in range(1, N):
  y += (Alist % np.roll( Alist, i ) ) == 0

print( y.sum() )

Submission status: Wrong Answer

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
f = [False]*n

if(n > 1):
    for i in range(1,n):
        if(a[i-1] == a[i]):
            f[i-1] = True
        for j in range(0,i):
            if(a[i] % a[j] == 0):
                f[i] = True
                break
            if(a[i] / a[j] < 2):
                break

count = 0
for i in range(n):
    if(not f[i]):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
A = list(map(int, input().split()))
if len(set(A)) == 1:
    print(0)
    exit()
heapq.heapify(A)
count = 0
divisor_list = []
while len(A) >= 1:
    count += 1
    item = heapq.heappop(A)
    amari = []
    for j in A:
        if j % item != 0:
            amari.append(j)
    heapq.heapify(amari)
    A = amari

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
if(len(list(set(a)))==1 and len(a)!=1):print(0);exit()
ans = []
num = 0
for i in a:
    b = True
    for j in ans:
        if(i%j == 0):
            b = False
            break
    if(b):
        ans.append(i)
        num+=1
print(num)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    n = I()
    mylist = list(MI())
    mylist.sort()
    mylist = tuple(mylist)
    if mylist[n-1] in mylist[:n-1]:
        result = 0
    else:
        result = 1

    for i in range(n-1):
        temp = mylist[i]
        divide = True
        for j in range(i+1,n):
            if mylist[j] % temp == 0:
                divide = False
                break
        if divide:
            result += 1
    print(result)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict

input()
A = np.fromstring(input(), int, sep=' ')

counter = defaultdict(int)
for x in A:
    counter[x] += 1

count = 0
for v in counter.values():
    if v > 1:
        count -= 1

A = np.array(list(set(A)))
maximum = A[-1]**0.5

f = np.ones_like(A, dtype=bool)
for i, x in enumerate(A):
    if not f[i]:
        continue
    count += 1

    if x <= maximum:
        f[i+1:] &= (A[i+1:] % x != 0)

print(count)

Submission status: Wrong Answer

Solution code:
a = int(input())
li = list(map(int,input().split()))
count = 0
for c,i in enumerate(li):
  print(i)
  for j in range(a):
    if i % li[j] == 0 and c != j:
      count = count + 1
      break

print(a-count)