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:
def resolve():
    import bisect
    import math
    n = int(input())
    a = list(map(int, input().split()))
    a1 = {}
    for i in range(len(a)):
        if a[i] in a1:
            a1[a[i]] += 1
        else:
            a1[a[i]] = 1
    a2 = []
    for i in a1.keys():
        if a1[i] == 1:
            a2.append(i)

    if len(a2) == 0:
        print(0)
        exit()

    a = sorted(a2)
    maxa = a[-1]
    maxi = bisect.bisect_left(a, math.ceil(maxa**0.5))

    ans = [1]*(len(a))
    for i in range(0, maxi+1):
        if ans[i] == 1:
            for j in range(i+1, len(a)):
                if ans[j] == 0:
                    continue
                if a[j] == a[i]:
                    ans[i] = 0
                if a[j] % a[i] ==0:
                    ans[j] = 0
    print(sum(ans))
resolve()

Submission status: Wrong Answer

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

a.sort()
for i in range(10**10):
  try:
    k=a[i]
    keep=i
    for j in range(10**10):
      keep+=1
      try:
        t=a[keep]
        if t%k==0:
          if t!=k:
            a.pop(keep)
            keep-=1
          if t==k:
            a.pop(i)
            a.pop(keep-1)
            keep-=2
      except IndexError:
        break
  except IndexError:
    break

print(len(a))

Submission status: Wrong Answer

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

    A.sort(reverse= True)

    count = 0
    for idx,i in enumerate(A):
        if i == A[idx -1]:
            continue
        if idx != N-1 and i == A[idx +1]:
            B.discard(i)

        deleted =set()
        for j in B:
            if i!=j and j % i ==0:
                deleted.add(j)
        B.difference_update(deleted)
        
        if i in B:
            count +=1
        B.discard(i)




    print(count)

resolve()

Submission status: Wrong Answer

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

if len(a_list) == 1:
    print(0)
else:
    if a_list[0] != a_list[1]:
        ans += 1
    for i in range(1, n):
        for j in range(i):
            if a_list[i] % a_list[j] == 0:
                break
            if a_list[j] > a_list[i] / 2:
                ans += 1
                break
            if j == i - 1:
                ans += 1
                break;
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
from collections import Counter
a_cnt = Counter(a)
a = []
for k, v in a_cnt.items():
    if v == 1:
        a.append(k)
a.sort()
ans = 0
if len(a) > 0:
    sosuu=[a[0]]
    for L in a[1:]:
        chk=True
        for L2 in sosuu:
            if L%L2 == 0:chk=False
        if chk==True:sosuu.append(L)
    print(len(sosuu))
else:
    print(0)

Submission status: Wrong Answer

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

