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: Runtime Error

Solution code:
#include <iostream> 
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int N; cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  sort(A.begin(), A.end(), greater<int>());

  int ans = 0;

  int i = 0;
  while (true) {
    if (i == N) break;
    bool condition = true;
    for (int j = N - 1; j > i; j--) {
      if (A[i] % A[j] == 0) {
        condition = false;
        break; 
      }
    }
    if (condition) {
      ans++;
      i++;
    }
    else {
      A.erase(A.begin() + i);
      N--;
    }
  } 


  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
@njit
def main():
    N = int(input())
    An = list(map(int, input().split()))
    ans = 0
    ng = set()
    a_An = np.array(An)
    for i, a in enumerate(An):
        temp = a_An / a
        temp[i] = 0.1
        check = np.where(temp % 1 == 0)
        check = check[0]
        # check = np.delete(check, np.where(check == i))
        # check = check[check != i]
        if len(check) > 0:
            ng = ng | set(check)
    print(N-len(ng))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

num=0
for i in range(len(l)-1):
    for d in l[i+1:]:
        if (l[i]/d).is_integer():
            num += 1
            break
if l[-2]==l[-1]:
    num += 1
print(len(l)-num)

Submission status: Runtime Error

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

A = list(set(A))
num = 0
for i in range(N):
    flag = True
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            flag = False
            break
    if flag == True:
        num += 1
print(num)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
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]
ans = 0
if a[-2] == a[-1]:
  ans -= 1
for i, num in enumerate(a):
  b = make_divisors(num)
  if set(a[i+1:]).isdisjoint(set(b)):
    ans += 1
print(ans)

Submission status: Runtime Error

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

A.sort()
C=[]
total = 0
for i in A:
    B =[]
    for n in range(1,len(A)):
        if A[n] % i !=0:
            B.append(A[n])
    if A[0] != A[1]:
        C.append(A[0])
    #print(B)
    A = B
    if len(A)==0:
        break
    Al = max(A)
    if A[0] == Al:
        C.append(B)
        break
#print(C)
if len(C)>0:
    print(len(C))
else:
    print(0)

Submission status: Runtime Error

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

a=sorted(a)
cnt=0
for i in range(n):
    if i == 0:
        if a[i] == a[i+1]:
            cnt+=1
        continue
    for j in range(i):
        if i == j:
            continue
        else:
            if (a[i]%a[j])==0:
                cnt+=1
                break
ans=n-cnt
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    l = sorted([int(i) for i in input().strip().split()])
    for i, n in enumerate(l[:-1]):
        flag = False
        if not n:
            continue
        for j, m in enumerate(l[i + 1:]):
            if not m:
                continue
            if m == n:
                flag = True
            if m % n == 0:
                l[i + j + 1] = None
        if flag:
            l[i] = None
    l = set(l)
    l.remove(None)
    ans = len(set(l))

    return ans


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

Submission status: Runtime Error

Solution code:
from bisect import bisect

