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: Accepted

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
import bisect
from queue import PriorityQueue
import itertools
from itertools import accumulate
from copy import deepcopy
from collections import Counter
import heapq
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    return c.join(A)
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def inputfloatlist(): 
    return list(map(float,input().split()))
def tozero(A):
    ret=[None]*len(A)
    for a in range(len(A)):
        ret[a]=A[a]-1
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def getmd(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):
    return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow
def heron(a,b,c):
    s=(a+b+c)/2
    S=s(s-a)(s-b)(a-c)
    S=math.sqrt(S)
    return S
def getAreaOfTriangle(x1,y1,x2,y2,x3,y3):
    a=geted(x1,y1,x2,y2)
    b=geted(x2,y2,x3,y3)
    c=geted(x3,y3,x1,y1)
    return heron(a,b,c)






######################################################################################################
N=int(input())
A=inputintlist()
S=set()
for k,v in Counter(A).items():
    if v>1:
        S.add(k)
num=10**6+10
warikireru=[False]*num
A.sort()
ans=0
for a in A:
    if warikireru[a]==False:
        if a not in S:ans+=1
    now=a
    if warikireru[now]:continue
    for b in range(now,num,now):
        warikireru[b]=True
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
aset=set()
dp=[0]*(m+1)
for i in a:
  dp[i]=1
