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())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
flag = [0]*2000000
for i in range(1,len(nums)):
  if nums[i] == nums[i-1]:
    flag[nums[i]] = 1

    
for i in range(len(nums)):
  if flag[nums[i]] == 0:
    ans += 1
  for j in range(nums[i]*2,1000000,nums[i]):
    flag[j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = []
for i in range(len(nums)):
  flag = 0
  for j in range(i-1,len(nums)):
    if i==j:
      continue
    if nums[i]%nums[j] == 0:
      flag = 1
      break
  if flag ==0:
    ans.append(nums[i])
print(len(ans))

Submission status: Wrong Answer

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
#print(A)
i=0
M = max(A)
for i in range(N):
    e = A[i]
    if Cs[e]==1:
        Cs[e]=2
    elif Cs[e]==0:
        Cs[e]=1

for i in range(len(Cs)):
    Cs[i] = Cs[i]%2

for e in A:
    i = 2
    while e*i <M:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Wrong Answer

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
#print(A)
i=0
M = min(max(A),10**6+1)
for i in range(N):
    e = A[i]
    if Cs[e]==1:
        Cs[e]=2
    elif Cs[e]==0:
        Cs[e]=1

for i in range(len(Cs)):
    Cs[i] = Cs[i]%2

for e in A:
    i = 2
    while e*i <M:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Wrong Answer

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
M = A[-1]
#print(A)
i=0

for e in A:
    i = 2
    while e*i < 10**6 +1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    max_A = max(A)
    dp = [True] * (max_A+1) # iより小さいiの約数がAに存在しない
    multi = [0] * (max_A+1) #重複個数
    for a in A:
        multi[a] += 1
        x = a
        while x + a <= max_A:
            x += a
            if dp[x] == False:
                break
            dp[x] = False
    ans = 0
    for a in A:
        if dp[a] and multi[a]==1:
            ans += 1
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 5
cnt = [0] * MAX
ok = [True] * MAX
for x in a:
    cnt[x] += 1
ans = 0
for i in range(1, MAX):
    if cnt[i] > 0:
        for j in range(i * 2, MAX, i):
            if not ok[j]:
                break
            ok[j] = False      
        if ok[i] and cnt[i] == 1:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A = set(A)
B = [True] * (10 ** 6 + 1)
C = Counter(A)
for a in A:
    for i in range(2 * a,10**6 + 1 ,a):
        B[i] = False
cnt = 0
for a in A:
    if (B[a] == True) and (C[a] == 1):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

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

t = [True for _ in range(n)]
a = sorted(a)
ma = a[-1]

for i in range(n):
    for j in range(i+1, n): 
        if t[j] == False: continue
        if a[j]%a[i] == 0:
            t[j] = False

ans = sum(t)
if len(set(a)) != n:
    print(ans-1)
else:
    print(ans)

Submission status: Wrong Answer

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

x=[0]*(10**6+1)
for i in a:
    x[i]+=1
a=[i for i in range(10**6+1) if x[i]==1]
n=len(a)
if n==0:
    print(0)
    exit()
x=[0]*(10**6+1)
for i in a:
    x[i]+=1
for i in range(10**6+1):
    if x[i]==1:
        j=2
        while i*j<=10**6:
            x[i*j]=0
            j+=1
print(x.count(1))

Submission status: Wrong Answer

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

cnt = {}

for item in a:
    if item not in cnt:
        cnt[item] = 0
    cnt[item] += 1

A = list(set(a))

candidate = []

for item in A:
    if cnt[item] == 1:
        candidate.append(item)

judge = [True] *(10**6 + 1)

for item in A:
    for i in range(2, -(-(10**6)//item)):
        judge[item*i] = False

ans = 0

for item in candidate:
    if judge[item]:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

    ans = n
    A.sort()
    table = [True]*(A[-1]+1)
    for k,a in enumerate(A):
        if table[a]:
            if k+1<n and table[k+1]==a:
                ans-=1
            for i in range(a,A[-1]+1,a):
                table[i] = False
        else:
            ans-=1
    
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
m = max(A)
sieve = [True]*(m+1)
sieve[0] = False
ct = 0
for i in range(N):
    n = A[i]
    if i < N-1 and n == A[i+1]:
        sieve[n] = False
    if sieve[n] == False:
        continue
    ct += 1
    for k in range(n*2, m+1, n):
        sieve[k] = False
print(ct)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
m = max(A)
sieve = [True]*(m+1)
sieve[0] = False
ct = 0
for n in A:
    if sieve[n] == False:
        continue
    ct+=1
    for k in range(n*2, m+1, n):
        sieve[k] = False
print(ct)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
def cal(n,li):
    lis=[True]*(n+1)
    for item in li:
        if lis[item]:
            for i in range(item*2,n+1,item):
                lis[i]=False
    return lis
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
a.sort()
l=cal(a[-1],a)
ll=Counter(a)
#print(l,ll)
ans=0
for item in a:
    if l[item]:
        ans+=1
    if ll[item]>1:
        ans-=1
print(ans)
for i in range(len(ll)):
    #print(ll[i])
    if item>1:
        ans-=1
#print(ans)

Submission status: Wrong Answer

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

dp = [0]*(ma+1)

for i in range(1,n):
    if a[i]==a[i-1]:
        dp[a[i]]=1

for i in a:
    for j in range(i*2,ma+1,i):
        if dp[j]==1:
            break
        dp[j]=1
        
ans = 0
for i in a:
    if dp[i]==0:
        ans+=1
        
print(ans)

Submission status: Wrong Answer

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

dp = [0]*(ma+1)

for i in range(1,n):
    if a[i]==a[i-1]:
        dp[a[i]]=1

a = sorted(set(a))

for i in a:
    for j in range(i*2,ma+1,i):
        if dp[j]==1:
            break
        dp[j]=1
        
ans = 0
for i in a:
    if dp[i]==0:
        ans+=1
        
print(ans)

Submission status: Wrong Answer

Solution code:

def main():
    n = int(input().strip())
    l = list(map(int, input().split()))

    l = sorted(l)
    flg = [1 for i in range(n)]

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

    for i in range(n):
        if l[i - 1] == l[i]:
            flg[i - 1] = 0
        if not flg[i]:
            continue
        if l[i] <= 1000:
            for j in range(1, n-i):
                if l[i + j] % l[i] == 0 and flg[i + j]:
                    flg[i + j] = 0

    print(sum(flg))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def main():
    n = int(input().strip())
    l = list(map(int, input().split()))
 
    l = sorted(l)
    flg = [1 for i in range(n)]
 
    if n == 1:
        print(1)
        exit()
 
    for i in range(n):
        if not flg[i]:
            if l[i-1] == l[i]:
                flg[i-1] = 0
            continue
        if l[i] <= 1000:
          for j in range(1, n-i):
            if l[i+j] % l[i] == 0 and flg[i+j]:
                flg[i+j] = 0
        
    print(sum(flg))
 
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    l = sorted(l)
    flg = [1 for i in range(n)]

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

    for i in range(n):
        if not flg[i]:
            if l[i-1] == l[i]:
                flg[i-1] = 0
            continue
        for j in range(n-i-1):
            if l[i+1+j] % l[i] == 0 and flg[i+1+j]:
                flg[i+1+j] = 0

    print(sum(flg))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:


def main():
    n = int(input().strip())
    l = list(map(int, input().split()))

    l = sorted(list(set(l)))
    m = len(l)
    flg = [1 for i in range(m)]
    cnt = m

    if m == 1:
        print(0)
        exit()

    for i in range(m):
        if not flg[i]:
            continue
        for j in range(m-i-1):
            if l[i+1+j] % l[i] == 0 and flg[i+1+j]:
                flg[i+1+j] = 0
                cnt -= 1

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
	N = int(input())
	A = [int(a) for a in input().split(" ")]
	A = list(set(A))
	A.sort()
	if len(A) == 1:
		print(0)
		return 0

	p = []
	while len(A) > 0:
		x = A.pop(0)
		for i in range(len(A)):
			A = list(filter(lambda a: a % x != 0, A))
		p.append(x)
	print(len(p))

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
# print(A)
multiple = [0]*(A[-1]+1)
for i in range(n):
    now = A[i]
    while(now <= A[-1]):
        multiple[now] += 1
        now += now
ans = 0
for i in range(n):
    if(multiple[A[i]] == 1):
        ans += 1
# print(multiple)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
print(A)
N = len(A)
multiple = [0]*(A[-1]+1)
for i in range(N):
    now = A[i]
    while(now <= A[-1]):
        multiple[now] += 1
        now += now
ans = 0
for i in range(N):
    if(multiple[A[i]] == 1):
        ans += 1
print(multiple)
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    import collections
    counter = collections.Counter(A)
    dp = [True for _ in range(max(A)+1)]
    ans = 0
    for a in A:
        if dp[a] and counter[a] == 1:
            for j in range(max(A)//a+1):
                dp[a*j] = False
            if counter[a] == 1:
                ans += 1
    print(ans)

if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    dp = [True for _ in range(max(A)+1)]
    counts = [0 for _ in range(max(A)+1)]
    for a in A:
        if dp[a]:
            counts[a] += 1
            i = 2
            v = a * i
            while v <= max(A):
                dp[v] = False
                i += 1
                v = a * i
    cnt = 0
    for a in A:
        if dp[a] and counts[a] == 1:
            cnt += 1
    

if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
cnt = 0
for i in range(N):
  flg = True
  for j in range(i,N):
    if i != j and A[i]%A[j] == 0 :
      flg = False
      break
  if flg:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
print('A={0}'.format(A))
cnt = 0
for i in range(N):
  flg = True
  for j in range(i,N):
    if i != j and A[i]%A[j] == 0 :
      flg = False
      break
  if flg:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

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

A = max(a)

cnt = [0]*(A+1)
uq = []

for i in a:
    cnt[i] += 1

for i in range(A+1):
    if cnt[i] == 1:
        uq.append(i)

cnt = [0]*((10**6)+1)
cnt1 = 0


a = list(set(a))

# for i in a:
#     for j in range(2,A+1):
#         if i*j<=A+1:
#             cnt[i*j] = 1

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

for i in uq:
    if cnt[i] == 0:
        cnt1 += 1

print(cnt1)

Submission status: Wrong Answer

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

a.sort()

cnt = [0]*(a[-1]+1)
uq = []

for i in a:
    cnt[i] += 1

for i in range(a[-1]+1):
    if cnt[i] == 1:
        uq.append(i)

cnt = [0]*(a[-1]+1)
cnt1 = 0

print(a)
a = list(set(a))
print(a)


for i in a:
    for j in range(2, a[-1]+1):
        if i*j <= a[-1]:
            cnt[i*j] = 1


for i in uq:
    if cnt[i] == 0:
        cnt1 += 1

print(cnt1)

Submission status: Wrong Answer

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

a.sort()

cnt = [0]*(a[-1]+1)
uq = []

for i in a:
    cnt[i] = 1

for i in range(a[-1]+1):
    if cnt[i] >= 1:
        uq.append(i)

cnt = [0]*(a[-1]+1)
cnt1 = 0

for i in uq:
    for j in range(2, a[-1]+1):
        if i*j <= a[-1]:
            cnt[i*j] = 1

for i in a:
    if cnt[i] == 0:
        cnt1 += 1

print(cnt1)

Submission status: Wrong Answer

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

al = a[-1]
table = [True] * (al+1)
cnt = 0
if len(a) == 1:
    print(0)
    exit()
for i in a:
    if table[i]:
        cnt += 1
    for j in range(al):
        if i * j > al:
            break
        else:
            table[i * j] = False
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
INF = 10**6+1
lis = [1]*INF
exist = [0]*INF
for i in range(N):
    a = A[i]
    exist[a] += 1
    if lis[a] and exist[a] < 1:
        q = 2
        while a*q < INF:
            lis[a*q] = 0
            q += 1
cnt = 0
for a in A:
    if lis[a] and exist[a] == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
count = 0
for i in range(N):
  judge = 0
  for j in range(N):
    if A[j] >= A[i] and i != j:
      break
    if A[i] % A[j] == 0 and i != j:
      judge = 1
      break
  if judge == 0:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


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)
    divisors.sort()
    return divisors


n = int(input())
A = list(map(int, input().split()))
cnt_a = Counter(A)
memo = [-1] * 1000001
for a in A:
    memo[a] = 1
for l in cnt_a.keys():
    if cnt_a[l] >= 2:
        memo[l] = "daburi"
#A.sort(reverse=True)
A = set(A)
ans = 0
for a in A:
    if memo[a] == "daburi":
        continue
    divisors = make_divisors(a)
    for divisor in divisors[:-1]:
        if memo[divisor] == 1:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


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)
    divisors.sort()
    return divisors


n = int(input())
A = list(map(int, input().split()))
cnt_a = Counter(A)
memo = [-1] * 1000001
for a in A:
    memo[a] = 1
for l in cnt_a.keys():
    if cnt_a[l] >= 2:
        memo[l] = "daburi"
A.sort(reverse=True)
ans = 0
for a in A:
    if memo[a] == "daburi":
        continue
    divisors = make_divisors(a)
    for divisor in divisors[:-1]:
        if memo[divisor] == 1:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


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)
    divisors.sort()
    return divisors


n = int(input())
A = list(map(int, input().split()))
cnt_a = Counter(A)
memo = [-1] * 1000001
for a in A:
    memo[a] = 1
A.sort(reverse=True)
ans = 0
for a in A:
    divisors = make_divisors(a)
    # print(divisors)
    for divisor in divisors[1:-1]:
        if memo[divisor] == 1:
            break
    else:
        ans += 1
daburi = 0
for l in cnt_a.values():
    if l >= 2:
        daburi += l
print(ans - daburi)

Submission status: Wrong Answer

Solution code:
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
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
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)
    divisors.sort()
    return divisors
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
mod = 10**9 + 7