def eratosthenes(n):
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    is_prime[4::2] = [False] * (n // 2 - 2)
    m = int(n**.5) + 1
    for i in range(3, m, 2):
        if is_prime[i]:
            is_prime[i*i::2*i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    return [2] + [i for i in range(3, n, 2) if is_prime[i]]
    # return is_prime

prime = eratosthenes(2*10**6+10)
l = [0] * (10**6+1)
for a in A:
    l[a] += 1
ans = 0
if l[1] == 1:
    ans += 1
l[1] = False
f = False
for i in range(2, 10**6+1, 2):
    if l[i] == 0:
        l[i] = False
        continue
    if l[i] == 1 and not f:
        # print(i)
        ans += 1
        f = True
    else:
        f = True
    l[i] = False
for j in range(3, int((10**6+1)**.5), 2):
    f = False
    if l[j]:
        for i in range(j, 10**6+1, j):
            if l[i] == 0:
                l[i] = False
                continue
            if l[i] == 1 and not f:
                # print(i)
                ans += 1
                f = True
            else:
                f = True
            l[i] = False
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=map(int,input().split())
A=sorted(a)
answers=[A[0]]
if N==1:
    print(A[0])
else:
     del A[0]
     for a in A:
         number=0
         if a in answers:
             answers.remove(a)
         else:
             for b in answers:
                 if a%b==0:
                     number=1
                     break
             if number==0:
                 answers.append(a)
print(len(answers))

Submission status: Wrong Answer

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

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

count = 0
for i in range(len(a)):
    if len(a) == 1:
        break
    elif 1 in a:
        break
    elif is_prime(a[i]):
        count += 1
    else:
        checker = 0
        for j in range(len(a)):
            if i != j and a[i] % a[j] == 0:
                checker = 1
                break
        if checker == 0:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    i = 0
    for j in A:
        if i == j:
            isPrime[i] = False
        i = j
        if i > 10**3:
            break
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
*A, = map(int, input().split())
A.sort()
a = []
b = []
last = 0
for i in range(N):
    if last != A[i]:
        a.append([A[i], 0])
        b.append(A[i])
        last = A[i]
    a[-1][1] += 1

h = [False]*(10**6+1)
ans = 0
for n, c in a:
    if c == 1:
        ok = True
        for i in range(2, int(n**0.5)+1):
            while n % i == 0:
                n = n//i
                if h[n] or h[i]:
                    ok = False
                    break
            if not ok:
                break
        if n != 1:
            if h[n]:
                ok = False
        if ok:
            ans += 1
    h[n] = True
print(ans)

Submission status: Wrong Answer

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

ans = 0

if len(A) > 2:
    for i in range(len(A)):
        for j in range(i+1):
            if A[i] % A[j] == 0:
                if j != i:
                    break
        else:
            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)
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:
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):
                d_num -= A_count[A_set[i]]
                break
    print(d_num)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
A=list(map(int,input().split()))
ans=0
for i in A:
    for j  in A:
        if i>j and i != j:
            if i%j==0:
                ans+=1
                break
print(ans)

Submission status: Wrong Answer

Solution code:
n =  int(input())
A = list(map(int,input().split()))
A.sort()
count = 0
if n == 1:
    count = 1
else:
    for i in range(len(A)):
        a = A[i]
        end = False
        if i ==len(A)-1:
            if A[i]==A[i-1]:
                end = True
            for j in range(0, i):
                b = A[j]
                if end:
                    count = count +1
                    break
                elif a%b ==0:
                    count = count+1
                    break
        else:
            if A[i]==A[i-1] or A[i] ==A[i+1]:
                end = True
                if end == True and i==0:
                    count = count +1

            for j in range(0, i):
                b = A[j]
                if end:
                    count = count +1
                    break
                elif a%b ==0:
                    count = count+1
                    break

print(n-count)

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

    if arr==[]:
        arr.append([n, 1])

    return arr

  
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):
    if len(factorization(a_list[i])) == 1:
      sosuu.append(a_list[i])
      a_list.pop(i)

  # 素数の重複判定
  sosuu = sorted(sosuu)
  iranai_index = []
  for i in range(len(sosuu)-1):
    if sosuu[i] == sosuu[i+1]:
      iranai_index.append(i,i+1)
  iranai_index = list(set(sorted(iranai_index,reverse=True)))
  for i in iranai_index:
    sosuu.pop(i)

  a_list = sorted(a_list, reverse=True)
  while len(a_list) != 0:
    num = a_list.pop()
    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:
