Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

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

a_len = len(a_list)
a_list_sorted = sorted(a_list, reverse=True)
for i in range(a_len):
    target = a_list_sorted[i]
    for j in reversed(range(i+1, a_len)):
        # print('i:{}, j:{}'.format(a_list_sorted[i], a_list_sorted[j]))
        a = a_list_sorted[j]
        if target == a:
            same += 1
        if target % a == 0:
            sum_num += 1
            # print('target:{}, a:{}'.format(target, a))
            break

print(n-sum_num-same)

Submission status: Wrong Answer

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 1:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

import collections





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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
counter = 0
sn_list = sorted(a)
#print(sn_list)
for i in range(n):
  flag = True
  for j in range(i, n):
    if sn_list[j] % sn_list[i] == 0:
      #print(i, j, sn_list[i], sn_list[j])
      flag = False
      break
  if flag:
    #print('*', i, sn_list[i])
    counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
number = input()
line = list(map(int,input().split()))

new_line = list(set(line))
new_line.sort()

#[2, 4, 8, 18, 19, 28, 33, 45, 86, 89]

for num in new_line:
  line2 = []
  for i in range(new_line.index(num)):
    amari = num%new_line[i]
    line2.append(amari)
  if line2 == []:
    x = 0
  elif 0 not in line2:
    x = 2
    x += 1
print(x)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(e) for e in input().split()]

ans = 0
for i in range(n):
    x = n%a[i]
    y = x / a[i]
    if len(str(y)) >= 15:
        ans += 1
    else:
        ans += 0

print(ans)

Submission status: Wrong Answer

Solution code:
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


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

#div = []
div = dict()
temp_dic = dict()
temp = A.pop(0)
temp_ans = [temp]
temp_dic[temp] = 0
ans = 1

for i in A:
  flag = 0
  if is_prime(i):
    if i in temp_dic:
      div[i] = 0
      flag = 1
  else:    
    for j in temp_ans:
      if i == j:
        #div.append(i)
        div[i] = 0
        flag = 1
        break
      if i % j == 0:
        flag = 1
        break
  if flag == 0:
    ans += 1
    temp_ans.append(i)
    temp_dic[i] = 0
#print(ans - len(set(div)))
print(ans - len(div))

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
A = sorted(A,reverse=True)
ans = 0
c = collections.Counter(A)
for i in c.values():
    if i !=1:
        ans -=i


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

Submission status: Wrong Answer

Solution code:
#デフォルト
import itertools
from collections import defaultdict
import collections
import math
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

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

a.sort()
tf = [False] * (10 ** 6 + 1)
ans = 0
if a[0] == 1:
    print("0")
else:
    for i in range(n):
        cnt = a[i]
        cc = 1
        if i != n -1:
            ll = i + 1
        else:
            ll = i - 1
        if not tf[cnt] and a[i] != a[ll]:
            ans += 1
            while cnt * cc <= max(a):
                tf[cnt * cc] = True
                cc += 1

    print(ans)

Submission status: Wrong Answer

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

Is=[]
for i in range(N-1):
  for j in range(i+1,N):
     if A[i]%A[j] != 0:
        if not i in Is:
           Is+=[i]
            
print(len(Is))

Submission status: Wrong Answer

Solution code:
#4問目
import math
N = int(input())
A = list(map(int, input().split()))
count = 0
A = sorted(A, reverse=True)

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:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = list(set(A))
p = 1
count = 0
if A:
    count = 1
    for i in range(1,len(A)):
        if p ==0:
            p = 1
            for j in range(i):
                if A[i]%A[j] == 0:
                    p = 0
                    break

        if p == 1:
            count +=1
print(count)

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:
      continue
      
  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 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 if a[0]==a[1] else 1
  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
        if a[j]>a[i]/2+1:
          break
        if a[i]%3>0 and a[j]>a[i]/3+1:
          break
  print(ans)
if __name__=='__main__':
  main()

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]):
      ok[a[i]*j]=0
    
print(sum(ok))

Submission status: Wrong Answer

Solution code:
import math
n, *a = map(int, open(0).read().split())
a.sort()

divisors = []
isDisible = 0
    
for i in range(n):
    for div in divisors:
        isDisible = 0
        if a[i] % div == 0:
            isDisible = 1
            break
    if isDisible == 0:
        divisors.append(a[i])
ans = len(divisors)
if n >= 2:
    if a[0] == a[1]:
        ans -=1
print(ans)

Submission status: Wrong Answer

Solution code:
N =int(input())
A = list(map(int,input().split()))
c = 0
def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    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 = []  # prime factor
    b, e = 2, 0  # base, exponent
    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