#maincode-------------------------------------------------

n = ini()
a = inl()
A = 10**6 + 5
b = [0] * A
ans = 0

for i in a:
    i -= 1
    b[i] += 1
c = b[::]


for j in a:
    if c[j] > 1:
        b[j] = 0
    for i in range(j*2,A,j):
        b[i] = 0

ans = sum(i != 0 for i in b) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
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
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)
    divisors.sort()
    return divisors
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
mod = 10**9 + 7

#maincode-------------------------------------------------

n = ini()
a = inl()
A = 10**6 + 5
b = [0] * A
ans = 0

for i in a:
    i -= 1
    b[i] += 1

for j in a:
    if b[j] > 1:
        b[j] = 0
    for i in range(j*2,A,j):
        b[i] = 0

ans = sum(i != 0 for i in b) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n=int(input())
    A=list(map(int, input().split()))
    counts=[0]*(10**6+1)
    for AA in A:
        counts[AA]+=1
    ans=0
    for i in range(1,10**6):
        if counts[i]>0:
            for j in range(i+i,10**6+1,i):
                counts[j]=-1
        if counts[i]==1:
            ans+=1
    print(ans)
        

        
    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
MAX = 10**6+1
cnt = [0]*MAX

for x in A:
  if cnt[x] != 0:
  	cnt[i] = 2
  else:
    for i in range(x, MAX, x):
      cnt[i] += 1
  