"""
    こんにちは。これはクシャルです
    
    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)
    if len(a) == len(set(a)):
        print(len(a) - qw(a,len(a)))
        return
    print(abs(len(list(set(a))) - qw(list(set(a)),len(list(set(a)))) - len(q) + q.count(0)))
            
################## ---- 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:
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 = [False for i in range(n + 10)]
for p in arr:
    if not prime[p]:
        for j in range(p+p, n+1, p):
            prime[j] = True
count = 0
for i in arr:
    if not prime[i]:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
if n == 1:
	print(1)
	exit()
a = list(map(int,input().split()))
t = Counter(a)
b = []
for i, j in t.most_common():
	if j == 1:
		b.append(i)
bset = set(a)

def sieve(n):
	ret = []
	divlis = [-1]*(n+1)  # 何で割ったかのリスト(初期値は-1)
	flag = [True]*(n+1)
	flag[0] = False
	flag[1] = False
	ind = 2
	while ind <= n:
		if flag[ind]:
			ret.append(ind)
			ind2 = ind**2
			while ind2 <= n:
				flag[ind2] = False
				divlis[ind2] = ind
				ind2 += ind
		ind += 1
	#何で割ったかのリストを取得したいとき, divlisも出力する
	return ret

k = sieve(10000)

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

ans = 0
for i in b:
	t=makediv(i)
	mode = 1
	for l in t:
		if l in bset:
			mode = 0
			break
	if mode:
		ans += 1
print(ans)

Submission status: Wrong Answer

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

count = 0
for i, Ai in enumerate(A):
  flag = 0
  for j, Aj in enumerate(A):
    if i == j:
      continue
    if (Ai % Aj) == 0:
      flag = 1
      break
  if flag == 0:
    count += 1
if len(A) == 1:
  print(0)
else:
  print(count)

Submission status: Wrong Answer

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

a.sort(reverse=True)
ans = 0

for i in range(n - 1):
    for j in reversed(range(i + 1, n)):
        if a[i - 1] == a[i] or a[i] == a[i + 1]:
            break
        elif a[i] % a[j] == 0:
            break
        elif a[i] < 2 * a[j] or j == i + 1:
            ans += 1
            break

if a[n - 2] != a[n - 1]:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 21:14:26 2020

@author: NEC-PCuser
"""

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

A.sort()


li = []
li2 = []
before_value = 0
next_flg = False
for n in A:
    if len(li) == 0:
        li.append(n)
        li2.append(n)
        next_flg = True
    if before_value == n:
        if li[len(li) - 1] == n:
            li.pop(len(li) - 1)
        next_flg = False
        before_value = n
        continue
    before_value = n
    if next_flg is True:
        next_flg = False
        continue
    for n2 in li2:
        if (n % n2 == 0):
            break
        if (n < n2 * n2):
            li.append(n)
            break
    else:
        li.append(n)

print(len(li))

Submission status: Wrong Answer

Solution code:
N=int(input())
hitoketa=[]
count=0
A=list(map(int,input().split()))
A.sort()
for i in range(min(10**3,N)):
    hitoketa.append(A[i])
for i in range(len(hitoketa)):
    for j in range(len(hitoketa)):
        if hitoketa[i]%hitoketa[j]==0 and hitoketa[i]!=hitoketa[j]:
            hitoketa[i]=10**6+1
#hitoketa.sort()
#print(hitoketa)
hitoketa_set=set(hitoketa)
for i in A:
    for j in hitoketa_set:
        if i != j and i%j==0:
            count+=1
            continue
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter


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


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

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

ans = 0
for i in new:
    div = make_divisors(i)
    if len(set(new) & set(div)) == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

num = n
if n >= 2:
    if a[0] == a[1]:
        num = n-1
    for i in range(1, n):
        for j in range(i):
            if a[i] % a[j] == 0:
                num -= 1
                break
print(num)

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

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
INF = float('inf')
from collections import defaultdict
dic = defaultdict(lambda:INF)

used = defaultdict(lambda:0)
remove = defaultdict(lambda:0)


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

from collections import Counter
def prime_factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

for aa in a:
    if used[aa]:
        remove[aa]=1
        break
    c = prime_factorize(aa)
    flg = True
    for k in c.keys():
        if dic[k] == INF:
            dic[k] = aa//k
        else:
            if dic[k] > aa//k:
                dic[k] = aa//k
            elif (aa//k)%dic[k]==0:
                flg = False

    if flg:
        used[aa]=1

ans = sum(list(used.values()))-sum(list((remove.values())))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int , input().split()))
if max(A) == min(A):
    print(0)
    sys.exit()