if 1 in A:
    print(N-1)
else:
    for i in A:
        if A.count(i) >= 2:
            c += 1
            continue
        flg=1
        div = []
        fct = factorize(i)
        div += [num(div) for div in divisorize(fct)]
        div = sorted(div)
        for j in div[:-1]:
            if j in A:
                flg = 0
            if flg==0:
                c +=1
                break
    print(N-c)

Submission status: Wrong Answer

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

As.sort(reverse=True)
As = [A for A in As if As.count(A) == 1]

# cnt = len(As)
# for i in range(len(As)-1):
#   for j in range(i+1,len(As)):
#     if As[i] % As[j] == 0:
#       cnt -= 1
#       break

# print(cnt)

Submission status: Wrong Answer

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

a = sorted(a, reverse=True)

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

print(count)

Submission status: Wrong Answer

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

#output
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]

answer = 0
for i in range(N):
    temp_list = make_divisors(A[i])
    temp1 = temp_list[:-1]
    temp2 = temp_list[-1]
    if len(A[A == temp2]) > 1:
        answer += 1
    for t in temp1:
        if t in A:
            answer += 1
            break

print(N - answer)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    a.sort()

    count = 0
    for ite1, i in enumerate(a):
        b = [_ for _ in a if _ < i]
        for ite2, j in enumerate(b):
            if ite1 == ite2: 
                pass
            elif i%j == 0:
                break
            elif ite2 == len(a)-1:
                count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
def func(A, AA, cnt):
    for i in A:
        tmp = i
        tmp1 = 2
        while A[-1] >= tmp:
            tmp =i * tmp1
            tmp1 += 1
            if(tmp in AA):
                cnt -= 1
                AA.remove(tmp)
                
    return cnt    
    
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = set(A)
    A.sort()
    
    if(1 in AA):
        print(1)
    elif(len(AA)==1):
        print(0)
    else:
        print(func(A, AA, len(AA)))
    
main()

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 (not check):
        ans.append(j)
    j += 1

print(len(ans))

Submission status: Wrong Answer

Solution code:
def check(n,p,i):
    b = True
    for j in range(0,len(p)):
        if(j!=i):
            if(p[j]%n==0):
                b = False
    return(b)


def check_main(n,p):
    c = 0
    for i in range(0,len(p)):
        if(check(p[i],p,i)):
            c = c + 1
    return c
    

if __name__ == "__main__":
    N = input()
    numbers = list(map(int,input().split()))
    print(check_main(N,numbers))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
i = 0
ans = 0 
A.sort()
A.reverse()
if A[n-1] == 1:
    if A[n-2] != 1:
        print(1)
        exit()
    else:
        print(0)
        exit()
while i <= n-2:
    for j in range(i+1,n):
        if A[i] % A[j] == 0:
            i = j
            break
        elif j == n - 1:
            ans = ans + 1
    i = i + 1
if A[n-1] == A[n-2]:
    print(ans)
else:
    print(ans+1)

Submission status: Wrong Answer

Solution code:
# D

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

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


ans = 0

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

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

print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(1,N+1):
    for a in A:
        B = []
        B.append(a%i)
        if (a == A[-1]) and B.count(0)==len(A):
            print(i)
print(ans)

Submission status: Wrong Answer

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


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


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

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

    while AArry:
        l1 = len(AArry)
        a = AArry.pop(0)
        if len(AArry) == 0:
            break
        AArry = [e for e in AArry if e % a == 0]
        l2 = len(AArry)
        count += (l1-l2)

    print(N-count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = np.array(sorted(list(map(int, input().split()))))
ans = 0
idx = 0
while True:
  try:
    a = A[idx]
  except:
    break

  A = A[A>a][np.where(A[A>a] % a != 0)]
  ans +=1
print(ans)

Submission status: Wrong Answer

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

A = sorted(A, reverse = True)
ans = 0

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

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

print(ans)

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
    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:
from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
B=A[::-1]
ans=0
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:
N = int(input())
A = list(map(int, input().split()))

A.sort()
# print(A)
count = 0

judge = True
i = 0
while(judge):
    place = A.index(A[i])
    tmp = A[i]
    A = [x for x in A if x % A[i] != 0]
    A.insert(place, tmp)
    N = len(A)
    # print(A)
    # print(N)
    if len(A) < i:
        i += 1
    else:
        judge = False

print(N)
# for i in range(0, N-1):




#     flag = 0
#     j_list = list(range(N))
#     j_list.pop(i)
#     for j in j_list:
#         if (A[i] % A[j] == 0):
#             flag = 1
#             break
#     if flag == 0:
#         count += 1

# print(count)

Submission status: Wrong Answer

Solution code:
from decimal import Decimal
from collections import Counter

N = int(input())
A = sorted([int(_) for _ in input().split()])
max_a = max(A)
min_a = min(A)
counter_A = Counter(A)
set_A = set([k for k, c in counter_A.items() if c == 1])

for a in A:
  if a not in set_A:
    continue
  i = 2
  while True:
    num = a * i
    if num > max_a:
      break
    if num in set_A:
      set_A.remove(num)
    i += 1

print(len(set_A))

Submission status: Wrong Answer

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

dic={}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]]=1
    else:
        dic[A[i]]+=1

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