def main():
    N = int(input())
    l = [int(x) for x in input().split()]
    
    count=0
    l = sorted(l)
    #print(l)
    for i in range(1,N)[::-1]:
     #   print("i",i)
        idx = bisect(l,l[i]//2+1)
      #  print("idx",idx)
        for j in range(idx+1):
            if l[i]%l[j]==0:
                break
        else:
            count+=1
       #     print(1)
    if l[0]!=l[1]:
        count+=1
    print(count)
    
main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = Counter(A)
    A.sort()
    ans = set()
    table = {i:-1 for i in range(1, 10 ** 6 + 1)}
    for a in A:
        table[a] = 0
    for a in A:
        if table[a] == 0 and cnt[a] == 1:
            ans.add(a)
        elif table[a] == 1:
            continue
        i = 2
        target = a
        while True:
            target = a * i
            if table[target] == 0:
                table[target] = 1
            i += 1
            if target >= A[-1]:
                break
    print(len(ans))
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
P = [int(x) for x in input().split()]
P.sort()
a = 0
b = 1
A = []
for i in range(N):
    if P[0] != P[1]:
        A.append(P[0])
    for j in range(1,len(P)-1):
        if P[b]%P[0] == 0:
            P.pop(b)
        else:
            b+=1

    P.pop(0)
    if len(P) == 0:
        break
    elif len(P) == 1:
        A.append(P[0])
        break
    b = 1

print(len(A))

Submission status: Runtime Error

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
 
    # divisors.sort()
    return divisors
 
fact = set()
 
A.sort()
ans = 0
for i in A:
    div = make_divisors(i)
    if len(fact & div) != 0:
        fact.add(i)
        
    else:
        ans += 1
        fact.add(i)
if A[0] == A[1]:
    ans -= 1
        
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin

A = int(stdin.readline())
B = list(map(int,stdin.readline().split()))
B.sort()
count=0
T=0

if B.count(1)>0:
    if B.count(1)>1:
        print(0)
    elif B.count(1)==1:
        print(1)
    B=[]
    T=1


while len(B)>0:
    if len(B)==1:
        if Q==0:
           count+=1
        break
    K=B[0]
    B.remove(B[0])

    Q=0
    D=B.copy()
    for t in D:

        if t==K:
            Q=1
        if t%K==0:
            B.remove(t)

    if Q==0:
       count+=1

if T==0:
   print(count)

Submission status: Runtime Error

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

import sympy

ans = 0
temp = [0]*(10**6+3)
temp[A[0]] += 1
if A[0]!=A[1]:
    ans += 1


for i in range(1,N):
    check = 0
    temp1 = sympy.divisors(A[i])
    for j in temp1:
        if temp[j]!=0:
            check += 1
            break

    if check == 0:
        ans += 1
        temp[A[i]]+=1
        
if A[0]==1:
    if A[1]==1:
        print(0)
    else:
        print(1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
for a in range(N):
  newA = [A[a]%n for n in A]
  newA.pop(a)
  print(newA)
  if 0 in newA:
    ans = ans
  else:
    ans += 1
  
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
"""D問題"""
from collections import defaultdict
import sympy
N = int(input())

def divisor(n): #nの約数を全て求める
  i = 1
  table = []
  while i * i <= n:
    if n%i == 0:
      table.append(i)
      table.append(n//i)
    i += 1
  table = set(table)
  return table

A = list(map(int, input().split()))
A.sort()
dic = defaultdict(int)
for a in A:
  dic[a] += 1
A = set(A)

for a in A:
  if a == 1:
    print(0)
    exit()
B = {}
for a in A:
  B[a] = set(sympy.divisors(a))

s = set()
ans = 0

for a in A:
  s = A - set([a])
  if len(s) == 0:
    continue
  if len(B[a] & s) == 0:
    if dic[a] == 1:
      ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
arr = list(map(int, input().split()))
for i in range(n):
    for j in range(n):
        if i != j and arr[i]%arr[j] != 0:
            c += 1
    if c == (n-1):
        d += 1
print(d)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

# 実行環境(0:vscode, 1:atcoder)
MODE = 1

# 入力の次元
DIMENSION = 2

# int型に変換
INT_TYPE = 1

if not (MODE):
    with open("input.txt", "r") as f:
        s = f.read()
else:
    s = sys.stdin.read()

if DIMENSION == 0:
    if INT_TYPE == 1:
        s = int(s)
elif DIMENSION == 1:
    if INT_TYPE == 0:
        s = s.split()
    elif INT_TYPE == 1:
        s = [int(x) for x in s.split()]
elif DIMENSION == 2:
    if INT_TYPE == 0:
        s = [x.split() for x in s.splitlines()]
    elif INT_TYPE == 1:
        s = [[int(y) for y in x.split()] for x in s.splitlines()]

N = s[0][0]
A = s[1]
A = sorted(A)

# cnt = 0
#
# for i in range(N):
#     sw = 0
#     if i < N - 1:
#         if A[i] != A[i + 1]:
#             for j in range(i):
#                 if A[i] % A[j] == 0:
#                     sw = 1
#                     break
#             if sw == 0:
#                 cnt += 1
#     else:
#         for j in range(i):
#             if A[i] % A[j] == 0:
#                 sw = 1
#                 break
#         if sw == 0:
#             cnt += 1


# print(cnt)

A = np.asarray(A)
B = np.tile(A, (N, 1))
C = A[..., np.newaxis]
D = B % C == 0
E = np.count_nonzero(D == True, axis=0)
print(np.count_nonzero(E == 1))

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split(' ')))
A.sort()
l=0
for i in range(len(A)-1):
    if A[i]==A[i+1] and A[i-1]!=A[i]:
        l=l-1
    k=True
    for j in range(i):
        if A[i]%A[j]==0:
            k=False
            continue
    if k:
        l=l+1
if A[0]==A[1]:
    l=l-1
k=True
for j in range(len(A)-1):
    if A[-1]%A[j]==0:
        k=False
        continue
if k:
        l=l+1
print(l)

Submission status: Runtime Error

Solution code:
import sympy

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

count = 0
for i in range(len(A)):
    flag = False
    for div in sympy.divisors(A[i]):
        if div <= 1:
            continue
        if div == A[i]:
            if div in A[:i]:
                flag = True
                break
            if div in A[i+1:]:
                flag = True
                break
        else:
            if div in setA:
                flag = True
                break
    if not flag:
        count += 1

print(count)

Submission status: Runtime Error

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

num=0
for i in range(len(l)-1):
    for d in l[i+1:]:
        if (l[i]/d).is_integer():
            num += 1
            break
if l[-2]==l[-1]:
    num += 1
print(len(l)-num)

Submission status: Runtime Error

Solution code:
n = int(input())
arr = list(map(int, input().split()))
for i in range(n):
	for j in range(n):
		if i != j and arr[i]%arr[j] != 0:
			c += 1
    if c == (n-1):
		d += 1
print(d)

Submission status: Runtime Error

Solution code:
def D():
    n = int(input())
    a = list(map(int, input().split()))
    b = [x for x in set(a) if a.count(x) < 2]
    b.sort()
    if len(b) == 0:
        print(0)
        return
    prime = [b[0]]
    for i in range(1,n):
        flg = False
        for p in prime:
            flg = True
            if b[i] % p == 0:
                flg = False
                break
        if flg:
            prime.append(b[i])
    print(len(prime))
D()

Submission status: Runtime Error

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

S = sorted(set(A))

ans = 0
n = len(S)
if n == 1:
    ans = 0
else:
    ans = 1
    for i in range(1, N):
        j = 0
        while S[i] % S[j] > 0:
            j += 1
            if i <= j:
                ans += 1
                break
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    from collections import Counter
    n= int(input())
    inlis = list(map(int, input().split()))
    inlis.sort()
    counter = Counter(inlis).most_common()
    inset = set()

    for countset in counter:
        if countset[1] == 1:
            inset.add(countset[0])
    
    for num in inset:
    new = [e for e in inset if e % num == 0]
    new.sort()
    #print(new)
    if len(new) > 1:
        if new[0] != new[1]:
            for i in range(1, len(new)):
                inset.remove(new[i])
        else:
            for i in range(0, len(new)):
                inset.remove(new[i])
            

    print(len(inset))



    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[0]*2*10**5
ans=[]
for i in a:
    f=True
    if i==2 or i==3:
        ans.append(i)
        b[i]=1
        continue
    if b[i]==1:
        if ans:
            ans.remove(i)
        continue
    for j in range(2,i):
        if i%j==0 and b[j]==1:
            f=False
            break
    if f:
        b[i]=1
        ans.append(i)

print(len(ans))

Submission status: Runtime Error

Solution code:
import math
import numpy as np

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

gcd_list=np.zeros((N,N),dtype="int64")
for i in range(N):
  for j in range(i+1,N):
    temp_gcd=math.gcd(A[i], A[j])
    if A[i]==temp_gcd:
      gcd_list[j][i]=1
    if A[j]==temp_gcd:
      gcd_list[i][j]=1
      
ans=0
for i in range(N):
  if (gcd_list[i]==0).all()==True:
    ans+=1
    #print(i)
print(ans)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
cnt=0
sqN=math.ceil(math.sqrt(N))
for i in A:
  num=A.index(i)+1
  for j in range(num,sqN+1):
    if  math.gcd(i,A[j])==min(i,A[j]):
      cnt+=1
      break
ans=N-cnt
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
ans = 0
import heapq
heapq.heapify(A)
while A != []:
    a = heapq.heappop(A)
    ans += 1
    AA = []
    if A[0] == a:
        ans -= 1
    for i in range(len(A)):
        if not (A[i] % a == 0):
            AA.append(A[i])
    A = AA
print(ans)

Submission status: Runtime Error

Solution code:

import math
N = a=int(input())
listP=[]
while True:
    try:
        listP=list(map(int,input().split()))
    except:
        break;
listP.sort()
#print(N,listP)
counter=0
for i in range(len(listP)):
  for j in range(math.floor(math.sqrt(max(listP)+1))):
    if i!=j and listP[i]%listP[j]==0:
      counter+=1
      break

print(len(listP)-counter)

Submission status: Runtime Error

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 and b[i]!=b[t]:
            d+=1
        else:
            t+=1
print(n-ct)

Submission status: Runtime Error

Solution code:
n=int(input())
A=sorted(map(int,input().split()))
L=[A[0]]

c=0
if A[0]!=A[1]:
    c=1
for i in range(n-1):
    flag=0
    for l in L:
        if A[i+1]%l==0:
            flag=1
            break
    L.append(A[i+1])
    if flag==0:
        c+=1
print(c)

Submission status: Runtime Error

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
num=[A[0]]
if A[0]==A[1]:
    flag=1
else:
    flag=0
    
for i in range(1,n):
    a=A[i]
    for k in num:
        if a%k==0:
            break

    num.append(a)
    if a==A[i+1]:
        flag+=1
ans=len(num)-flag
print(ans)

Submission status: Runtime Error

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

a.sort()
#print(a)

ans = 0
div = []
if a[0] == a[1]:
    pass
else:
    ans += 1

div.append(a[0])

for i in range(1, n-1):
    if a[i] == a[i-1]:
        pass
    elif a[i] == a[i+1]:
        div.append(a[i])
    else:
        flg = True
        for j in div:
            if a[i] % j == 0:
                flg = False
                break
        if flg:
            div.append(a[i])
            ans += 1
    #print(i, a[i], div, ans)

if a[n-2] == a[n-1]:
    pass
else:
    flg = True
    for j in div:
        if a[n-1] % j == 0:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
from collections import defaultdict
from bisect import bisect_left


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    is_prime = [True for i in range(n+1)]
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return primes


def solve(N, A, AMAX=10**3):
    A.sort()
    primes = sieve(AMAX)
    P = len(primes)
    table = [[False for i in range(P)] for j in range(N)]
    L = [[False for i in range(P)] for j in range(N+1)]
    for i in range(N):
        a = A[i]
        for j in range(P):
            p = primes[j]
            if p * p > a:
                break
            while a % p == 0:
                table[i][j] = True
                a //= p
        if a > 1:
            idx = bisect_left(primes, a)
            table[i][idx] = True
    for i in range(N):
        for j in range(P):
            L[i+1][j] = L[i][j] ^ table[i][j]

    ans = 0
    A.append(A[-1])
    for i in range(N):
        not_div = True
        if A[i] == A[i+1]:
            continue
        for j in range(P):
            if table[i][j] and (i > 0 and L[i-1][j]):
                not_div = False
                break
        if not_div:
            ans += 1
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Runtime Error

Solution code:
from collections import Counter

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: # choufuku
                divisors.append(n//i)
    # divisors.sort()
    return divisors


exists = [False] * (2 * (10 ** 5) + 1)

input = raw_input
n0 = int(input())
As_0 = map(int, input().split(" "))

counter = Counter(As_0)
As = counter.keys()
#n = len(As)

out = 0

for A in As:
    exists[A] = True

#for i in range(n):
#    A1 = As[i]
#    num = counter[A1]
for A1, num in counter.items():

    if num >= 2:
        continue
    
    exist = False

    ds = make_divisors(A1)
    for d in ds:
        if exists[d]:
            if d != A1:
                exist = True

    if not exist:
        out += 1

print(out)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = Counter(A)
    A.sort()
    ans = set()
    table = {i:-1 for i in range(10 ** 6 + 1)}
    for a in A:
        table[a] = 0
    for a in A:
        if table[a] == 0 and cnt[a] == 1:
            ans.add(a)
        elif table[a] == 1:
            continue
        i = 2
        target = a
        while True:
            target = a * i
            if table[target] == 0:
                table[target] = 1
            i += 1
            if target >= A[-1]:
                break
    print(len(ans))
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int , input().split()))
sa = set()
for ai in a:
    if ai in sa:
        sa.discard(ai)
        continue
    sa.add(ai)

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

