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
import math
import collections
import bisect
#import sympy


def divisor(n):
    i = 1
    lower_divisors, upper_divisors = [], []
    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()))

A.sort()

ans = 0
ans = N
Set = set()
for i in range(N):
    divs = divisor(A[i])
    print(divs)
    if i != 0:
        Set.add(A[i - 1])
    if i < N - 1:
        if A[i] == A[i + 1]:
            ans -= 1
            continue

    for d in divs:
        if i != 0:
            if d in Set:
                ans -= 1
                break
print(ans)

Submission status: Wrong Answer

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

B = [1 for _ in range(n)]

for i in range(n):
  if B[i] == 0:
    continue
  if A[i]*2 > A[n-1]:
    if A[i] == A[n-1]:
      for j in range(n)[i:]:
        B[j] = 0
    else:
      break
      
  c = 0
  if i < n-1 and A[i] == A[i+1]:
    B[i] = 0
    B[i+1] = 0
    for j in range(n)[i+2:]:
      if A[j] == A[i]:
        B[j] = 0
      else:
        break
  while(A[i]*c <= A[n-1]):
    c += 1
    for j in range(n)[i+1:]:
      if A[j] == A[i]*c:
        B[j] = 0
print(sum(B))

Submission status: Wrong Answer

Solution code:
def make_divisors(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)

    divisors.sort()
    return divisors
n = int(input())
numlist = sorted(list(map(int,input().split())))

counter = 0
print(numlist)
for i in range(n):
    temp = set(numlist[i+1:])
    divs = set(make_divisors(numlist[i]))
    if len(temp-divs) == len(temp):
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(n) for n in input().split()]
AS = sorted(set(A))
ans = 0
if len(AS) == 1:
    print(ans)
    exit()
ans += 1
for i in range(1, len(AS)):
    c = 0
    for j in range(i):
        if AS[i] % AS[j]==0:
            break
        else:
            c += 1
            if c == i:
                ans += 1
print(ans)

Submission status: Wrong Answer

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

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

import collections
c=collections.Counter(A)

cnt=0
for i in range(len(A)):
    #print(A[i],is_prime(A[i]),c[A[i]])
    if c[A[i]] == 1:
        if is_prime(A[i]):#素数かつ一つしかない場合は確定
            cnt+=1
        else:
            flg=True
            for j in range(i):
                if A[i]%A[j]==0:
                    flg=False
                    break
            if flg:
                cnt+=1
print(cnt)

Submission status: Wrong Answer

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

cnt = 0
divided = False

for i in ints:
    for j in ints:
        if i % j == 0 and i != j:
            divided = True
            break
    if not divided:
        cnt += 1
    divided = False

print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
p=[]
print(b)
while True:
    if len(a)==0:
        break
    prime=min(a)
    p.append(prime)
    i = 0
    while i < len(a):
        if a[i] % prime == 0:
            a.pop(i)
            continue
        i += 1

for x in a:
    p.append(x)
g=0
for i in range(len(p)):
    if b.count(p[i])>1:
        g+=1
print(len(p)-g)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
INF = 10**9
import fractions

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

    A.sort()
    ans = len(A)
    if n == 1:
        print(1)
        return
    for i in range(n):
        for j in range(n):
            ri = -i-1
            r = A[ri]
            l = A[j]

            if (ri!=-n and r == A[ri-1]) or (j!=n-1 and r == A[ri+1]):
                ans -= 1
                break
            if n+ri == j:
                break
            if r % l == 0:
                ans -= 1
                break
            if l >= r**(1/2):
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def is_prime(n):
    '''引数nが素数であればTrue、そうでなければFalseを返す'''
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

A_list = [int(n) for n in input().split()]

import numpy as np

A_array = np.array(A_list)
sort_A = np.sort(A_array)

XX = list()

for n in range(len(sort_A) - 1):
    
    r_list = list()
    
    for m in range(n+1):
        r_list.append(sort_A[n + 1] % sort_A[m] == 0)
       
    XX.append(np.array(r_list).sum() == 0)
    
XX_array = np.array(XX)        
        
print(XX_array.sum()+1)

Submission status: Wrong Answer

Solution code:

n=int(input())
a=list(map(int,input().split()))
a.sort()
ok=[0]*(a[-1]+1)
for i in range(n):
  ok[a[i]]+=1