ans = 0
for x in A:
  # 2回以上通った数字 (cnt[x]>1) は，その数字より小さい約数が存在する (割り切れる他の数が存在する)。
  if cnt[x] == 1:  
    ans += 1
    
print(ans)

Submission status: Wrong Answer

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

checked = [0 for _ in range(10**6+1)]
nums.sort()
answer = N
s_cnt = 0
before = 0
for num in nums:
  if num == before:
    s_cnt += 1
    continue
  else:
    if s_cnt != 0:
      answer -= (s_cnt + 1)
      s_cnt = 0
    before = num
  if checked[num] == 1:
    answer -= 1
  else:
    count = 1
    temp = num*count
    while(temp <= nums[N-1]):
      checked[temp] = 1
      count += 1
      temp= num*count
if s_cnt != 0:
  print(answer-s_cnt-1)
else:
  print(answer)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

A.sort()

count = Counter(A)

divisible = [False] * (max_a + 1)

ans = 0

for a in A:
    if divisible[a] or count[a] > 1:
        continue
    ans += 1
    for i in range(1, max_a // a + 1):
        divisible[i * a] = True
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
n = int(input())
lst = list(map(int,input().split()))
arr = np.array(lst)
lst.sort()
check = ['t']*n
s = 0
arr2 = arr % lst[0]
if sum(arr2) == 0:
  s = 0
else:  
  s = 1
  i = 0
  while True:
    if i == n-1:
      break
    else:
      for k in range(i,n):
        if lst[k] % lst[i] == 0:
          check[k] = 'f'
      j = i+1
      while j <= n:
        if check[j] == 'f':
          pass
        else:   
          s += 1
          i = j
          break
        j += 1  
        if j == n:
          print(s)
          sys.exit()
    
    

print(s)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=1
for i in range(N-1,-1,-1):
  flag=0
  lb=bisect.bisect_right(A,A[i]//2)
  if lb == 0 and A[i] == A[0]:
    continue
  for j in range(lb-1,-1,-1):
    if A[i]%A[j]==0:
      flag=1
      break
  if flag==0:
    ans+=1

if N>1 and A[0]==A[1]:
  ans-=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
am=max(a)
dp=[[True,0] for _ in range(am+1)]
count=0
for i in a:
    if dp[i][0]==False:
        continue
    else:
        if dp[i][1]==1:
            dp[i][0]=False
            count-=1
        else:
            dp[i][1]=1
            count+=1
            for j in range(i,am+1,i):
                dp[j][0]=False
print(count)

Submission status: Wrong Answer

Solution code:
#D - Div Game
N = int(input())

def Prime_factorize(n):
    cnt = 0
    A = set()
    #2の倍数で割っていく
    z = 2
    while n%2==0 and (n>=z):
        cnt += 1
        n //= z

        A.add(z)
        #割るたびに2倍
        z *= 2
    #割る始めの数をfとして保持
    f = 3
    z = 3
    #sqrt(n)以内に全ての素因数は含まれる
    while f*f <= n:
        if n%z == 0:
            cnt += 1
            n //= z
            A.add(z)
            
            #割るたびにf倍
            z = z*f
        #fで割り切れなかったら(f+2)してf_divもリセット
        else:
            f += 2
            z = f

    #残ったnが素数かつ以前に選んでいないとき
    if n != 1 and not(n in A):
        A.add(z)
        cnt += 1
    #素数のとき
    if cnt == 0:
        cnt = 1
    return cnt
if N == 1:
    ans = 0
else:
    ans = Prime_factorize(N)
print(ans)

Submission status: Wrong Answer

Solution code:
#D - Div Game
N = int(input())

def Prime_factorize(n):
    cnt = 0
    A = set()
    #2の倍数で割っていく
    z = 2
    while n%2==0 and (n>=z):
        cnt += 1
        n //= z

        A.add(z)
        #割るたびに2倍
        z *= 2
    #割る始めの数をfとして保持
    f = 3
    z = 3
    #sqrt(n)以内に全ての素因数は含まれる
    while f*f <= n:
        if n%z == 0:
            cnt += 1
            n //= z
            A.add(z)

            #割るたびにf倍
            z = z*f
        #fで割り切れなかったら(f+2)してf_divもリセット
        else:
            f += 2
            z = f

    #残ったnが素数かつ以前に選んでいないとき
    if n != 1 and not(n in A):
        A.add(z)
        cnt += 1
    #素数のとき
    if cnt == 0:
        cnt = 1
    return cnt
if N == 1:
    ans = 0
else:
    ans = Prime_factorize(N)
print(ans)

Submission status: Wrong Answer

Solution code:
import numba
from numba import njit, b1, i4, i8, f8
import numpy as np  # noqa

N = int(input())
A = np.array(sorted([int(x) for x in input().split()]))

print(A)


@njit((i8[:], ), cache=True)
def main(A):
    ans = 0
    for i in range(len(A) - 1, 0, -1):
        for j in range(i):
            if A[i] == A[j]:
                continue
            if A[i] % A[j] == 0:
                break
            if A[i] < A[j] * 2 or j == i - 1:
                ans += 1
                break
    if A[0] != A[1]:
        ans += 1
    return ans


print(main(A))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=list(map(int, input().split()))

m=Counter(a)
a=list(set(a))
for i in m.keys():
  if m[i]>1:
    a.remove(i)
a.sort()
n=len(a)
arr=[0]*n
ans=0
if n==1:
    print(1)
    exit()
if n==0:
    print(0)
    exit()
for i in range(n-1):
    if arr[i]==1:
        continue
    ans+=1
    for j in range(i,n):
        if a[j]%a[i]==0:
            arr[j]=1
if arr[-1]==0:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
A=sorted(A)
B=['true']*max(A)  #Bがtrueのときそれより小さい約数がAに存在しない
C=[0]*max(A)
for i in range(n):
    C[A[i]-1]=C[A[i]-1]+1
count=0
for i in range(n):       
    if(B[A[i]-1]=='true'):
        for j in range(2,max(A)):
            if(A[i]*j)>max(A):
                break
            if(A[i]*j in A):
                B[A[i]*j-1]='false'

for i in range(n):
    if(B[A[i]-1]=='true'):
        count=count+1
ans=count
for i in range(max(A)):
    if(C[i]>=2):
        ans=ans-C[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=['true']*max(A)  #Bがtrueのときそれより小さい約数がAに存在しない
C=[0]*max(A)
for i in range(n):
    C[A[i]-1]=C[A[i]-1]+1
count=0
for i in range(n):       
    if(B[A[i]-1]=='true'):
        for j in range(2,max(A)):
            if(A[i]*j)>max(A):
                break
            if(A[i]*j in A):
                B[A[i]*j-1]='false'

for i in range(n):
    if(B[A[i]-1]=='true'):
        count=count+1
ans=count
for i in range(max(A)):
    if(C[i]>=2):
        ans=ans-C[i]
print(ans)

Submission status: Wrong Answer

Solution code:
#D
from sys import stdin
def main():
    readline=stdin.readline
    n = int(readline())
    a = list(map(int,readline().split()))
    count=0
    for i in range(len(a)):
        num_div=0
        for j in range(i,len(a)):
            if a[i]%a[j]==0:
                num_div+=1
        if num_div==1:
            count+=1
    print(count)
main()

Submission status: Wrong Answer

Solution code:
#D
n = int(input())
a = list(set(map(int,input().split())))
count=0
for i in a:
    num_div=0
    for j in a:
        if i%j==0:
            num_div+=1
    if num_div==1:
        count+=1
print(count)

Submission status: Wrong Answer

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

a.sort()

dup_num = len([x for x in set(a) if a.count(x) > 1])

def eratosthenes_num(x):
  list1 = []
  list2 = []
  for i in a:
    if i not in list2:
      list1.append(i)
      for j in range(i, x+1, i):
        list2.append(j)
  print(len(list1) - dup_num)

eratosthenes_num(max(a))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
A=sorted(A)
soset=set()
soset.add(A[0])
for i in range(1,N):
    flag=0
    now=A[i]
    for k in soset:
        if now%k==0:
            if now==k:
                soset.discard(k)
            flag=1
            break
    if flag==0:
        soset.add(now)
print(len(soset))