Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

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
def prime_factorize(n):
    prime_fact = []
    while n%2 == 0:
        prime_fact.append(2)
        n//=2
    f = 3
    while f * f <= n:
        if n % f == 0:
            prime_fact.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        prime_fact.append(n)
    return prime_fact
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    for i in range(2,int(n**0.5)+1):
        if n%i != 0:
            continue
        else:
            return False
    return True


if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    a.reverse()
    cnt = 0
    c = collections.deque(a)
    d = collections.deque([])
    cnt = 0
    for i in range(n-1):
        flag = 0
        b = c.popleft()
        for j in c:
            if b%j == 0:
                flag = 1
                break
        if flag == 0:
            cnt+=1
    b = c.popleft()
    flag = 0
    for i in range(n-1):
        if b%a[i] == 0:
            flag = 1
            break
    if flag == 0:
        cnt+=1
    print(cnt)

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)
# print(divs)

n = int(input())
A = [int(i) for i in input().split()]
ans = 0
A.sort()
if n > 1:
    if A[0] != A[1]:
        ans = 1
for i in range(1, n):
    can_div = False
    for j in range(0, i):
        if A[i] % A[j] == 0:
            can_div = True
            break
        if A[j] > A[i] // 2:
            if A[i-1] == A[i]:
                can_div = True
            else:
                break
    if not can_div:
        ans += 1

print(ans)

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 (i!=n 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:
import sys
N = int(input())
a_list = [int(_c) for _c in 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

a_list = sorted(a_list)

if 1 in a_list:
    if a_list.count(1) == 1:
        print(1)
    else:
        print(0)
    sys.exit(0)

answers = []
ng_list = []
for a in a_list:
    if a in answers:
        if a not in ng_list:
            ng_list.append(a)
        continue

    if len(answers) == 0:
        answers.append(a)
        continue

    a_soinsuu = factorization(a)

    append_num = True
    for _a_soinsuu in a_soinsuu:
        if _a_soinsuu[0] in answers:
            append_num = False
            break

    if append_num:
        answers.append(a)

print(len(answers) - len(ng_list))

Submission status: Wrong Answer

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

count=n
sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    if all(L % L2 != 0 for L2 in sosuu):  # すべての既存素数で割り切れなかったら素数
        sosuu.append(L)

for i in range(n):
    flg=0
    if a[i] in sosuu:
        continue 
    for j in range(n): 
        if a[i]%a[j]==0 and i!=j:
            #print(a[i],a[j])
            count-=1
            break

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



from collections import Counter

c = Counter(A)

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

D = sorted(D)

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

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

print(ans-a)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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


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

    if i != len(A)-1 and A[i] == A[i+1]:
        count -= 1

print(count)

Submission status: Wrong Answer

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



l.sort()
j = [0]*2

for i in l:
    if i%2 == 0:
        if j[0] == 0:
            j[0] = i
            break

for m in l:
    if m%2 != 0:
        if j[1] == 0:
            j[1] = m
            break
    

ans = 0
for k in l:
    if k in j:
        ans += 1
    elif k%2 == 0:
        if k%j[0] != 0:
            ans += 1
    else:
        if k%j[1] != 0:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
li = list(map(int, input().split()))
li.sort()

if len(set(li)) == 1:
  print(0)
  sys.exit()

def del_(list_):
  key = list_.pop(0)
  new = [x for x in list_ if x % key != 0]
  return new

result = 0
j = len(li)

while result <= j:
  if len(li) > 1:
    li = del_(li)
    result += 1
  else:
    result += 1
    break

print(result)

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 = list(sorted(list(map(int,input().split()))))
sosuu = []
hukusuu = []

for i in range(len(a_list)-1,0,-1):
  if a_list[i] == a_list[i-1]:
    hukusuu.append(i)
    hukusuu.append(i-1)
    
hukusuu = sorted(list(set(hukusuu)),reverse=True)
for i in hukusuu:
  a_list.pop(i)

if len(a_list) == 0:
  print(0)
else:
  for i in range(len(a_list)-1,-1,-1):
    hoge = factorization(a_list[i])
    if len(hoge) == 1 and hoge[0][1] == 1:
      sosuu.append(a_list[i])
      a_list.pop(i)
  sosuu = sorted(sosuu)
  a_list = sorted(a_list)
  while 1:
    if len(a_list) == 0:
      break
    num = a_list.pop(0)
    iranai = False
    for i in sosuu:
      if num % i == 0:
        iranai = True
        break
    if iranai == False:
      sosuu.append(num)

  print(len(sosuu))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
def set_list(es):
    return len(list(set(es))) == 1
count = 0
if set_list(A):
    print(count)
    exit()
while A != []:
    if  len(A)>=2 and A[0] != A[1]:
        count += 1
    s = A.pop(0)
    B = [A[j] for j in range(len(A)) if A[j]%s != 0]
    A = B
count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1:
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
if a[0] < a[1]:
  ans = 1
else:
  ans = 0
s.add(a[0])
print(ans)
for nm,i in enumerate(a[1:]):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct):
      c.add(num(div))
  if c&s == set() and (nm < n-2 and a[nm+2] != i) or nm == n-2:
    ans += 1
  s.add(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.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()))