#A = list(set(A))
A.sort(reverse=True)
count = 0
for i in range(0,len(A)-1):
    for j in range(i+1,len(A)):
        if A[i] % A[j] == 0:
            count += 1
            break
print(max(0,len(A)-count))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=sorted(a)
ct=0
for i in range(n):
    t=0
    d=0
    while d==0:
        if i!=t and b[i]==b[t]:
            d+=1
            ct+=1
        elif b[i]%b[t]==0 and i!=t:
            d+=1
            ct+=1
        elif b[t]>b[i]/2:
            d+=1
        else:
            t+=1
print(n-ct)

Submission status: Wrong Answer

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

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

count = 0
found = 0
for i in range(N):
    for j in range(N):
        if i != j:
            if A[i] % A[j] == 0:
                break
            else:
                found = found + 1
        else:
            continue
    if found == 4:
        count = count + 1
    found = 0
        


print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

l.sort()

ct=0
if n>1 and l[1]!=l[0]:
  ct=1
elif n==1:
  ct=1
for i in range(1,n):
  flag=0
  for j in range(i):
    if l[i]%l[j]==0:
      flag=1
      break
  #print(flag,l[i])
  if flag==0:
    ct+=1

print(ct)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
box = [1] * (a[-1] + 1)
ans = 0
if n == 1:
    print(1)
else:
    for i in range(n):

        if i == 0:
            for j in range(a[-1] // a[i]):
                box[a[i] * (j + 1)] = 0
            if a[1] != a[0]:
                ans += 1
        elif i == n - 1:
            if box[-1] == 1:
                ans += 1
        else:
            if a[i] != a[i - 1] and a[i] != a[i + 1]:
                if box[a[i]] == 1:
                    ans += 1
                    for j in range(a[-1] // a[i]):
                        box[a[i] * (j + 1)] = 0
            elif a[i] != a[i + 1]:
                for j in range(a[-1] // a[i]):
                    box[a[i] * (j + 1)] = 0
    print(ans)

Submission status: Wrong Answer

Solution code:
def check_prime(k):
    '''
    素数の時1、合成数の時0を返す
    '''
    if k == 1:return 0
    for i in rec:
        if i > k // 2:break
        if k % i == 0:return 0
    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
rec = [a[0]]
double = dict()
for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        rec.append(a[i])
        continue
    if double.get(a[i]):continue
    temp = check_prime(a[i])
    if temp:
        rec.append(a[i])
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():

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

    d = dict()
    for v in A:
        d[v] = d.get(v, 0) + 1
    if 1 in d:
        if d[1] == 1: return 1
        else: return 0

    A.sort()
    s = set()
    ans = 0
    for i in range(N):
        if d[A[i]] == 1:
            if A[i] not in s:
                ans += 1
            k = 1
            while k * A[i] <= A[-1]:
                s.add(k * A[i])
                k += 1
    return ans




if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
d = list(map(int, input().strip().split()))

# 重複しているやつは削除
counts = collections.Counter(d)
d = []
for a, c in counts.items():
    if c == 1:
        d.append(a)

dic = {a: True for a in d}
if len(dic) == 0:
    print(0)
    exit(0)

keys = sorted(dic.keys())
last = keys[-1] + 10

for k in keys:
    if dic[k]:
        n = 2
        while k * n <= last:
            if k * n in dic:
                dic[k * n] = False
            n += 1

count = len([True for v in dic.values() if v])
print(count)

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(1,n-i):
        if a[i]%a[i+j] == 0:
            count += 1
            break

print(n-count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())), reverse = True)
ans=0
mem={}
for i in range(n):
    for j in range(i+1,n):
        if tuple(sorted((a[i],a[j]))) in mem:
            ans+=1
            break
        if a[i]%a[j]==0:
            mem[tuple(sorted((a[i],a[j])))]=1
            ans+=1
            break
if n > 1 and a[-1]==a[-2]:
    ans+=1

print(n-ans)

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
n=int(input())
A=list(map(int,input().split(" ")))
g=0
for i in range(n):
  if is_prime(A[i]):
    for j in range(n):
      if i!=j:
        if A[i]==A[j]:
          g=g+1
          break
  else:
    for j in range(n):
      if i!=j:
        if A[i]%A[j]==0:
          g=g+1
          break
print(n-g)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(0)
    exit()

Ss = sorted(As)
primes = set()
cnt = 0
d = defaultdict(int)
for s in Ss:
    d[s] += 1
# print(Ss)
mn = min(Ss)
for s in Ss:
    if d[s] > 1:
        continue
    flg = False
    for p in primes:
        if s % p == 0: 
            flg = True
            break
    if not flg:
        cnt += 1
        if s*mn <= 10**6:
            primes.add(s)
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
search = list(map(int,input().split()))
ans = []
search.sort(reverse=True)
while search and (search[-1]*2 <= search[0] or search[-1] == search[0]):
    k = search.pop()
    ans.append(k)
    if search and k == search[-1]:
        ans.pop()
    search = [i for i in search if i % k != 0]
ans += search
print(len(ans))

Submission status: Wrong Answer

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

#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
#S = [[0 for j in range(3)] for i in range(2)]
S.sort()
if S[0]==1 and N==1:
    print(1)
    exit()
elif S[0]==1 and S[1]==0:
    print(0)
    exit()
elif S[0]==1:
    print(1)
    exit()


candivcount=0
for i in range(N):
    for j in range(N):
        if i!=j:
            if S[i]<S[j]:
                break
            if S[i]%S[j]==0:
                candivcount+=1
                break

    
print(N-candivcount)

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
h = list(map(int, input().split()))
h.sort(reverse = True)
l = []
for i in range(0, N):
    d = []
    for j in range(0, len(l)):
        if l[j] % h[i] == 0:
            d.append(l[j])
    for k in range(0, len(d)):
        l.remove(d[k])
    l.append(h[i])
if len(collections.Counter(h)) == 1:
    l.clear()
print(len(l))

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]:
  print(0)
  exit()