a = list(sa)
a.sort()

#print(a)

import fractions
def lcm(a, b):
    return a * b // fractions.gcd(a, b)

ans = 1
l = 1
for i in range(n):
    if lcm(a[i], l) < a[i] * l:
        continue
    l = lcm(a[i], l)
    ans += 1
print(ans, l)

Submission status: Runtime Error

Solution code:
N = int(input())
num_list = list(map(int, input().split()))
count=0
num_list = list(set(num_list))
if len(num_list) == 0:
  print(0)
  
else:
  for i in range(N):
    for j in range(N):
      if i != j:
        if num_list[i] % num_list[j]==0:
          count = count+1
        
  if count != 0:
    print(count)
  else:
    print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N=int(input())
A=set(map(int,input().split()))
A=list(A)
st=sorted(A)
cnt=0
if len(A)==1:
    print(0)
    exit()
for i in range(0,N):
    res=0
    for j in range(i):
        if st[i]%st[j]==0:
            res=1
            break
    if res==0:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
x_list = np.repeat(list(map(int, input().split())), N).reshape(N,N)

print(np.sum(np.sum(x_list%x_list[:,0]==0, axis=1)==1))

Submission status: Runtime Error

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

count = 0

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

print(count)

Submission status: Runtime Error

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc170/abc170_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = sorted(int(c) for c in i2s().split(' '))
    max_ = A[-1]
    B = {}
    for i in range(N):
        if i == 0:
            if A[i] == A[i+1]:
                continue
        elif i == N - 1:
            if A[i] == A[i-1]:
                continue
        elif A[i-1] == A[i] or A[i+1] == A[i]:
            continue
        B[A[i]] = True
    for b in B:
        if not B[b]:
            continue
        for i in range(2, max_ // b + 1):
            if b * i in B:
                B[b * i] = False
    res = 0
    for v in B.values():
        if v:
            res += 1
    print(res)
    return

main()

Submission status: Runtime Error

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

N=int(input())
A=list(map(int,(input().split())))
new_A=list(set(A))
tmp_A = copy.copy(new_A)
count=0

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

Submission status: Runtime Error

Solution code:
n = int(input())
arr = list(map(int, input().split()))
for i in range(n):
  for j in range(n):
    if i != j and arr[i]%arr[j] != 0:
      c += 1
	if c == (n-1):
      d += 1
print(d)

Submission status: Runtime Error

Solution code:
N = int(input())
num_list = list(map(int, input().split()))
count=0
num_list = list(set(num_list))
if len(num_list) == 0:
  print(0)
  
else:
  for i in range(N):
    for j in range(N)
    if i != j:
      if num_list[i] % num_list[j]==0:
        count = count+1
        
  if count != 0:
    print(count)
  else:
    print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

ans=0

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

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

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int, input().split(" "))))
idx = 0
while True:
    removes = []
    v = a[idx]
    for target in a:
        if target % v == 0:
            removes.append(target)
    removes.remove(v)
    if removes:
        if removes[0] == v:
            removes.append(v)
        for target in removes:
            a.remove(target)
    if len(a) == 0 or a[-1] == v:
        break
    idx += 1