for i in range(n):
  if ok[a[i]]>1:
    ok[a[i]]=0
  elif ok[a[i]]:
    for j in range(2,a[-1]//a[i]+1):
      ok[a[i]*j]=0
    
print(sum(ok))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    sieve_len = A[-1] + 1
    sieve = [0] * sieve_len

    count = 0
    for ix, a in enumerate(A):
        if sieve[a] == 0 and (ix == len(A) - 1 or a != A[ix+1]):
            count += 1
        else:
            continue
        intermediate_a = a
        while intermediate_a < sieve_len:
            sieve[intermediate_a] += 1
            intermediate_a += a
    print(count)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


j=0
while(True):
    del_list=[]
    for i in range(j+1, len(A)):
        if A[i]%A[j]==0:
            del_list.append(i)
    for k in sorted(del_list, reverse=True):
        A.pop(k)
    j+=1
    if len(A)==j+1:
        break

print(len(A))

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=sorted(list(map(int, input().split())))
if N==1:
    ans=1
elif A[0]==A[1]:
    ans=0
else:
    ans=1    

for i in range(1,N-1):
    for j in range(i):
        if A[i]==A[i-1] or A[i+1]:
            break
        if A[i]%A[j]==0:
            break
        if A[j]>math.sqrt(A[i]):
            ans+=1
            break
        
for j in range(1,N):
    if A[N-1]%A[0]==0:
        break
    if A[N-1]==A[N-2]:
        break
    if A[N-1]%A[j]==0:
        break
    if A[j]>math.sqrt(A[N-1]):
        ans+=1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
x=N
if A[0]==1:
    print(0)
    exit(0)

for i in range(N):
    if A.count(A[i])>1:
        x-=1
        continue
    for j in range(max(i,0)):
        if A[i]%A[j]==0:
            x-=1
            break
        if A[i]//A[j]+1<=A[j]:
            break
print(x)

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
    elif a==min(As):
        i+=1
        continue
    for b in As:
        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
import bisect

n = int(input())
a = [int(i) for i in input().split()]

a.sort()

count = 0

if(n == 1):
    print(1)
else:
    for i in reversed(range(n)):
        flag = 0
        temp = int(math.sqrt(a[i]))
        for j in range(2, temp+1):
            if(a[i] % j == 0):
                temp2 = a[i] / j
                x1 = bisect.bisect_left(a, j)
                if(j == a[x1]):
                    flag = 1
                if(temp2 <= a[n-1]):
                    x2 = bisect.bisect_left(a, temp2)
                    if (temp2 == a[x2]):
                        flag = 1
        if(i < n-1):
            if(a[i] == a[i+1]):
                flag = 1
        else:
            if (a[i] == a[i-1]):
                flag = 1
        if(flag == 0):
            count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
import collections

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

c = collections.Counter(A_list)
sorted_list = sorted(A_list)

count = 0

for i_index in range(N):
    i = sorted_list[i_index]
    for j in sorted_list[:i_index]:
        jmemo = j
        print(i, j)
        if i % j == 0:
            break
    else:
        if c[str(i)] == 0:
            count+= 1
print(count)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
B=A[::-1]
if Counter(A)[A[-1]]>1:
    ans=0
else:
    ans=1
for i in range(N-1):
    for j in range(i,N):
        if B[i]%A[j]==0:
            break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
A_org = A
A = set(A)
A = list(A)
A = sorted(A)
N = len(A)

ans_arr = []
ans_arr.append(A[0])

for i in range(1, N):
  for j in range(0, i):
    flag = 0
    if A[i] % A[j] == 0:
      flag = 1
      break
  if flag == 0:
    ans_arr.append(A[i])
    
ans = 0
for i in ans_arr:
  ans += A_org.count(i)
  
  
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
divisible = int()
dup = len([x for x in set(A) if A.count(x) > 1])
# print(dup)
B = A[:]
for i, a in enumerate(A):
  r_range = i - divisible
  for ri, r in enumerate(B[:r_range]):
#    print(a,r)
    if a % r == 0:
      divisible += 1
      B.pop(r_range)
      break
print(N - divisible - dup)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
AA = [ False for i in range(N) ]

A.sort()

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

Submission status: Wrong Answer

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

k = list(set(A))
if (len(k) == 1):
    print(0)
    exit()
j = 0
ans = deque()
c = Counter(A)
while j <= N - 1:
    if (j < N - 1):
        if (A[0] == A[j] and A[j] == A[j + 1]):
            j += 1
            continue

    if (j == 0 and A[j] != A[j + 1]):
        ans.append(j)
        j += 1
        continue
    check = False
    for i in range(0, j):
        # iとjが同じとき
        if (i == j):
            continue
        if (c[A[j]] != 1):
            check = True
            break

        if (A[j] % A[i] == 0):
            check = True
            break

    if (not check):
        ans.append(j)
    j += 1

print(len(ans))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
count = 0
i = 0
while i <= n-1:
    flag = True
    root = math.sqrt(a[i])
    for j in range(i):
        if a[j] > root:
            break
        elif  (a[i]%a[j]) == 0:
            flag = False
            break
    if flag and i <= n-2 and a[i] == a[i+1]:
        flag = False
        k = 2
        while i+k <= n-1 and a[i] == a[i+k]:
            k += 1
        i += k
    if flag:
        count += 1
    i += 1
print(count)

Submission status: Wrong Answer

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

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

res = N - flag
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


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

    # divisors.sort()
    return divisors


N = int(input())
A = list(map(int, input().split()))
setA = set(A)
countA = Counter(A)
if countA[1] == 1:
    print(1)
    exit()

minA = min(A)

count = 0
for num in A:
    if countA[num] >= 2:
        continue
    if minA == num:
        count += 1
        continue
    divisors = make_divisors(minA, num)
    if any((e in setA) for e in divisors):
        continue
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/local/bin/python3
# coding: utf-8
n = input()
ha = input()
kita = ha.split(" ")
newkita = sorted(kita)
count = 0
for i in range(int(n)):
    ifC = True
    for j in range(int(n)):
        if(i > j):
            a = int(newkita[i])
            b = int(newkita[j])
            if(a%b == 0):
                ifC = False
                break
        else:
            break
    if(ifC):
        count += 1
print(count)

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 N == 1:
    print(1)
    exit()

if A[0] == 1:
    if N >= 2 and A[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()


a = 0
ans = 0
B = [0]*(10**6+1)
for i in range(len(A)):
    if B[A[i]] == 0:
        ans += 1
    if i >= 1 and A[i] == A[i-1]:
        a += 1

    for j in range(A[i],10**6+1,A[i]):
        B[j] = 1

print(ans-a)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split(" ")))
c = 0
A = sorted(A)
judge = True
for i in range(N):
  for j in range(i):
    if A[i]%A[j] == 0:
      judge = False
      break
  if judge:
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def prime_fact(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return Counter(a) #カウンターを返す（要素と出現回数）


def main():
    n = int(input())
    nums = list(map(int,input().split()))
    #prime_factors = list(map(prime_fact,nums))
    #prime_factors_to_s = list(map(str,prime_factors))
    #prime_factors_string = list(map(lambda x:",".join(x),prime_factors_to_s))
    #ind = dict()
##    for i in range(n):
##        if not i in ind:
##            ind[nums[i]] = [i] #インデックスを保存
##        else:
##            ind[nums[i]].append(i) #重複も一応……)
    nums.sort()
    fact_counters = [prime_fact(n) for n in nums]
    undivisable = [True] * n
    #print(nums)
    print(nums)
    for i in range(n-1):

        if not undivisable[i]:
            continue #すでに何かで割られた数はスルー(それより小さい数で割れる)
        divisor = fact_counters[i]
        for j in range(i+1,n):
            for key in divisor.keys():
                flag = True
                if fact_counters[j][key] <= divisor[key]:
                    continue
                else:
                    undivisable[j] = False
                    #print(j,nums[j],"is divisorble! by",nums[i],key)
                    break
            if nums[j] == nums[i]:
                undivisable[i] = False
        #print(nums[i],undivisable)

    print(undivisable.count(True))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A_list = [int(i) for i in input().split()]
    A_list = list(set(A_list))
    if len(A_list) == 1:
        print(0)
        return
    A_list_sorted = sorted(A_list)
    prime_numbers_in_A_list = []
    for i in range(N):
        prime_numbers_in_A_list.append(A_list_sorted[0])
        A_list_sorted = [A for A in A_list_sorted if A % A_list_sorted[0] != 0]
        if len(A_list_sorted) == 0:
            break
    print(len(prime_numbers_in_A_list))

resolve()

Submission status: Wrong Answer

Solution code:
import math

def isPrime(n):
  if n == 1:
    return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False
  return True

def isDiv(x, y):
  if x % y == 0:
    return True
  else:
    return False

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

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

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

for i in range(N):
  x = A[i]
  if isPrime(x):
    if i - 1 >= 0:
      x == A[i - 1]
      cnt -= 1
      continue
    if i + 1 < N:
      x = A[i + 1]
      cnt -= 1
      continue
    continue
    
  for j in range(i):
    y = A[j]
    if isDiv(x, y):
      cnt -= 1
      break
print(cnt)

Submission status: Wrong Answer

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

for i in range(n):
    temp_count = 0
    same_count = 0
    for j in range(n):
        if i == j:
            continue
        if alist[i] == alist[j]:
            same_count += 1
            continue

        if alist[i] % alist[j] != 0:
            temp_count += 1
        if temp_count == len(alist) - same_count-1:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int,input().split()))