A=list(set(a))
if len(A) ==1:
    c=0
else:
    c=len(A)
for i in range(len(A)):
    # print(A[i])
    arr = factorization(A[i])
    # print(arr)
    A_ = A[:i]+A[i+1:]
    for j in range(len(arr)):
        for k in range(arr[j][1]):
            # print(pow(arr[j][0],k+1))
            if pow(arr[j][0],k+1) in A_:
                c-=1
                # print('C',c)
                break
        else:
            continue
        break

print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = []
if len(set(A)) == 1:
    print(0)
elif A[0] == 1:
    print(1)
else:
    is_prime = [False] * (A[-1]+1)
    for a in A:
        is_prime[a] = True
    for i in A:
        if not is_prime[i]:
            continue
        for j in range(i * 2, A[-1]+1, i):
            is_prime[j] = False
    ans = [i for i in range(A[-1]+1) if is_prime[i]]
    print(len(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
chklist=[1]*n
for i in range(n):
  if chklist[i]==1:
    for j in range(i+1,n):
      if a[j]%a[i]==0:
        chklist[j]=0
chkflag=True
for i in range(n-1):
  if a[i]!=a[i+1]:
    chkflag=False
    break
if chkflag:
  print(0)
else:
  print(sum(chklist))

Submission status: Wrong Answer

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

flag = [0 for _ in range(N)]

for n in range(N):
    if n > 0 and A[n-1] == A[n]:
        flag[n-1] = 1
        flag[n] = 1    

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

print(flag.count(0))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
# stdin = open("sample.txt")

MOD = 1000000007
INF = float('inf')

def keta(kazu):
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def combination(m,n):
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x
    
def main():
    n = int(stdin.readline().rstrip())
    a_kari = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    a = list(set(a_kari))
    ans = 0
    for i in range(len(a)):
        for j in range(i):
            if a[i] // a[j] > 0 and a[i] % a[j] == 0:
                ans += 1
                break
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
S=0
for i in range(1,N):
	flag=0
	for j in range(0,i-1):
		if A[i]%A[j]==0:
			flag=1
			break
	if flag==0:
		S=S+1
if A[N-1]!=A[N-2]:
	S=S+1
print(S)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

count = 0

for i in range(n-1):
  flag = 0
  if a[i] % a[i+1] != 0:
    for j in range(i+2,n)[::-1]:
      if a[i] % a[j] == 0:
        flag = 1
        break
  else:
    flag = 1
  if flag == 0:
    count += 1
    
if a[-1] % a[-2] != 0:
  count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

upper_bound = 200001

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

dup = [key for key, value in Counter(nums).items() if value >= 2]

out = set()
for d in dup:
	if d not in out:
		to_add = [d * i for i in range(1, 2 + upper_bound // d) if i not in out]
		for y in to_add:
			out.add(y)

nums = sorted([x for x in nums if x not in dup])

cnt = 0
for x in nums:
	if x not in out:
		cnt += 1
		to_add = [x * i for i in range(1, 2 + upper_bound // x) if i not in out]
		for y in to_add:
			out.add(y)

print(cnt)

Submission status: Wrong Answer

Solution code:
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
  
def main():
  m = int(input())
  a = LI()
  ans = 0
  n = max(a)
  num = [True]*(n+1)
  num[0] = num[1] = False
  a.sort()
  for i in range(m):
    if (i != m-1 and a[i]==a[i+1]) or (i != 0 and a[i]== a[i-1]): num[a[i]] = False
    for j in range(a[i]*2, n+1, a[i]):
      num[j] = False
  for aa in a:
    if num[aa]:
      ans += 1
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
count = 1
for i in range(N-1):
  flag = 1
  for j in range(N-1, i, -1):
    if A[i] % A[j] == 0:
      flag = 0
      break
  if flag:
      count += 1
if N == 1:
  print(1)
elif A[0] == A[1] and count == N:
  print(0)
else:
  print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
mis=0
for i in range(len(a)):
  # if a[i]==a[i-1]:
  #   continue
  for j in range(i):
    if a[i]%a[j]==0:
      if i!=j:
        mis=1
        break
  if mis==0:
    ans+=1
  mis=0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy as cp
from numba import jit
@jit
def fac_serch():
    n = int(input())
    all_num = list(map(int,input().split()))
    all_num.sort()
    factor = []
    tmp_fac = list()
    if(all_num[0] == all_num[-1]):
        print(0)
        sys.exit()
    while(len(all_num)!=0):
        now_factor = all_num.pop(0)
        factor.append(now_factor)
        if(len(all_num) == 0):
            break
        tmp_fac = []
        for i in range(len(all_num)):
            # print(all_num,i)
            if(all_num[i]%now_factor != 0):
                tmp_fac.append(all_num[i])
        all_num = cp.copy(tmp_fac)
    return len(factor)
print(fac_serch())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections

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[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if arr==[]:
        arr[n] = 1

    return arr

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    factors_dict = collections.defaultdict(int)

    count = 0
    counted_items = set()

    for i, a in enumerate(A):

        if A.count(a) > 1:
            continue
        primes = factorization(a)

        count_flag = True
        for k, v in primes.items():
            if not factors_dict[k] == 0 and not factors_dict[k] > v:
                count_flag = False
        if count_flag == True:
            count += 1
            counted_items.add(a)
            for k, v in primes.items():
                factors_dict[k] = max(v, factors_dict[k]) if factors_dict[k] != 0 else v
            continue
        else:
            break_flag = False
            for c in counted_items:
                if a % c == 0:
                    break_flag = True
                    break
            if break_flag == False:
                count += 1
                counted_items.add(a)

    print(count)
    return

def solve2(N: int, A: "List[int]"):
    A = sorted(A)
    factors_dict = collections.defaultdict(int)
    count = 0
    counted_items = set()

    for i, a in enumerate(A):
        if A.count(a) > 1:
            continue
        primes = factorization(a)
        break_flag = False
        for k, v in primes.items():
            if factors_dict[k] == 0:
                count += 1
                factors_dict[k] = max(factors_dict[k], v)
                counted_items.add(a)
                break_flag = True
                break
            if factors_dict[k] > v:
                count += 1
                factors_dict[k] = max(factors_dict[k], v)
                counted_items.add(a)
                break_flag = True
                break
        if break_flag == False:
            for c in counted_items:
                if a % c == 0:
                    break
                count += 1
                counted_items.add(a)

    print(count)
    return


def solve_ld(N: int, A: "List[int]"):
    A = sorted(A)
    factors_dict = collections.defaultdict(int)
    count = 0
    for i, a in enumerate(A):
        primes = factorization(a)
        included = True
        for k, v in primes.items():
            if not factors_dict[k] > v:
                included = False
                break

        if included == False:
            print('included:', False)
            print(factors_dict)
            for k, v in primes.items():
                if factors_dict[k] > 0:
                    factors_dict[k] = min(v, factors_dict[k])
                else:
                    factors_dict[k] = v
            if len(included_set) == 0:
                count += 1
                included_set.add(a)
                continue
            for element in included_set:
                if not a % element == 0:
                    count += 1
                    included_set.add(a)
                    break

    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
nun_list = list(map(int, input().split()))
count=0
hoge = len(nun_list) - 1

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

def set_list(es):
    return len(list(set(es))) == 1

if (set_list(nun_list)) :
    print(0)
    sys.exit()


for i in range(1,n+1):
    if is_prime(nun_list[i-1]):
        count+=1
        continue
    tmp = 0
    for j in range(1,n+1):
        if i != j:
            if nun_list[i-1] % nun_list[j-1]  == 0:
                break
            else :
                tmp+=1
    if tmp == hoge:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
tmp = set()
from bisect import bisect_left
while True:
    v = a[0]
    if v**2>a[-1]:
        for item in a:
            tmp.add(item)
        break
    tmp.add(v)
#     na = []
#     ii = bisect_left(a, v*2)
#     for 
    a = [item for item in a if item%v!=0]
    if not a:
        break

# tmp = [a[0]]
# for i in range(1, n):
#     num = a[i]
# #     for i in range(len(tmp)-1, -1, -1):
#     for i in range(len(tmp)):
#         item = tmp[i]
#         if num%item==0:
#             break
#         if item*2>num:
#             tmp.append(num)
#             break
#     else:
#         tmp.append(num)

tmp = set(tmp) - s
print(len(tmp))

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n):
  if a[i] != 0:
    if i == n-1:
      ans +=1
    else: 
      if a[i] == a[i+1]:
        for j in range(i+1, n):
          if a[j]%a[i]==0:
            a[j]=0
      else:
        ans += 1
        for j in range(bisect.bisect_left(a, 2*a[i]), n):
          if a[j]%a[i]==0:
            a[j]=0
        
    
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right

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

flag = [False for _ in range(n)]
i = 0
for i in range(n):
	if flag[i]:
		continue
	num = a[i]
	index = bisect_right(a,num)
	if i != index-1:
		for j in range(i,index):
			flag[j] = True
	index = bisect_left(a,num*2)
	if index == len(a):
		break
	for j in range(index,n):
		if a[j] % num == 0:
			flag[j] = True

#print(a)
#print(flag)
print(flag.count(False))

Submission status: Wrong Answer

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

sorted_a_list = sorted(a_list)

cnt = 0
for i in range(n):
    if i < (n-1) and sorted_a_list[i] == sorted_a_list[i+1]:
        continue

    divisible = False
    for j in range(i):
        a = sorted_a_list[i]
        b = sorted_a_list[j]
        if a == b:
            divisible = True
            break
        if b > a/2:
            break
        if a % b == 0:
            divisible = True
            break
    if not divisible:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

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=True
    for j in range(n):
        if(((a[i]%a[j]) == 0) and (i != j)):
            print(a[i],a[j],i,j)
            flag=False
    if(flag == True):
        x += 1
print(x)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

readline = sys.stdin.readline


def solve(a):
    ans = 0
    while len(a):
        x  = a[0]
        if len(a) != 1:
            if x==a[1]:
                a = a[a != x]
            else:
                ans += 1
                a = a[a % x != 0]
        else:
            return ans + 1
    return ans

n = int(input())
a = np.array(readline().split(), dtype=np.int64)
a.sort()
print(solve(a))

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  a.sort()
  if a[0]==a[-1]:
    print(0)
    exit()
  if a[0]==1:
    print(1)
    exit()
  a=a+[0]
  ans=0
  for i in range(1,n):
    if a[i]==a[i-1] or a[i]==a[i+1]:
      continue
    else:
      ans+=1
      for j in range(i):
        if a[i]%a[j]==0:
          ans-=1
          break
  print(ans)
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

A.sort()

se = set(A)
if len(se) == 1 and N > 1:
    print(0)
    exit()

for i in range(N):
    tmp = set()
    for s in se:
        if s == A[i] or s % A[i] != 0:
            tmp.add(s)
    se = se & tmp

print(len(se))

Submission status: Wrong Answer

Solution code:
# 2020/06/14
# AtCoder Beginner Contest 170 - D

# Input
n = int(input())
a = list(map(int,input().split()))
a.sort()
a.append(10**7)
sosulist = list()
sosulist.append(0)

# Calc
ans = n

if a[0] == a[1]:
    ans = ans - 1

for i in range(1, n):
    if a[i] == a[i+1]:
        ans = ans - 1
        sosulist.append(i)

    else:
        wkval = 1
        slen = len(sosulist)
        for j in range(slen):
            if a[i] % a[sosulist[j]] == 0:
                ans = ans - 1
                wkval = 0
                break
            if a[i] // 2 <= a[sosulist[j]]:
                break

        if wkval == 1:
            sosulist.append(i)

# Output
print(ans)

Submission status: Wrong Answer

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

# 全部同じ数
lenset = len(set(a))
if len(set(a)) == 1:
    print('0')
    exit()


a.sort(reverse=True)
ndup = 0

# 同じ数が含まれる→その組み合わせ数を取得・リストには1つだけ残す
if lenset != n:
    for i in a:
        count = a.count(i)
        if count >= 2:
            ndup += 1
            for j in range(count-1):
                a.remove(i)


# print(a)

size = len(a)

ans = 0

for i in range(size-1):
    n_divide = 0
    for j in range(i+1, size):
        # print(a[i], a[j])
        if  a[i] % a[j] == 0:
            if a[i] == a[j]:
                i += 1
            break
        n_divide += 1

    if n_divide == size - (i+1):
        ans += 1

print(ans+1-ndup)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = n
dic = {}
for i in range(n):
    if a[i] not in dic.keys():
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1
cnt = n
res = list(dic.keys())
chk = [0 for i in range(len(res))]
for i in range(len(res)):
    if dic[res[i]] >= 2:
        cnt -= dic[res[i]]
        chk[i] = 1
for i in range(len(res)-1, -1, -1):
    if chk[i] != 1:
        for j in range(0, i):
            if res[i] < res[j]*2:
                break
            if res[i]%res[j] == 0:
                print(res[i], dic[res[i]])
                cnt -= dic[res[i]]
                break
print(cnt)

Submission status: Wrong Answer

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

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

is_continue = [False] * n

A.sort()
ans = 0

div_set = set([])


def div(x):
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            if i in div_set or x // i in div_set:
                div_set.add(x)
                return False
    div_set.add(x)
    return True


for i in range(n):
    if i != n - 1:
        if A[i] == A[i + 1]:
            div_set.add(A[i])
            continue
        elif A[i] not in div_set and div(A[i]):
            ans += 1
    elif A[i] not in div_set and div(A[i]):
        ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
#Q4
input()
nums = [int(s) for s in input().split(" ")]
nums.sort(reverse=True)
count = 0
for i in range(len(nums) - 1):
    flag = 0
    for j in range(1, len(nums) - i):
        #print("{0} % {1} = {2}".format(nums[i], nums[i + j], nums[i]%nums[i + j]))
        if nums[i]%nums[i + j] == 0:
            flag = 1
    if flag == 0:
        count = count + 1
print(count + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
if n == 1:
    print(0)
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
        elif a[i] % a[i-1] == 0:
            ans -= 1
        else:
            flag = True
            for j in range(i-1):
                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 numpy as np

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
List = list(map(int,input().split()))
List.sort()
List2= []

for i in range(N-1):
  a = List[i]
  b = List[i+1]
  if a != b:
    List2.append(a)

if List2 == []:
  print(0)
elif len(List2) == 1:
  print(1)
else:
  ans = [List2[0]]

  for i in range(1,len(List2)):
    a = List2[i]
    b = np.gcd(a, ans)
    if max(b) == 1:
      ans.append(a)
  print(len(ans))