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:
import sys
input = sys.stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
eratosthenes = [True] * (maxval+1)

for i in range(n):
    if a[i] == 1:
        continue
    for k in range(a[i] + a[i], maxval+1, a[i]):
        eratosthenes[k] = False

result = sum(eratosthenes[v] for v in a)
print(result)

Submission status: Wrong Answer

Solution code:
from collections import Counter
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    dp = [True] * (10 ** 6 + 1)
    counter = Counter(A)

    A.sort()
    ans = 0
    for a in A:
        if counter[a] >= 2:
            continue
        if dp[a]:
            ans += 1
            i = a
            while i <= 10 ** 6:
                dp[i] = False
                i += a
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

M = max(A)
dp = [True] * (M + 1)
ans = 0

for i in set_A:
    for j in range(2 * i, M + 1, i):
        dp[j] = False

for i in set_A:
    if dp[i]:
        ans += 1
    if A.count(i) >= 2:
        ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def chk():
    N = int(input())
    A=list(map(int,input().split(' ')))
    counter = Counter(A)

    flg = [0 for _ in range(10**6+1)]

    ans = 0
    for i in range(1,10**6+1):
        if counter[i] == 0:
            continue
        if flg[i] == 0 and counter[i] == 1:
            ans += 1
        for j in range(1,(10**6+1)//i):
            flg[i*j] = 1

    print(ans)

chk()

Submission status: Wrong Answer

Solution code:
def main():
    n, *a = map(int, open(0).read().split())
    if n == 1:
        print(1)
        return

    m = max(a) + 1
    l = [0] * m
    for i in a:
        if l[i] == 0:
            l[i] = -2
        elif l[i] == -1:
            l[i] = 1
        for j in range(i, m, i):
            l[j] += 1

    ans = l.count(-1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

MAX = 1000005
cnt = [0] * MAX
for x in a:
    if cnt[x] != 0:
        continue
    #cnt配列の各倍数のところに+1
    for i in range(x, MAX, x):
        cnt[i] += 1
ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = [True] * n

# 先に重複を処理しておく
from collections import Counter
ca = Counter(a)

for i in range(n):
    if not ans[i]:
        continue
    if ca[a[i]] > 1:
        ans[i] = False
        continue
    for j in range(i+1,n):
        if a[j]%a[i]==0:
            ans[j]=False
print(sum(answer for answer in ans))

Submission status: Wrong Answer

Solution code:

                
from math import sqrt
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = set(A)
B = dict(Counter(A))

n = 10**6
prime = {i for i in range(2, n)}
for i in range(2, n):
    if i in prime:
        for j in range(i*2, n, i):
            if j in prime:
                prime.remove(j)
ans = 0
for i in range(N):
    if B[A[i]] > 1:
        pass
    else:
        if A[i] in prime:
            ans+=1
            continue
        flag = True
        for j in range(1, A[i]+1):
            if j**2 > A[i]:
                break
            if A[i] % j == 0:
                if A[i]//j in C:
                    if A[i]//j < A[i]:
                        flag = False
                        break
                if j in C:
                    if j < A[i]:
                        flag = False
                        break

        ans += int(flag)
print(ans)

Submission status: Wrong Answer

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

    a.sort()

    dp = [1]*max(a)

    for i in a:
        if i*2 > len(dp):
            pass
        elif dp[2*i-1] == 0:
            pass
        else:
            for j in range(2*i-1, len(dp), i):
                dp[j] = 0


    count = 0
    for i in set(a):
        if len(set(a))==1:
            break
        if dp[i-1]==1:
            count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
# D - Not Divisible

N = int(input())
A = list(int(a) for a in input().split())
A.sort()

M = max(A)
is_D = [0] * (M+1)
for i, a in enumerate(A):
    if is_D[a]:
        is_D[a] = 2
        continue
    for j in range(2*a, M+1, a):
        is_D[j] += 1

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

Submission status: Wrong Answer

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

M = max(A)
dp = [True] * (M + 1)
ans = 0

for i in set_A:
    for j in range(2 * i, M + 1, i):
        dp[j] = False

for i in set_A:
    if dp[i]:
        ans += 1
for i in set_A:
    if A.count(i) >= 2:
        ans -= A.count(i)

print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 

"""
3
1 1 2
のパターンが例外だった
"""

N = int(input())
A = LI()
A.sort()

table = [0 for i in range(10 ** 6 + 1)]
cnt = 0
pre = -1
for a in A:
    if table[a] != 0:
        pass
    else:
        if pre != a:
            cnt += 1
        for i in range(1, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            table[a * i] = 1

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c=0
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        del A[k+1] 
        A.insert(0,0)
        c+=2
del A[:c]
if len(A)>0:
    saidai = A[-1]
else:
    saidai=0
#print(A)
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        count+=1
        for j in range(A[k], saidai+1, A[k]):
            foo[j] = 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
exist_flags = [0] * (10 ** 6)
for a in A:
    if exist_flags[a - 1] > 0:
        exist_flags[a - 1] += 1
    else:
        # for i in range(a, 25, a):
        for i in range(a, 10 ** 6, a):
            exist_flags[i - 1] += 1


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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
inf = 10**6
boo = [0]*(inf+1)#True or False
for a in A:
    for i in range(2,inf//a + 1):
        boo[a*i] = 1
cnt = 0
comp = 0
doub = 0
for a in A:
    if a == comp:
        doub += 1
    else:
        cnt += doub + 1 if doub > 0 else 0
        doub = 0
        cnt += boo[a]
    comp = a
cnt += doub + 1 if doub > 0 else 0
print(N-cnt)

Submission status: Wrong Answer

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

MAX = 1000005
cnt = [0] * MAX
for x in a:
    #cnt配列の各倍数のところに+1
    for i in range(x, MAX, x):
        if cnt[i] > 2:
            break 
        cnt[i] += 1
ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

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

from collections import Counter
c = Counter(A)

NMAX = 10 ** 6 + 1000
dp = [True] * (NMAX + 1)
for k, v in c.items():
    if dp[k]:
        for i in range(k * 2, NMAX + 1, k):
            dp[i] = False
    if v > 1:
        dp[k] = False

count = 0
for k, v in c.items():
    if v > 1: continue
    if dp[k]: count += 1

print(count)

Submission status: Wrong Answer

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

kazu=[0]*(10**6+1)
for i in a_uni:
  for j in range(i,10**6+1, i):
    if j > 10**6+1:
      break
    kazu[j] += 1

count = 0
for i in a_uni:
  if kazu[i] == 1:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = [0 for _ in range(10**6+5)]
ans = 0
if a[0] == 1:
    print(0)
    exit()
for x in a:
    for i in range(x, 10**6+5, x):
        cnt[i] += 1
for x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#import numpy as np
import time

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう
remove_list = []

kouho = [x for x in set(A) if A.count(x) == 1]
#maxA = 10**5

#target = kouho[:]
if kouho != []:
    maxA = kouho[-1]

buf = time.time()

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN+1):
        buf = A[i]*n
        remove_list.append(buf)
            #print(A[i]*n)

#target = kouho[:]
kouho = list(set(kouho) - set(remove_list))

print(len(kouho))

Submission status: Wrong Answer

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

M = max(A)
dp = [True] * (M + 1)
ans = 0

for i in A:
    for j in range(2 * i, M + 1, i):
        dp[j] = False

for i in A:
    if dp[i]:
        ans += 1
for i in set_A:
    if A.count(i) >= 2:
        ans -= A.count(i)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())						# 5
A =        list( map(int, input().split()) )	# 1 2 3 4 5 ...

A.sort()
maxA = A[-1]
X = [0]*(maxA+1)


for a in A:
  for i in range(1,maxA+1):
    x = a*i
    if x > maxA: break
    if X[x] >= 2: break
    X[x] += 1

ans = 0
for a in A:
  if X[a]==1: ans+=1

print(ans)
# print(A)
# print(X)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def chk():
    N = input()
    A=list(map(int,input().split()))
    counter = Counter(A)

    flg = [0 for _ in range(10**6+1)]

    ans = 0
    for i in range(1,10**6+1):
        if counter[i] == 0:
            continue
        if flg[i] == 0 and counter[i] == 1:
            ans += 1
        for j in range(1,(10**6+1)//i):
            flg[i*j] = 1

    print(ans)

chk()

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 

"""
3
1 1 2
のパターンが例外だった
"""

N = int(input())
A = LI()
A.sort()

table = [0 for i in range(10 ** 6 + 1)]
cnt = 0
for a in A:
    if table[a] != 0:
        pass
    else:
        cnt += 1
        for i in range(1, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            table[a * i] = 1

A_dic = collections.Counter(A)
for key in A_dic.keys():
    if A_dic[key] > 1:
        cnt -= 1
    
print(cnt)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax=A[-1]+1
    dp = [True]*Amax
    ans=0
    a_temp=0
    a_tempcheck=False
    if A[0]==1:
        ans=0
    else:
        for a in A:
            if a_temp==a:
                dp[a] = False
                if a_tempcheck==False:
                    ans-=1
                    a_tempcheck=True
                
            if dp[a]:
                ans+=1
                for i in range(a, Amax, a):
                    dp[i] = False
            a_temp=a
            a_tempcheck=False

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

Submission status: Wrong Answer

Solution code:

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

count =0

while(not a==[]):
    am = min(a)
    c = a.count(am)
    a = [j for j in a if not j ==am]
    ai =a
    if c ==1:
        for i in ai:
            if i%am ==0 :
                a = [j for j in a if not j ==i]
            #a.remove(i)

        count =count +1




print(count)

Submission status: Wrong Answer

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

    a.sort()

    for num, e in enumerate(a):
        i = 0
        while len(a) > i:
            if a[i] % e == 0:
                a.pop(i)
            else:
                i += 1
    print(len(a))

Submission status: Wrong Answer

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


def divisors(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

N = int(input())
A = [int(a) for a in input().split()]
X = [0] * 1000001
for a in A:
    X[a] += 1

ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
M=max(a)
ok = [0]*(M+1)
a.sort()
for i in range(n):
    ok[a[i]] += 1

for i in range(n):
    if ok[a[i]] == 1:
        for g in range(a[i], M+1, a[i]):
            if g != a[i]:
                ok[g] = 0

if ok.count(1) == 1:
    print(0)
else:
    print(ok.count(1))

Submission status: Wrong Answer

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

li.sort(reverse=True)

ans = 0

for i in range(n):
    for j in range(i+1, n):
        if li[i]%li[j] == 0:
            break
    else:
        ans += 1

if li[n-1] == li[n-2]:
    ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
#TLE

N=int(input())
l=list(map(int,input().split()))
l=[x for x in set(l) if not l.count(x) > 1]
count=0
l.sort(reverse=True)
if not l:
    print(0)
else:
    M=max(l)
    tmp=[0]*(M+1)
    """
    for i in range(len(l)):
        Frag=True
        for j in range(1,len(l)-i):
            if l[i]%l[i+j]==0:
                Frag=False
                break
        if Frag==True:
            count+=1
    """
    for i in l:
        for j in range(i,M+1,i):
            tmp[j]+=1
    for i in l:
        if tmp[i]==1:
            count+=1
    print(count)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 

"""
3
1 1 2
のパターンが例外だった
"""

N = int(input())
A = LI()
A.sort()

table = [0 for i in range(10 ** 6 + 1)]
cnt = 0
for a in A:
    if table[a] != 0:
        pass
    else:
        cnt += 1
        for i in range(1, 10 ** 6):
            if a * i > 10 ** 6:
                break
            table[a * i] = 1

A_dic = collections.Counter(A)
for key in A_dic.keys():
    if A_dic[key] > 1:
        cnt -= 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter



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

flg = [0 for _ in range(10**6+1)]

ans = 0
for i in range(1,10**6+1):
    if counter[i] == 0:
        continue
    if flg[i] == 0 and counter[i] == 1:
        ans = ans + 1
    for j in range(1,(10**6+1)//i):
        flg[i*j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(set(list(map(int, input().split()))))
numbers = [0] * (max(A)+1)
ans = len(A)
if ans == 1:
    print(0)
    exit()
for a in A:
    i = 1
    while a*i <= max(A):
        numbers[a*i] += 1
        i += 1
    if numbers[a] >= 2: ans -= 1
print(ans)

Submission status: Wrong Answer

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

N = int(readline())
A = sorted(list(map(int,readline().split())))
M = A[-1]

dp = set()
ans = 0
for a in A:
  if a in dp:
    continue
  ans += 1
  for i in range(a * 2, M + 1, a):
    dp.add(i)
from collections import Counter
counter = Counter(A)
for val in counter.values():
  if val > 1:
    ans -= val
    
print(ans)

Submission status: Wrong Answer

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

if np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1) > 0:
    print(1)
else:
    for i in range(1,len(dp)):
        if dp[i] and i in a:
            for j in np.arange(i*2, len(dp), i):
                dp[j] = False
    print(np.count_nonzero(dp[a] == True))

Submission status: Wrong Answer

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

max_a = max(a)
dp = [0] * (max_a + 1)

for i in a:
    dp[i] += 1
    if dp[i] ==1:
        for j in range(i, max_a+1, i):
            dp[j] += 1
dp.count(1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
dp=[True for i in range(max(A)+1)]
for i in A:
    if dp[i]==False:
        break
    else:
        for j in range(2,max(A)+1):
            dp[min(j*i,max(A))]=False
    
ans=0
for i in A:
    if dp[i]==True:
        ans+=1
if 2 in A and A[0]!=A[1]:
    print(ans+1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 

"""
3
1 1 2
のパターンが例外だった
"""

N = int(input())
A = LI()
A.sort()

table = [0 for i in range(10 ** 6 + 1)]
cnt = 0
for a in A:
    if table[a] != 0:
        pass
    else:
        cnt += 1
        for i in range(10 ** 6):
            if a * i > 2 * 10 ** 5:
                break
            table[a * i] = 1

A_dic = collections.Counter(A)
for key in A_dic.keys():
    if A_dic[key] > 1:
        cnt -= 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
saidai = A[-1]
c=0
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        del A[k+1] 
        A.insert(0,0)
        c+=2
del A[:c]
#print(A)
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        count+=1
        for j in range(1, saidai//A[k]+1):
            foo[A[k]*j] = 1
print(count)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax=A[-1]+1
    dp = [True]*Amax
    ans=0
    a_temp=0
    a_tempcheck=False
    if A[0]==1:
        ans=0
    else:
        for a in A:
            if a_temp==a:
                dp[a] = False
                if a_tempcheck==False:
                    ans-=1
                    a_tempcheck=True
                
            if dp[a]:
                ans+=1
                for i in range(a, Amax, a):
                    dp[i] = False
                a_temp=a
                a_tempcheck=False

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

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0 for _ in range(a[-1] + 1)]

for x in a:
    for j in range(x, a[-1] + 1, x):
        dp[j] += 1
for i, result in enumerate(dp):
    print(i, result)
print("#" * 15)
ans = 0
for x in a:
    #print(x)
    if dp[x] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

def func1(a):
    a.sort()
    cnt=0
    chker=[]
    for idx,i in enumerate(a):
        candiv=False
        if idx<len(a)-1 and i==a[idx+1] or idx==len(a)-1 and i==a[idx-1]:
            candiv=True
            chker.append(i)
        else:
            for j in chker:
                if j*2>i:
                    break
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
            chker.append(i)
    print(cnt)
func1(a)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
from math import *
import copy
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def bo(i):
	return ord(i)-ord('a')
from copy import *
from bisect import *	

from itertools import permutations 



n=fi()
a=li()
d={}
a.sort()
for i in a:
	if i not in d:
		d[i]=0
	d[i]+=1
ans=0	

for i in a:
	flag=1
	for j in range(1,int(sqrt(i))+1):
		if i%j==0:
			if j in d  :
				flag=0
				break
			if i//j in d :
				if (j==1 and d[i]>1) or j>1:
					flag=0
					break


	ans+=flag
print(ans)

Submission status: Wrong Answer

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

if np.all(a==a[0]):
    print(0)
else:
    for i in range(1,len(dp)):
        if dp[i] and i in a:
            for j in np.arange(i*2, len(dp), i):
                dp[j] = False
    print(np.count_nonzero(dp[a] == True))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

def ii():
    return int(input())

def main():
    N = ii()
    A = list(mi())
    k = max(A)+1
    l = [True]*k
    l[0] = l[1] = False
    cnt = 0
    A.sort()
    c = Counter(A)
    for a in A:
        i = 2
        while a*i < k:
            l[a*i] = False
            i += 1
    for a in A:
        if l[a] and c[a] == 1:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
N = a=int(input())
listP=[]
while True:
    try:
        listP=list(map(int,input().split()))
    except:
        break;
        
listTF=[1]*N
listP.sort()
for i in range(N):
  if listTF[i]==0:
    break
  for j in range(N):
    print("i:",i)
    if (i!=j) and (listP[i]%listP[j]==0):
      listTF[i]=0
      break

print(len([i for i in listTF if i > 0]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections


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


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

S = list(set(A))

dp = [True] * (A[-1]+1)
max_a = A[-1]
P = {}

for i in range(1, max_a+1):
    P[i] = 0

for i in range(2, int((max_a**0.5//1)+1)):
    index = 1
    if dp[i] == False: continue
    P[i] = 1
    while True:
        dp[i*index] = False
        index += 1
        if i * index > max_a: break


for i in range(2, max_a+1):
    if dp[i] == True: P[i] = 1


if 1 in A:
    if A.count(1) == 1:
        print(1)
    else:
        print(0)
    exit()

ret = 0
D = collections.Counter(A)

A = list(set(A))
 
for a in D.keys():
    if P[a] == 1:
        if D[a] == 1:
            ret += 1
        continue
    
    f = make_divisors(a)
    flag = True
    for f2 in f[2:]:
        if D[f2] == 0: continue
        else: flag = False
    if flag: ret += 1
 
 
print(ret)

Submission status: Wrong Answer

Solution code:
import bisect as bc

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

dp = [True for _ in range(A[-1]+1)]

for i in range(N):
    ai = A[i]
    if 2*ai <= A[-1] and dp[2*ai]:
        for j in range(2,A[-1]+1):
            if ai*j > A[-1]:
                break
            dp[ai*j] = False

ans = 0
finish = [True for _ in range(A[-1]+1)]
for i in range(N):
    if dp[A[i]] and finish[A[i]]:
        if bc.bisect_right(A,A[i]) - bc.bisect_left(A,A[i]) == 1:
            ans += 1
            finish[A[i]] = False

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter



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

flg = [0] * (10**6+1)

ans = 0
for i in range(1,10**6+1):
    if counter[i] == 0:
        continue
    if flg[i] == 0 and counter[i] == 1:
        ans = ans + 1
    for j in range(1,(10**6+1)//i):
        flg[i*j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

def ii():
    return int(input())

def main():
    N = ii()
    A = list(mi())
    k = max(A)+1
    l = [True]*k
    l[0] = l[1] = False
    cnt = 0
    A.sort()
    c = Counter(A)
    for a in A:
        i = 2
        while a*i < k and l[a*i]:
            l[a*i] = False
            i += 1
    for a in A:
        if l[a] and c[a] == 1:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 初期入力
import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
A_np =np.array(A,dtype=np.int64)
count =set()
for i in range(N):
    a_mod =np.where(A_np %A_np[i] ==0)
    aa =A_np[a_mod]
    a_self =np.where(aa==A_np[i])  
    a_count =np.delete(aa,a_self)
    a_count = a_count.tolist()
    count |= set(a_count)      
ans =len(A_set - count)
print(ans)

Submission status: Wrong Answer

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

MAX = 1000005
cnt = [0] * MAX
for x in a:
    for i in range(x, MAX, x):
        cnt[i] += 1
ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n = int(input())
a = list(set(map(int, input().split())))
a.sort()
l = len(a)
dp = [True for _ in range(a[-1])]

for x in a:
    for j in range(x * 2, a[-1] + 1, x):
        dp[j - 1] = False
#for i, result in enumerate(dp):
#    print(i, result)
#print("#" * 15)
ans = 0
for x in a:
    #print(x)
    if dp[x - 1] == True:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import bisect

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


def main():
  N = I()
  P = LI()
  P.sort()
  #print(P)
    
  PP = [0]*N
  
  for i,n in enumerate(P):
    #print("i=",i)
    if PP[i] == 0:
      for j in range(i+1,N):
        _gcd = math.gcd(n, P[j])
        if 1 != _gcd and _gcd == n:
          PP[j] = 1
  
  #print(PP)
  for i,p in enumerate(P):
    if P.count(p) != 1:
      PP[i] = 1
      
  print(PP.count(0))
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
saidai = max(A)
c=0
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        del A[k+1] 
        A.insert(0,0)
        c+=2
del A[:c]
#print(A)
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        count+=1
        for j in range(1, saidai//A[k]+1):
            foo[A[k]*j] = 1
print(count)

Submission status: Wrong Answer

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

X = [0] * (ma + 1)
ans = 0
A.sort()

for a in A:
    X[a] += 1
for a in A:
    if X[a] > 1:
        continue
    else:
        ans += 1
        num = 1
        while num * a <= ma:
            X[num * a] += 2
            num += 1

print(ans)

Submission status: Wrong Answer

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

M = max(A)
dp = [True] * (M + 1)
ans = 0

for i in A:
    for j in range(2 * i, M + 1, i):
        dp[j] = False

for i in A:
    if dp[i]:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter



N = input()
A=list(map(int,input().split()))
B=list(set(A))
C= sorted(B)
l = len(C)

flg = [0] * (10**6+1)

if 1 in C:
    print(0)
    exit()

ans = 0
counter = Counter(C)
for i in range(1,10**6+1):
    if counter[i] == 0:
        continue
    if flg[i] == 0 and counter[i] > 0:
        ans = ans + 1
    for j in range(1,(10**6+1)//i):
        flg[i*j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
def divisors(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return sorted(ass) #sortされていない


N = int(input())
A = [int(a) for a in input().split()]
X = [0] * 1000001
for a in A:
    X[a] += 1

ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
#n = 2 * 10**5
#a = [i for i in range(1, n+1)]

a.sort()
def Eratosthenes(x):
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in range(1, nmax+1):
        if not is_prime[i]:
            continue
        if i in x:
            for j in range(i*2, nmax+1, i):
                is_prime[j] = False
    for i in range(1, nmax+1):
        if is_prime[i] == True and i in a:
            cnt += 1
    print(cnt)

Eratosthenes(a)

Submission status: Wrong Answer

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

M = max(A)
dp = [True] * (M + 1)
ans = 0

for i in A:
    for j in range(2 * i, M + 1, i):
        dp[j] = False

for i in A:
    if dp[i]:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#import numpy as np
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう
remove_list = []

kouho = [x for x in set(A) if A.count(x) == 1]
maxA = 2*(10**5)

##target = kouho[:]
#if kouho != []:
#    maxA = max(kouho)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN+1):
        buf = A[i]*n
        remove_list.append(buf)
            #print(A[i]*n)

#target = kouho[:]
kouho = list(set(kouho) - set(remove_list))
print(len(kouho))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
set(a)
dp = [True]*n
 
for i in range(n-1):
    for j in range(1,n-i):
        if a[i+j]%a[i] == 0:
            dp[i+j] = False

print(sum(dp))