A_list.sort()
cnt1 = 1

for i in range(1,len(A_list)):
  for j in range(0,i):
    cnt2 = 0
    if A_list[i] % A_list[j] == 0:
      break
    if A_list[i] % A_list[j] != 0:
      cnt2 += 1
  
  if cnt2 > 0:
    cnt1 += 1

print(cnt1)

Submission status: Wrong Answer

Solution code:
def make_divisors(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 sorted(divisors, reverse=True)


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

if N == 1:
    print(1)
    exit()
    
A = sorted(A)
check_list = [0] * (10**6 + 1)

for a in A:
    check_list[a] = 1

cnt = 0
prev_val = -1
next_val = A[1]
for i in range(len(A)):
    if len(A) - 1 == i:
        if prev_val == A[i]:
            continue        
        prev_val = A[i]
    else:
        next_val = A[i + 1]
        if next_val == A[i]:
            continue
        if prev_val == A[i]:
            continue        
        prev_val = A[i]
    divisors = make_divisors(A[i])[1:-1]
    check_ok = True
    for d in divisors:
       if check_list[d] == 1:
           check_ok = False
    if check_ok == True:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import math


def int1(x): return int(x) - 1
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def mi1(): return map(int1, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def lli(rows_number): return [li() for _ in range(rows_number)]


if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(list(set(a)))
    b = [True] * (a[-1] + 1)
    def sived(x):
        for not_ans in range(x+x, a[-1]+1, x):
            b[not_ans] = False
    for i in range(a[0]):
        b[i] = False
    for i in a:
        if b[i-1]:
            sived(i)
    ans = 0
    for i in a:
        if b[i-1]:
            ans += 1
    print(ans-1)

Submission status: Wrong Answer

Solution code:
import numpy as np

d = list(map(int,input().split()))
a = np.array(list(map(int,input().split())))


ansindex = []
found = []
cnt = 0
for var in range(0, len(a)):
    new_list = np.delete(a, var)
    #Sprint(a[var])
    #print(new_list%a[var])
    resp = new_list%a[var]
    basis = np.insert(resp,var,a[var])
    #print(basis)
    found += np.where(basis == 0)
    #modが0になったところをさがす
    for fd in range(0, len(found)):
        #ある一つの数字で割った結果について
        f = found[fd]
        #print(f)
        for ff in f:
            ansindex.append(ff)

    """

    for fd in range(0, len(found)):
        #ある一つの数字で割った結果について
        f = found[fd]
        #print(f)
        for ff in f:
            #print(f)
            if ff not in ansindex:
                ansindex.append(ff)
            else:
                continue
    """


#print(ansindex)
set(ansindex)
print(int(d[0]) - len(ansindex))

Submission status: Wrong Answer

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

from math import sqrt
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
s = Counter(a)
a = sorted(s)
if s[1]>=2:
    ans = 0
elif s[1]==1:
    ans = 1
else:
    ans = 0
    for i in range(len(a)):
        if s[a[i]]>1:
            continue
        j = 2
        sq = sqrt(a[i])
        while j<=sq+1:    
            if a[i]%j==0 and (j in s or a[i]//j in s):
                break
            j+=1
        else:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=list(set(a))
ans=[]
if len(a)==1:
    print(0)
    quit()
for i in range(len(a)):
    for j in range(i+1,len(a)):
        if a[i]%a[j]==0 and i!=j:
            ans.append(a[i])
        elif a[j]%a[i]==0 and i!=j:
            ans.append(a[j])
            #割り切れたやつを追加
print(len(a)-len(set(ans)))

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    if n==1:
        print(0)
        return

    #arr.sort()
    ans=0
    for i in range(n):
        h=int(arr[i]**(1/2))+2
        flg=0
        for x in range(1,h):
            if arr[i]%x!=0:
                continue
            y = arr[i]//x
            if x in arr or y in arr:
                if y==arr[i]:
                    if arr.count(y)>1:
                        flg=1
                    else:
                        flgdd=1
                else:
                    flg=1
        if flg==0:
            ans+=1
    print(ans)
    return

    #print(arr)
    ans=0
    for i in range(n):
        flg=0
        if i==0:
            if arr[i]!=arr[i+1]:
                ans+=1
            continue

        h=arr[i]//2+1
        for j in range(0,i):
            if arr[i]%arr[j]==0:
                flg=1
                break
            if arr[j] > h:
                break
        if flg==0:
            if (i+1)<n:
                if arr[i]==arr[i+1]:
                    flg=1
        if flg==0:
            ans+=1
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:
import sys

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

def main():

    N = int(input())
    A = sorted(list(map(int,input().split())))
    check = [0] * N
    ans = 0

    if A.count(A[0]) == 1:
        ans += 1

    for i in range(N-1):
        if check[i] == 0 and i != 0:
            ans += 1
        for j in range(i+1,N):

            if check[i] == 0:
                if A[j] % A[i] == 0:
                    check[j] = 1
            else:
                break
    print(ans)
    """

    if A.count(A[0]) == 1:
        ans += 1

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

def heapsort(iterable):
  h = []
  for value in iterable:
    heapq.heappush(h, value)
  l = []
  for _ in range(len(h)):
    l.append(heapq.heappop(h))
  return l

n = ri()
li = rl()
dic = {}
for w in li:
    if w in dic:
        dic[w] += 1
    else:
        dic[w] = 1
li1 = []
li2 = []
for k, v in dic.items():
    if v > 1:
        li1.append(k)
    else:
        li2.append(k)
li1 = heapsort(li1)
li2 = heapsort(li2)
le1 = len(li1)
le2 = len(li2)
cnt = 0
for i in range(le2):
    li2i = li2[i]
    for j in range(i):
        li2j = li2[j]
        if li2j > li2i**0.5:
            for k in range(le1):
                li1k = li1[k]
                if li1k > li2i**0.5:
                    cnt += 1
                    break
                if li2i % li1k == 0:
                    break
            else:
                cnt += 1
            break
        if li2i % li2j == 0:
            break
    else:
        for k in range(le1):
            li1k = li1[k]
            if li1k > li2i**0.5:
                cnt += 1
                break
            if li2i % li1k == 0:
                break
        else:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

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

arr = np.array(p)
rev = 1/arr
ans = 0
for i in range(N):
    a = arr[i]*rev
    for j in range(N):
        d = a[j].is_integer()
        if a[j]==1:
            ans = ans
        elif d:
            ans = ans + 1
            break
print(N-ans)

Submission status: Wrong Answer

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

def divisor(n):
    ass = set()
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.add(i)
            if i**2 == n:
                continue
            ass.add(n//i)
    return ass

ans=n
s=set()
for i in range(n):
    for k in s:
        if a[i]==k:
            ans-=1
            break
    for k in divisor(a[i]):
        s.add(k)
print(ans)

Submission status: Wrong Answer

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

for i in range(n - 1):
    ii = i
    i = i - l
    keep = 0
    for j in range(ii + 1, n - l):

        if aa[j - l] % aa[i] == 0:
            aa.pop(j - l)

            l += 1
print(len(aa) - 1)

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    A = sorted(A)
    if len(set(A)) == len(A):
        for i in range(1, N):
            count = 0
            for j in range(i):
                if A[i] % A[j] == 0:
                    count += 1
            if count == 0:
                ans += 1
        print(ans)
    else:
        print("0")
resolve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())

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


lpf = defaultdict(list)



def primes1(n):
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]

primes = primes1(10**6+1)

primes = primes[:78500]

# print(primes)

for a in range(n):
    for p in primes:
        if alist[a] % p == 0:
            lpf[p].append(alist[a])

res = 0

for k, v in lpf.items():
    # print(v)
    tranv = set(v)
    if len(tranv) > 0:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
import copy

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

count = 0

for i in range(n-1):
    c_ = 0
    a_ = copy.copy(a)
    del a_[i]
    for j in a_:
        if  (a[i] % j) == 0:
            break
        else:
            c_ += 1
    if c_ == (n - 1):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=list(map(int,input().split()))
a=set(a)
a=list(a)
a.sort(reverse=True)
d=1
ans=1
if len(a)==1:
  print(0)
  exit()
for i in range(len(a)):
    d*=a[i]
    if (d//a[i])%a[i]==0:
        ans+=1
print(ans)