if 1 in dic:
    if dic[1]>1:
        print(0)
        exit()
    else:
        print(1)
        exit()

ans=0
minn=min(A)
for i in range(N):
    if dic[A[i]]>1:
        continue
    if minn<A[i] and A[i]<minn*2:
        continue
    f=False
    for j in range(2, int(A[i]**0.5)+1):
        if A[i]%j==0:
            if j in dic or A[i]//j in dic:
                f=True
                break
    if f:
        continue
    ans+=1

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:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    nums = []

    A.sort()

    while A:
        head = A[0]
        if len(A) >=2 and head == A[1]:
            while head in A: A.remove(head)
            continue

        flag = True

        for num in nums:
            if head % num == 0:
                flag = False
                break
            if num ** 2 > head: break

        if flag == True:
            nums.append(head)

        A.remove(head)

    print(len(nums))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

A = sorted(A, reverse=True)
B = sorted(A)
answer = 0
c = Counter(A)

for i, Anumber in enumerate(A):
    if c[Anumber] > 1:
        break
    for k, Bnumber in enumerate(B):

        if i == N - 1 - k:
            answer = answer + 1
            break
        if Anumber % Bnumber == 0:
            break

print(answer)

Submission status: Wrong Answer

Solution code:
n=int(input())
a_list=[int(i) for i in input().split()]
print(a_list)

sum=0    
for i in a_list:
    for j in a_list:
        if i%j==0:
            print(i,j)
            break
        else:
            print(i,j)
            sum+=1
sum-=n
print(sum)

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

    d = dict()
    for x in A:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    A = set()

    ans = 0
    while(A):

        x = min(A)
        if d[x] == 1:
            ans += 1
        next = set()
        for y in A:
            if y % x != 0:
                next.add(y)
        A = set()
        A |= next

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array([int(x) for x in input().split()]))[::-1]

count = 0
if not np.all(a == a[0]):
    for index,i in enumerate(a):
        a_i = i%a[index:]
        if np.count_nonzero(a_i == 0)==1:
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def make_divisors(n: int) -> list:
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if i == 1:
            continue
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

def main():
    n = i_input()
    num_list = i_list()

    if num_list.count(1) >= 1:
        print(0)
        exit()

    num_list.sort()
    num_list = set(num_list)

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



    count = 0

    for num in num_list:
        yakusu_list = make_divisors(num)
        # if len(yakusu_list) == 0:
        #     count += 1
        #     continue
        # print(num, yakusu_list)
        for yakusu in yakusu_list:
            if yakusu in num_list:
                count += 1
                break

    print(n - count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    import bisect
    n = int(input())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A.sort()

    ans = 0
    a_max = A[-1]
    note = [True]*(a_max+1)
    for a in A:
        if note[a]:
            for i in range(a,a_max+1):
                if i%a==0:
                    note[i] = False
            ans+=1

        
    
    print(ans)
main()

Submission status: Wrong Answer

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

    sum=n

    for i in range(n):      
        for j in range(0,n-1-i):
            if a[i]%a[n-1-j]==0:
               
                sum-=1
                break                
            if a[i]<2*a[n-1-j]:
                break
    if n!=1:
        if a[n-1]==a[n-2]:
            sum-=1

            

                
        


    print(sum)
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
from itertools import combinations

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
pen = 0
nex = n-1
count = 2
ans = 0
com = list(combinations(a,2))

for i in range(len(com)):
    pen -= 1

    if com[i][0]%com[i][1] == 0 and pen < 1:
        ans += 1
        pen = nex

    nex -= 1
    if nex < 1:
        nex = n-count
        count += 1

print(n-ans)

Submission status: Wrong Answer

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

A.sort()
ans_list=[]
for i in range(N):
  for j in range(i+1,N):
    if A[i]<=math.sqrt(A[j]):
      temp=math.gcd(A[i],A[j])
      if A[i]==temp:
        ans_list.append(j)  
    elif A[i]==A[j]:
      ans_list.append(i)
      ans_list.append(j)
    else:
      break
      

print(N-len(set(ans_list)))
#print(gcd_list)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())
A.sort()

visit=defaultdict(lambda: 0)

#約数列挙
def make_divisors(n):
    divisors=[]
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            if visit[i]==1:
                return True
            if i!=n/i:
                if visit[n/i]==1:
                    return True
    return False

ans=0
for a in A:
    if make_divisors(a) is False:
        ans+=1
    visit[a]=1
print ans

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()])
A = np.sort(A)
if(sum(A%A[0])==0):
  print(0)
  sys.exit()