for i in sorted(a):
  if dp[i]!=0:
    for j in range(1,m//i):
      dp[i*(j+1)]=0
for i in a:
  if i in aset:
    dp[i]=0
  else:
    aset.add(i)
print(sum(dp))

Submission status: Accepted

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

t = [True] * (10 ** 6 + 1)
d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

A = sorted(set(A))
for a in A:
    if d[a] > 1:
        t[a] = False
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False

result = 0
for a in A:
    if t[a]:
        result += 1
print(result)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
ans = 0
d = [0]*(10**6+1)
for i in range(N):
    if d[A[i]] == 0:
        if c[A[i]] == 1:
            ans += 1
        j = A[i]
        while j <= (10**6):
            d[j] += 1
            j += A[i]
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    AList = list(map(int, input().split()))
    AList.sort()
    AMax = AList[-1] + 1

    dp = [True] * AMax
    answer = 0

    ACheckSet = set()
    ACheckSetCheckSet = set()

    for A in AList:

        if dp[A]:
            answer = answer + 1
            ACheckSet.add(A)

            for x in range(A, AMax, A):
                dp[x] = False

        elif A in ACheckSet:

            if A in ACheckSetCheckSet:
                pass
            else:
                answer = answer - 1
                ACheckSetCheckSet.add(A)

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

cnt=[0]*((10**6)+1)
for elem in a:
    cnt[elem]+=1

unique=[]

for i in range(10**6+1):
    if cnt[i]==1:
        unique.append(i)

cnt=[0]*((10**6)+1)
a=list(set(a))

for elem in a:
    for i in range(elem*2,10**6+1,elem):
        cnt[i]=1

ans=0

for elem in unique:
    if cnt[elem]==0:
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=set(A)
A.sort()
S=max(A)
ans=[1]*S
for i in range(len(A)):
  if ans[A[i]-1]!=0:
    if i>0 and A[i]==A[i-1]:
      ans[A[i]-1]=0
    for j in range(A[i]*2,S+1,A[i]):
      ans[j-1]=0
k=0
for i in A:
  if ans[i-1]==1:
    k+=1
print(k)

Submission status: Accepted

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

if N == 1:
    print(1)
    exit()
    
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        if tmp > A[-1]:
            break
        check_list[tmp] += 1
        tmp += A[i]

for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * (a[-1]*3)
for i, num in enumerate(a):
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        if i-1>=0 or i+1<n:
            flag[num] = False
    for j in range(2, a[-1]//num+2):
        flag[j*num] = False
counter = 0
for i in a:
    if flag[i]:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

a.sort()
dic=dict(Counter(a))

ans=0
for i in range(n):
    if dic[a[i]]==1:
        ans+=1
    if dic[a[i]]==0:
        continue
    dic[a[i]]=0
    j=1
    while 1:
        j+=1
        if j*a[i]>10**6+10:
            break
        if j*a[i] in dic:
            dic[j*a[i]]=0

print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline().rstrip('\n')
    

def calc(N, A):
    A.sort()
    M = A[N - 1] + 1
    b = [False for _ in range(M)]
    tmp = -1
    d = set()
    for a in A:
        if a == tmp:
            d.add(a)
            continue
        for i in range(a * 2, M, a):
            b[i] = True
        tmp = a
    n = 0
    for a in A:
        if not a in d:
            n += (0 if b[a] else 1)
    return n

N = int(input())
A = [int(s) for s in input().split()]
print(calc(N, A))

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
maxa = max(a)
a_s = set(a)
s = set()
s1 = set()
same_s = set()
ans = 0
for i in a:
    if i in s1:
        same_s.add(i)
    if i not in s:
        s1.add(i)
        for j in range(i, maxa+1, i):
            s.add(j)
        ans += 1

print(ans - len(same_s))

Submission status: Accepted

Solution code:
import sys
import math

n = int(input())
a = list(map(int, input().split()))
a.sort()
limit = max(a)
dp = [True] * (limit + 1)
archives = set()
for i in a:
    if i in archives:
        dp[i] = False
        continue
    archives.add(i)
    n = 2
    while i * n <= limit:
        dp[i * n] = False
        n += 1

# print(dp)
ans = 0
for i in a:
    if dp[i] is True:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
n = int(input())
a = list(map(int, stdin.readline().split()))
a.sort()
amax = max(a)+1
e = [True]*amax
Alice = set()
Bob = set()
ans = 0

for i in range(n):
    if e[a[i]] == True:
        Alice.add(a[i])
        for j in range(a[i], amax, a[i]):
            e[j] = False
    else:
        if a[i] in Alice:
            Bob.add(a[i])

print(len(Alice - Bob))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = max(a)
t = [1]*(m+1)
for i in range(n):
    if(t[a[i]] == 1):
        x = a[i]*2
        while(x <= m):
            t[x] = 0
            x += a[i]
for i in range(n):
    if(t[a[i]] == 0):
        n -= 1
    elif(t[a[i]] == 1):
        t[a[i]] = -1
    elif(t[a[i]] == -1):
        t[a[i]] = -2
        n -= 2
    else:
        n -= 1
print(n)

Submission status: Accepted

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

t = [True] * (10 ** 6 + 1)
d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

A = sorted(set(A))
for a in A:
    if d[a] > 1:
        t[a] = False
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()

MAX = 10 ** 6


def main():
    A.sort()
    s = set()
    ans = N
    for i in range(N):
        a = A[i]
        if a in s:
            ans -= 1
            continue
        if i < N - 1 and A[i + 1] == a:
            ans -= 1
        n = MAX // a
        for i in range(1, n + 1):
            s.add(a * i)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
A = list(map(int,(input().split())))
A.sort()
A.append(-1)
ans = 0
ok = [True]*(10**6+1)
for i in range(N):
    now = A[i]
    if now != A[i+1]:
        if ok[now]:
            if i == 0 or now != A[i-1]:
                ans += 1
            c = 1
            while now*c < 10**6+1:
                ok[now*c] = False
                c += 1
print(ans)

Submission status: Accepted

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

maxa=max(a)
dp=[0]*(maxa+1)
for num in a:
    for i in range(2,10**10):
        if num*i > maxa:
            break
        dp[num*i]=1

import collections
c = collections.Counter(a)

ans=0
for num,cnt in c.items():
    if cnt==1 and dp[num]==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key

# from numpy import gcd


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


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

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N = intinput()
    # ds = set(mulinputs())

    # if len(ds) <= 1:
    #     print(0)
    #     exit()
    # ds = list(ds)
    # # ds.sort()
    # if ds[0] == 1:
    #     print(0)
    #     exit()
    # p = []
    # l = int(sqrt(len(ds)))
    # # for _ in range(l):
    # #     if not ds:
    # #         break
    # while ds:
    #     tmp = ds.pop(0)
    #     p.append(tmp)
    #     ds = [ d for d in ds if d % tmp != 0]
# 
    # # 出力
    # print(len(p)+len(ds))


    # ======
    # 参考:https://atcoder.jp/contests/abc170/submissions/14360996
    # ======
    # N <= 2*10**5なので6乗あれば絶対安心
    M = 10**6+1
    # 0 は 0個という意味とfalseという意味
    memo = [0] * M
    ds = list(mulinputs())
    # Trueという意味と、iがいくつあるか(同値の個数をカウント)
    # 今仮に、ds集合数の中で自分自身しか約数を持たない素数だと認定する
    for i in ds: memo[i] += 1
    ds.sort()
    ans = []
    for i in ds:
        # すでに誰かの約数となっている
        if not memo[i]:
            continue
        # まだ誰の約数にもなってないけど、同値なのが自分自身しかいないかチェック
        if memo[i] == 1:
            ans += [i]
        # iの倍数のフラグを落としていく=>落とされた先は、自分(i)を約数として持ってる
        for j in range(i, M, i): memo[j] = 0
    # 出力
    print(len(ans))

Submission status: Accepted

Solution code:
from collections import Counter

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

m=a[-1]+1
dp=[1]*m
c=Counter(a)
ans=0
for i in a:
    if dp[i] and c[i]==1:
        ans+=1

    for j in range(2*i, m, i):
        dp[j]=0

print(ans)
#print(c)

Submission status: Accepted

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

D=set()
S=set()
for i in range(n):
    if A[i] in S:
        D.add(A[i])
    else:
        S.add(A[i])

biggest = max(S)
dp = [1 for i in range(biggest+1)]
for i in S:
  if i in D:
    dp[i] = 0
  for j in range(2*i,biggest+1,i):
    dp[j] = 0

ans = 0
for i in A:
  ans += dp[i]
print(ans)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
a.sort()
am = a[-1] + 1
dp = [True] * am
ans = 0
dup = set()
for x in a:
    d = dp[x]
    if d:
        ans += 1
        for i in range(x, am, x):
            dp[i] = False
        dp[x] = None
    elif d == None:
        dup.add(x)

print(ans - len(dup))

Submission status: Accepted

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

d = set()
s = set()

for n in numbers:
    if n in s: 
        d.add(n)
    else :
        s.add(n) 

M = max(s) 

X = [1 for _ in range(M+1)] 

for a in s:
    if a in d:
        X[a] = 0 
    for i in range(2*a, M+1, a): 
        X[i] = 0
    
output = 0

for n in numbers:
    if X[n] == 1:
        output += 1
print(output)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    for a in A:
        B[a] += 1

    for i in range(1, 10**6):
        if not B[i]:
            continue
        j = 2*i
        while j <= 10**6:
            B[j] += 1
            j += i
    ans = 0
    for a in A:
        if B[a] <= 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

t = [True] * (10 ** 6 + 1)
d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1
    if d[a] > 1:
        t[a] = False

A = sorted(set(A))
for a in A:
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

Submission status: Accepted

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

MAXN = max(A)
B = [False]*(MAXN+1)
for c in C.most_common():
    B[c[0]] = True
ans = 0
for i in range(MAXN + 1):
    if B[i]:
        if C[i]==1:
            ans += 1
        B[i::i] = [False]*(MAXN//i)
print(ans)

Submission status: Accepted

Solution code:

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(A))
mark = [0]*(10**6+1)

for i in A:
    mark[i] += 1
    if mark[i] == 1:
        for j in range(2*i, len(mark), i):
            mark[j] += 2

print(mark.count(1))

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
        #print(dp)
    print(dp.count(1))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

maxa=max(a)
dp=[0]*(maxa+100)
for num in a:
    for i in range(2,10**10):
        if num*i > (maxa+50):
            break
        dp[num*i]=1

import collections
c = collections.Counter(a)

aa=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        aa.append(num)

ans=0
for num in aa:
    if dp[num]==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    S = list(set(A))
    ND = [True]*(10**6 + 1)
    for e in S:
        m = e*2
        while m <= 10**6:
            ND[m] = False
            m += e
    ans = 0
    for a in A:
        if C[a] == 1 and ND[a]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

# エラトステネスの篩っぽく処理
ans_list = [True for _ in range(A[-1] + 1)]
ans = 0

# ダブリを省くために先に数える
c = Counter(A)

for a in A:
    if ans_list[a] == True:
        if c[a] == 1:
            ans += 1
        i = 2
        while a * i <= A[-1]:
            ans_list[a * i] = False
            i += 1

print(ans)

Submission status: Accepted

Solution code:

import numpy as np
def resolve():
    N = int(input())
    A = np.array(list(map(int, input().split())))

    cnt = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if cnt[x] > 1:
            continue
        cnt[::x] += 1
    ret = 0
    for x in A:
        ret += cnt[x] == 1

    print(ret)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

m_a = max(A)+1
B = [0]*(m_a)

for i in A:
  B[i]+=1
  if B[i] == 1:
    for j in range(i*2, m_a, i):
      B[j]+=100
print(B.count(1))

Submission status: Accepted

Solution code:
def main():
    n, *A = map(int, open(0).read().split())
    A.sort()
    n = A[-1]
    isPrime = [True] * (n + 1)
    prep = 0
    for i in A:
        if prep == i:
            isPrime[prep] = False
            continue
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
        prep = i

    prep = res = 0
    for i in A:
        if prep == i:
            continue
        if isPrime[i]:
            res += 1
        prep = i
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
counter = Counter(A)
ans = 0
cache = set()
for a in A:
    if a in cache:
        continue
    tmp = a
    while tmp <= 10**6:
        cache.add(tmp)
        tmp += a
    if counter[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

a.sort()
mx = a[-1]

dp = [True for _ in range(mx)]

cnt = 0
for i, ai in enumerate(a):
    if dp[ai-1]:
        if i >= len(a)-1 or ai != a[i+1]:
            cnt += 1
        for j in range(ai - 1, mx, ai):
            dp[j] = False

print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
A.sort()
dic = defaultdict(int)
for a in A:
    dic[a] += 1
ctr = defaultdict(int)
ans = 0
for a in A:
    if dic[a] == 1 and ctr[a] == 0:
        ans += 1
    if ctr[a] == 0:
        m = 1
        while a*m <= 10**6:
            ctr[a*m] += 1
            m += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
M = max(a)
cands = [0]*M

ans = 0
for num in a:
    if cands[num-1] >= 2:
        continue
    for i in range(num, M+1, num):
        cands[i-1] += 1
        
for num in a:
    if cands[num-1]==1:
        ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
anstable = [0] * (10 ** 6 + 1)
d = defaultdict(int)
for i in a:
    d[i] += 1

u = []
for i, v in d.items():
    if v == 1:
        u.append(i)
a = set(a)
for i in a:
    for j in range(i * 2, 10 ** 6 + 1, i):
        anstable[j] += 1

cnt = 0
for i in u:
    if anstable[i] == 0:
        cnt += 1

print(cnt)