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:
# coding: utf-8
N = int(input())
li = [True for _ in range(0, 2*10**5 + 1)]
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N):
    if li[A[i]]:
        ans += 1
    for j in range(A[i], 2*10**5 + 1, A[i]):
        li[j] = False
ans -= len(A) - len(set(A))
print(max(0, ans))

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
a = list(map(int, input().split()))
D = dict(Counter(a))
E = []
for key in D.keys():
    if D[key] == 1:
        E.append(key)

E = set(E)

for d in a:
    for j in range(2, max(E)//d+3):
        if d*j in E:
            E.remove(j*d)
print(len(E))

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())))
b = []
if a[0] != a[1]:
    b += [a[0]]
for i in range(1, n-1):
    if a[i-1] != a[i] and a[i] != a[i+1]:
        b += [a[i]]
if a[-1] != a[-2]:
    b += [a[-1]]

if len(b) == 0:
    print(0)
    exit()
ans = 1
div = [b[0]]
for x in b[1:]:
    f = True
    for d in div:
        if x % d == 0:
            f = False
            break
    if f:
        div += [x]
        ans += 1
print(ans)

Submission status: Runtime Error

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

A.sort()
result = 0
for i in range(N):
    for j in range(i):
        count += 1
        if A[i] % A[j] == 0:
            break
    else:
        result += 1
print(result)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[1]*(2*10**6)
c=0
for i in range(n):
    j=a[i]
    while j<19*10**5:
        b[j+a[i]]=0
        j+=a[i]
a.sort()
if a==[a[0]]*n:
    c-=1
for i in range(n-1):
    if a[i]==a[i+1]:
        c-=1
        f=1
        if f==0:
            c-=1
    else:
        f=0
for i in range(n):
    c+=b[a[i]]
print(c)

Submission status: Runtime Error

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

x = [0] * (10 ** 6 + 1)
for a in A :
  x[a] += 1
  if x[a] == 2 :
    x[a] = 100000000
  
for i in range(10 ** 6 + 1) :
  if not x[i] : continue
  j = i * 2
  while j <= 10 ** 6 + 1 :
    x[j] = False
    j += i

print(x.count(1))

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int,input().split()))
a.sort()
res = 1
divisors = [a[0]]
if a[0]==a[1]:
    if a[0]==1:
        print(0)
        exit()
    else:
        res = 0
for tgt in a[1:]:
    flg = 1
    for dv in divisors:
        if tgt%dv==0:
            flg = 0
            break
    if flg==1:
        res += 1
        divisors.append(tgt)
print(res)

Submission status: Runtime Error

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

ok = [True]*100005

a.sort()
ans=0
for i in range(n):
    if i<n-1 and a[i]!=a[i+1] and ok[a[i]]:
        ans+=1
    elif i==n-1 and ok[a[i]]:
        ans+=1
    if ok[a[i]]:
        for j in range(a[i],100004,a[i]):
            ok[j]=False

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))+[10**7]
a.sort()
e = np.zeros(2*10**5+1)
ans = 0
for i in range(n):
    if e[a[i]] == 0 and a[i] != a[i+1]:
        ans += 1
    e[::a[i]] = 1
print(ans)

Submission status: Runtime Error

Solution code:
X,N = map(int,input().split())
if N>0:
    p_set = set(map(int,input().split()))
else:
    p_set = set()
min_dist_xp = 1000
for p in reversed(range(0,102)):
    if p not in p_set:
        dist_xp = abs(X-p)
        if dist_xp<=min_dist_xp:
            min_dist_xp = dist_xp
            ans = p
print(ans)

Submission status: Runtime Error

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

nums.sort()

ans_list = [nums[0]]

for i in range(n):
    valid = True
    for j in range(len(ans_list)):
        if nums[i] % ans_list[j] == 0:
            # 割り切れた
            valid = False
            break
    if valid:
        ans_list.append(nums[i])
    
# nums[0] = num[1] の場合は0を減らす：
ans = len(ans_list)
if nums[0] == nums[1] :
    ans -= 1

print(ans)

Submission status: Runtime Error

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

al.sort()
table = [False]*100001
table2 = [False]*100001

for a in al:
    if table2[a]:
        table[a]=True
    if not table[a]:
        table2[a] = True
        for i in range(a+a,100000,a):
            table[i]=True
    

cnt=0
for a in al:
    if not table[a]:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

const int limit = 1e6;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    vector<bool> ng(limit+1, false);
    for(int i=0; i<n-1; i++){
        if(a[i] == a[i+1]){
            ng[a[i]] = true;
        }
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    
    int ans = 0;
    for(int i: a){
        if(!ng[i]) ans++;
        for(int j=i; j<=limit; j+=i){
            ng[j] = true;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

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

M = 10**6+1
L = [0]*M

for a in A:
    if L[a] >= 1:
        L[a] = 2
        continue
    L[a] = 1
    i = 2
    while a*i <= M:
        L[a*i] = 2
        i += 1

ans = 0
for a in A:
    if L[a] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

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

l = [0] * 1000001

ans = 0

for i in range(n):
    l[a[i]] += 1

for i in range(1, 1000001):
    if l[i] > 0:
        if l[i] == 1:
            ans += 1
        for j in range(2, 1000001//i + 1):
            l[i * j] = 0

print(ans)