n = 1
for i in range(1,N):
  l = 0
  for j in range(i):
    if((A[i] % A[j]) == 0):
      break
    l += 1
     
  if(l == i):
    n += 1
print(n)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

# エラトステネスの篩っぽく処理
ans_list = []
ans = 0

# ダブリを省くために先に数える
c = Counter(search_list)
original = [x for x in c.keys() if c[x] == 1]

tmp = min(search_list)

while tmp <= max(search_list)/2:
    if tmp in original:
        ans_list.append(tmp)
    search_list = [i for i in search_list if i % tmp != 0]
    if len(search_list) == 0:
        break
    else:
        tmp = min(search_list)

ans = len(ans_list) + len(search_list)
print(ans)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    if n < 1:
        return
    i = 1
    while i * i <= n:
        if n % i == 0:
            yield i
            if i * i != n:
                yield round(n / i)
        i = i + 1
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * n
for i, num in enumerate(a):
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        flag[i] = False
        continue
    div = make_divisors(num)
    for d in div:
        if d == num:
            continue
        if d in a:
            flag[i] = False
counter = 0
for i in range(len(flag)):
    if flag[i]:
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
import random

N = int(input())
# = map(int, input().split())
A = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]

A = list(sorted(set(A)))
mark = []

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True



for i in range(len(A)):
    if is_prime3(A[i]):
        mark.append(A[i])

for i in range(len(mark)):
    count = 0
    for j in range(len(A)):
        if A[j]%mark[i] == 0:
            A[j] = 0
            count += 1
    for k in range(count):
        A.remove(0)

for i in range(len(A)):
    length = len(A)
    count = 0
    if i >= length:
        break
    else:
        for j in range(i+1, length):
            if A[j]%A[i] == 0:
                A[j] = 0
                count += 1
        for k in range(count):
            A.remove(0)

answer = len(mark) + len(A)


if answer == 1:
    print(0)

else:
    print(answer)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import itertools
import array
import textwrap


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()))
s = [1 for i in range(N)]
d = dict(zip(A, s))
# print(d)
cnt = 0
temp = 0
temp2 = 0
for i in A:
    d[i] = d.get(i)-1
    # print(d)
    temp = i
    arr = factorization(i)
    temp2 = cnt
    for k in arr:
        # if temp2 != cnt:
        #     break
        # print(k, arr, arr[-1])
        for j in range(1, k[1]+1):
            # print(k[0])
            tmp = k[0]**j
            # if tmp == temp:
            #     break
            # print(i, d.get(tmp, 0))
            if d.get(tmp, 0) == 1:
                temp2 = 1
                break
            # print(tmp, k, arr, arr[-1])
            if j == k[1] and k == arr[-1]:
                # print(i)
                cnt += 1
                # print(i)
        if temp2 == 1:
            temp2 = 0
            break
    d[i] = d.get(i)+1
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np


N = int(input())
A = list(map(int, input().split()))
A_sorted = sorted(A)
ans = 0
for i in A_sorted:
    np_list = np.array(A_sorted)
    if (np_list - i).sum() == 0:
        break
    idx = np.where((np_list % i) == 0)[0]
    for yo, j in enumerate(idx[1:]):
        del A_sorted[j - yo]
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
def find_i(i, bools, N):
    for j in range(i+1, N):
        if bools[j] == True:
            return j
    return N
from collections import Counter
def Main(N, A):
    c = Counter(A)
    if len(c) == 1:
        return 0
    A.sort()
    bools = [True]*N
    i = 0
    j = 0
    while i < N:
        j = find_i(i, bools, N)
        while j < N:
            if A[j]%A[i] == 0:
                bools[j] = False
            j = find_i(j, bools, N)
        i = find_i(i, bools, N)
    return bools.count(True)

print(Main(N, A))