print(len(a))

Submission status: Runtime Error

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

A.sort()
ans=N
i=0
while i<len(A):
    if i==0 and A[i]==A[i+1]:
        ans-=1
        i+=1
        continue
    for a in A[:i]:
        if A[i]%a==0:
            ans-=1
            A=A[:i]+A[i+1:]
            i-=1
            break
    i+=1

print(ans)

Submission status: Runtime Error

Solution code:
import sympy

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

cnt = [0] * 1000001

for i in range(n):
    cnt[p[i]] += 1

p = sorted(p, reverse=True)

ans = n

for i in range(n):
    c = sympy.divisors(p[i])
    for j in range(len(c)):
        if (not (c[j] == p[i]) or cnt[c[j]]>1) and cnt[c[j]]:
            ans -= 1
            break
print(ans)

Submission status: Runtime Error

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

list.sort(A)
count=0
if A[0]==A[1]:
    count-=1
for i in range(0,N):
    switch=0
    for j in range(0,i):
        if A[i]%A[j]==0:
            switch=1

    if switch==0:
        count+=1

print(count)

Submission status: Runtime Error

Solution code:


import collections
import math

def get_sieve_of_eratosthenes_new(data):
    prime = []
    limit = math.sqrt(max(data))
    # 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]
    return data


def main():
    n = int(input())
    al = list(map(int, input().split()))
    al_not_multi = []
    cnt = collections.Counter(al)
    for i,v in cnt.items():
        if v == 1:
            al_not_multi.append(i)

    if not al_not_multi:
        print(0)
        return

    al_not_multi.sort()
    ans = get_sieve_of_eratosthenes_new(al_not_multi)
    print(len(ans))

    # ans = 0
    # while al_not_multi:
    #     p = al_not_multi[0]
    #     al_not_multi = [e for e in al_not_multi[1:] if e % p != 0]
    #     ans += 1


    # al_n = al_not_multi[:]
    # ans = 0
    # while al_n:
    #     new_al_n = []
    #     start = al_n[0]
    #     for a in al_n[1:]:
    #         if a%start!=0:
    #             new_al_n.append(a)
    #     al_n = new_al_n[:]
    #     ans += 1
    # print(ans)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