s = set()
ans = 1
s.add(a[0])
for i in a[1:]:
  p = True
  for j in s:
    if i%j == 0:
      p = False
      break
  if p:
    ans += 1
    s.add(i)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import decimal
import math
import collections
import sys
input = sys.stdin.readline

N=int(input())

ListA=list(map(int,input().split()))
ListA.sort()#reverse=True)

ans=N
rootN=int(math.sqrt(N))
for i in range(N):
    rootA=math.sqrt(ListA[i])
    for j in range(min(i+1,N)):
        if(ListA[i]%ListA[j]==0):
            ans-=1
            break
        if(ListA[j]>rootA):
            break

    
# if(N>=2):
#     if(ListA[2]%ListA[1]==0):
#         ans-=1

print(ans)

Submission status: Wrong Answer

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

A = list(set(A))
A = sorted(A, reverse=True)
num = 0
N = len(A)
for i in range(N):
    flag = True
    for j in range(i+1, N):
        if A[i] % A[j] == 0:
            flag = False
            break
    if flag == True:
        num += 1
if N == 1:
    print(0)
else:
    print(num)

Submission status: Wrong Answer

Solution code:
from math import ceil

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

m = 10**6
n_map = {}
v_a = []
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
v_a = [k for k, v in n_map.items() if v == 1]

v_a.sort()
vv_a = []
nn_map = {}
for i in v_a:
    if i in nn_map:
        continue
    vv_a.append(i)
    for j in range(ceil(m/i)+1):
        nn_map[i*j] = True
print(len(vv_a))