n, *a = map(int, open(0).read().split())
a.sort()
cnt = n
if a[1] == a[0]:
    cnt -= 1
    
def make_divisors(n,th):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n and i <= th:
        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]
    
for i in range(n):
    divisors = make_divisors(a[i], a[i-1])
    
    for div in divisors:
        if div in a[:i]:
            cnt -= 1
            break

print(max(cnt,0))

Submission status: Runtime Error

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

A.sort()
if A[0] == A[1]:
    cnt = N-1
else:
    cnt = N

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

print(cnt)

Submission status: Runtime Error

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

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

a = sorted(a)
ads = [0]*(2*10**5)

ans = 0
dups = []
for ai in a:
    ds = make_divisors(ai)
    ok = True
    if ads[ai]:
        if ai not in dups:
            dups.append(ai)
        continue
    for d in ds:
        if ads[d]:
            ok = False
            break
    if ok:
        ads[ai] = 1
        ans += 1

print(ans - len(dups))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
x_list = np.repeat(list(map(int, input().split())), N).reshape(N,N)

print(np.sum(np.sum(x_list%x_list[:,0]==0, axis=1)==1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = set()
if len(set(a)) != n:
    print(0)
    exit()
a.sort()
cnt = 0
flg = True

for i in a:
    flg = True
    l = make_divisors(i)
    for num in l:
        if num in b:
            flg = False
            break
    if flg == True:
        cnt += 1
    b.add(i)


print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
an =[]
for i in range(n):
  if i == 0:
    if not a[i]==a[i+1]:
      an.append(a[i])
  else:
    s=0
    for j in range(i):
      if a[i]%a[j]==0:
        s =1
    if s==0:
      an.append(a[i])
print(len(an))