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
from collections import Counter

n = int(input())
A = sorted(map(int, input().split()))
U = 10**6
B = [1]*(U+1)
C = Counter(A)
ans = 0
for a in A:
  if C[a] > 1:
    continue
  ans += C[a]
  for j in range(a, U+1, a):
    C[j] = 0
print(ans)

Submission status: Wrong Answer

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(d)                        
                                          
print(ans - len(dup))

Submission status: Wrong Answer

Solution code:
import copy

N = input()
data = input().split()
original = data.copy()
data2 = original.copy()

res_count = 0
loop_count = 0

for num in data:
    flag = 0
    olddata = []
    data2 = original.copy()
    data2.pop(loop_count)
#   print(original)
#   print(data2)
    for num2 in data2:
        if num2 in olddata:
            break
        if (int(num) % int(num2)) == 0:
            flag = 1
        olddata.append(num2)

    if flag == 0:
        res_count += 1
 #       print('num = {}  num 2 = {}'.format(num,num2))

    loop_count += 1
    
print(res_count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(sorted(list(map(int,input().split()))))
sosuu = []
hukusuu = []

for i in range(len(a_list)-1,0,-1):
  if a_list[i] == a_list[i-1]:
    hukusuu.append(i)
    hukusuu.append(i-1)
    
hukusuu = sorted(list(set(hukusuu)),reverse=True)
for i in hukusuu:
  a_list.pop(i)

if len(a_list) == 0:
  print(0)
else:
  a_list = sorted(a_list)
  biggest = a_list[-1]
  dp = [True for i in range(biggest+1)]
  for i in a_list:
    count = biggest // i
    for j in range(2,count+1):
      dp[j*i] = False
  ans = 0
  for i in a_list:
    if dp[i] == True:
      ans += 1
  print(ans)

Submission status: Wrong Answer

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

if n==1:
    print(1)
    exit()
if len(set(a)) == 1:
    print(0)
    exit()

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

ans=0
for num in a:
    if num in fins:
        dups.add(num)
        continue
    if dp[num]==0:
        ans+=1
    fins.add(num)


print(ans-len(dups))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split(" ")))
c = 0
A = sorted(A)
for i in range(N):
  judge = True
  for j in range(N):
    if A[i]%A[j] == 0:
      judge = False
      break
  if judge:
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if ok[i] == 1:
        continue
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1
    if a[i] < 2 * 10:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:
        times = 1
        while a[i] * times < a[-1]:
            r = bisect.bisect_left(a, a[i] * times)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Wrong Answer

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

for a in A:
  B[a]+=1
  if B[a]==1:
    for n in range(2*a,10**6+1,a):
      B[n]+=1

print(B.count(1))

Submission status: Wrong Answer

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

import math

M = [0] * (10 ** 6)

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

avg = sum(A)/len(A)
if avg == A[0]:
	print(0)
else:
	ans = 0
	for i in range(N):
		if M[A[i]] == 1 or is_prime(A[i]):
			ans += 1
			M[A[i]] = 1

		else:
			for j in range(N):
				if i != j:
					if A[i] % A[j] == 0:
						break
				if j == N - 1:
					ans += 1
					M[A[i]] = 1
	print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    from math import gcd
    n, *a = map(int, open(0).read().split())
    x = Counter(a)
    y = [k for k, v in x.items() if v == 1]
    if len(y) == 0:
        print(0)
        exit()

    z = sorted(y)

    if z[0] == 1:
        print(1)
        exit()

    m = [0] * (z[-1] + 1)
    l = len(m)
    for i in z:
        if m[i] == -1:
            continue
        m[i] = 1
        j = (l - 1) // i
        for k in range(2, j + 1):
            m[i * k] = -1

    ans = m.count(1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

a = sorted(a)
dic = defaultdict(lambda: False)

count = 0 

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

for i in range(n):
    ai = a[i]
    if dic[ai] == True:
        count+=1
    else:
        for j in range(1,a[n-1]):
            dic[j*ai] = True
        if i+1 < n and a[i]==a[i+1]:
            count+=1
print(n-count)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

def main():
    n = int(input())

    A = Counter(map(int, input().split()))
    A = sorted(k for k, v in A.items() if v == 1)

    if not A:
        print(0)
        return

    ans = 0
    maxi = max(A)
    cache = set()
    for a in A:
        if a in cache:
            continue

        x = a
        while x <= maxi:
            cache.add(x)
            x += a
        ans += 1

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
counter_set=set()
a=list(set(a))
a.sort()
if 1 in a:
    print(1)
elif len(set(a))==1:
    print(0)
else:
    for j in range(len(a)):
        for i in range(2, int(a[j]**0.5)+1):
            if a[j] % i == 0:
                if i in counter_set:
                    break
                if i != a[j] // i:
                    if a[j]//i in counter_set:
                        break
        else:
            counter_set.add(a[j])
                
    print(len(counter_set))

Submission status: Wrong Answer

Solution code:
import collections


def main():
    n = int(input())
    al = list(map(int, input().split()))
    al.sort()

    dp = [1]*(10**6+1) 
    for a in al:
        if dp[a]:
            dp[a] -= 1
            for i in range(2,10**6//a + 1):
                dp[a*i] -= 2
    
    ans = 0
    for a in al:
        if dp[a] >= 0: 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(reverse=True)
d={}

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

else:
    p_check=[0 for _ in range(A[0]+1)]
    dif=0
    for a in d:
        if d[a]>1:
            dif+=1
        p_check[a]=1
        n=2
        if a*n<=A[0]:
            while a*n<=A[0]:
                p_check[a*n]=0
                n+=1
    ans=sum(p_check)-dif
print(ans)

Submission status: Wrong Answer

Solution code:
# # -*- coding: utf-8 -*-
import collections
N = int(input())
A = list(map(int, input().split(' ')))

a_frq_dict = collections.Counter(A)
A = sorted(a_frq_dict.keys())

bads = set()
max_a = max(A)
n = len(A)
for i in range(n):
    if A[i] in bads:
        continue
    elif a_frq_dict[A[i]] > 1:
        bads.add(A[i])
        continue

    a = A[i]
    for a in range(A[i]*2, max_a+1, A[i]):
        if a in a_frq_dict:
            bads.add(a)

answer = set(A) - bads
# print(answer)
print(len(answer))

Submission status: Wrong Answer

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

ans = 0
A = [True]*(10**6+1)

for i in range(0, N):
    if not A[S[i]]:
        continue
    if 0 < i:
        if S[i-1] == S[i]:
            continue
    if i < N-1:
        if S[i] == S[i+1]:
            for j in range(1, 10**6//S[i]+1):
                A[S[i]*j] = False
    ans += 1
    for j in range(1, 10**6//S[i]+1):
        A[S[i]*j] = False

print(ans)

Submission status: Wrong Answer

Solution code:
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

N = int(input())
parts = dict()
r = set()
for x in sorted(map(int, input().split())):
    f = factorization(x)
    for i, cnt in f:
        if i in parts and parts[i] <= cnt:
            if x in r:
                r.remove(x)
            break
    else:
        r.add(x)
    if len(f) == 1:
        i, cnt = f[0]
        if i not in parts:
            parts[i] = cnt
print(len(r))

Submission status: Wrong Answer

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

sorted_A = sorted(A)
result = 0

# 倍数を管理するテーブル
lendp = sorted_A[-1] + 1
dp = [True] * lendp

if N == 1:
    print(0)
else:
    for a in sorted_A:
        if dp[a] and sorted_A.count(a) == 1:
            result += 1
        while a < lendp:
            dp[a] = False
            a += a

    print(result)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict, Counter

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    cA = Counter(A)
    Amax = max(A)
    dp = [True] * (Amax + 1)

    bl = set()
    for k, v in cA.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in set(A):
        if a not in bl and dp[a]:
            ans += 1
        for k in range(1, 100000):
            if Amax < a * k:
                break
            dp[a * k] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

alist = input().split(' ')
for i in range(n):
    alist[i] = int(alist[i])

unique = [x for x in set(alist) if alist.count(x) == 1]
if len(unique) == 0:
    print(0)
    exit()
unique.sort()
count = 1
while len(unique) > 1:
    count +=1 
    x = unique[0]
    blist = unique[1:]
    unique = []
    for j in blist:
        if not j%x == 0:
            unique.append(j)
print(count)

Submission status: Wrong Answer

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

dlen = A[-1]+1
d = [True]*dlen
for a in A:
    if d[a]:
        for i in range(a*2, dlen, a):
            d[i] = False

res = 0
for i in range(N):
    if i > 1:
        if A[i] == A[i-1]:
            continue
    if i < N-1:
        if A[i] == A[i+1]:
            continue
    if d[A[i]]:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
if N == 1:
    print(1)
elif A[0] == 1 and A[1] == 1:
    print(0)
elif A[0] == 1:
    print(1)
else:
    Eratos = [False]*1000001
    ans = 0
    for i in range(N):
        if Eratos[A[i]]:
            ans += 1
        else:
            for j in range(A[i], 1000001, A[i]):
                Eratos[j] = True
    print(N-ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A.sort()
d = deque()
for i in range(N-1):
    if A[i] != A[i+1]:
        d.append(A[i])
if A[N-1] != A[N-2]:
    d.append(A[N-1])

ans = 0
max_A = max(A)
ban = [0]*(max_A+1)
while len(d):
    num = d.popleft()
    if ban[num] != 1:
        ans += 1
        ban_num = num
        while ban_num <= max_A:
            ban[ban_num] = 1
            ban_num += num

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

def main():
    n_ = int(input())

    if n_ == 1:
        print(1)
        return

    A = Counter(map(int, input().split()))
    A = sorted(k for k, v in A.items() if v == 1)

    if not A:
        print(0)
        return

    ans = 0
    maxi = max(A)
    cache = set()
    for a in A:
        if a in cache:
            continue

        x = a
        while x <= maxi:
            cache.add(x)
            x += a
        ans += 1

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def main1():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    ans=[0]*(10**6+1)
    for i in  range(len(A)):
        if ans[A[i]]!=0:
            continue
        if i < N-1 and A[i]!=A[i+1]:
            ans[A[i]]+=1
        if i == N-1:
            ans[A[i]]+=1
        for j in range(A[i]*2,10**6+1,A[i]):
                ans[j]=2
    print(ans.count(1))
main1()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    hurui = [0] * (10**7)
    prev = 0
    ex = set()
    for a in A:
        hurui[a] = 1
        if prev == a:
            ex.add(a)
        prev = a
    for i in range(1010):
        if hurui[i] == 0:
            continue
        j = 2
        while j * i <= 10**6 + 100:
            hurui[i*j] = 0
            j += 1

    print(sum(hurui) - len(ex))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import numpy as np

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

c = Counter(a)
arr = np.zeros(MAX + 1, np.int64)
for k, v in c.items():
    if v == 1:
        arr[k] = 1

for i, e in enumerate(arr):
    if e:
        arr[2 * i::i] = 0

print(arr.sum())

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True for _ in range(10**6 + 5)]
dic = {}
if len(a) == 1:
    print(0)
    exit()

for i in a:
    if i in dic:
        dic[i] += 1
        continue
    dic[i] = 0
    now = 2 * i
    while (10**6 + 3 > now):
        check[now] = False
        now += i

ans = 0
for i in a:
    if check[i] and dic[i] == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    N = int(input())
    A = map(int,input().split())

    seen = set()
    dup = set()
    ng = 0
    B = []

    for a in A:
        if not a in seen:
            B.append(a)
            seen.add(a)
        else:
            dup.add(a)

    ng += len(dup)
    N = len(B)
    out = set()
    mx = max(B)

    for b in B:
        c = 2
        while c * b <= mx:
            out.add(c * b)
            c += 1

    for b in B:
        if b in out: ng += 1


    print(N-ng)






if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a = sorted(list(set(a)))
n = len(a)
ma = max(a)

div = defaultdict(bool)
count = 0
for i in range(n):
    b = a[i]
    if div[b]:
        count += 1
    else:
        for j in range(1,ma//b+1):
            div[j*b] = True

if(n == 1):
    print(0)
else:
    print(n-count)

Submission status: Wrong Answer

Solution code:
n = int(input())
*A, = map(int, input().split())
C = {a: 0 for a in range(1, 10**6 + 1)}
for a in A:
    C[a] += 1
E = [0 for i in range(n)]
for i, a in enumerate(A):
    if C[a] > 1:
        E[i] = 1
    tmp = 1
    while tmp**2 <= a:
        if a % tmp == 0 and C[tmp] > 0:
            E[i] = 1
        if a % tmp == 0 and tmp != 1 and C[a // tmp] > 0:
            E[i] = 1
        tmp += 1
print(n - sum(E))

Submission status: Wrong Answer

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

ans = 0
A = [True]*(10**6+1)

for i in range(0, N):
    if not A[S[i]]:
        continue
    if 0 < i:
        if S[i-1] == S[i]:
            continue
    if i < N-1:
        if S[i] == S[i+1]:
            continue
    ans += 1
    for j in range(1, 10**6//S[i]+1):
        A[S[i]*j] = False

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10 ** 6 + 1)
print(cnt)
for a in A:
    if P[a] == 0:
        for i in range(10 ** 7):
            x = a * i
            if x > 10 ** 6:
                break
            P[x] = 1
        if cnt[a] == 1:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

def main():
    n_ = int(input())

    if n_ == 1:
        print(1)
        return

    A = Counter(map(int, input().split()))
    A = sorted(k for k, v in A.items() if v == 1)

    if not A:
        print(0)
        return

    ans = len(A)
    maxi = max(A)
    cache = set()
    for a in A:
        if a in cache:
            ans -= 1
            continue

        x = a
        while x <= maxi:
            cache.add(x)
            x += a

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = Counter(list(map(int,input().split(' '))))
ans = 0
m = max(A.keys())
L = [1]*(10**6+1)
for i in sorted(A.keys()):
    if A[i] > 1 or not L[i]:
        continue
    ans += 1
    for j in range(i,m+1,i):
        L[j] = 0
print(ans)

Submission status: Wrong Answer

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

#a = list(sa)
a.sort()

#print(a)
import numpy as np
U=10**6 + 5
is_prime = np.zeros(U,np.bool)
#is_prime[2] = 1
is_prime[1::] = 1
M = int(U**.5)+1
for ai in a:#range(3,M,2):
    if is_prime[ai]:
        is_prime[ai*2::ai] = 0
    #print(is_prime.nonzero()[0])

ans = 0
for ai in a:
    if is_prime[ai]:
        ans += 1

print(ans)

"""
p = list(range(10**6+10))

a = list(sa)
a.sort()

print(a)

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

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

"""

Submission status: Wrong Answer

Solution code:
import math


def read_input(trans=int):
    return list(map(trans, input().split()))


N = read_input()[0]
A = read_input()
A_r = sorted(A, reverse=True)

count = 0
while len(A_r) > 1:
    x = A_r[-1]
    rem_list = []
    for i, a in enumerate(A_r[:-1]):
        if a % x == 0:
            rem_list.append(i)
    A_r_new = []

    for i in range(len(A_r)-1):
        if i in rem_list:
            continue
        A_r_new.append(A_r[i])
    A_r = A_r_new.copy()

    if len(A_r) == 0:
        pass
    elif len(A_r) == 1:
        count += 2
    else:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a = sorted(list(set(a)))
n = len(a)
ma = max(a)

print(a)
div = defaultdict(bool)
count = 0
for i in range(n):
    b = a[i]
    if div[b]:
        count += 1
    else:
        for j in range(1,ma//b+1):
            div[j*b] = True

if(n == 1):
    print(0)
else:
    print(n-count)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = sorted(list(map(int,input().split())))
c=0
for i,x in enumerate(a):
    for y in a[i+1:]:
        if x == y:
            a.remove(y)
            continue
        if y%x == 0:
            a.remove(y)
            continue
print(len(a))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(map(int,input().split()))
s=set(A)
ran=set(range(max(A)+1))
ans=0
dp=[True]*(max(A)+1)
for i in range(N):
    if i<N-1 and A[i+1]==A[i]:
        dp[A[i]]=False
        continue
    if not dp[A[i]]:
        continue
    ans+=1
    rem=set()
    for j in ran:
        if j%A[i]==0:
            dp[j]=False
            rem.add(j)
    for x in rem:
        ran.remove(x)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
c = 0
A = sorted(A)
n_1 = A.count(1)
if n_1 == 1:
    c = 1
elif n_1 > 1:
    c = 0

for ai in A:
    if A.count(ai) > 1:
        continue
    for aj in [a for a in A if a < ai]:
        if ai % aj == 0:
            break
    else:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    hurui = [0] * (10**7)
    prev = 0
    ex = []
    for a in A:
        hurui[a] = 1
        if prev == a:
            ex.append(a)
        prev = a
    for i in range(1010):
        if hurui[i] == 0:
            continue
        j = 2
        if i in ex:
            j = 1
        while j * i <= 10**6 + 100:
            hurui[i*j] = 0
            j += 1

    print(sum(hurui))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = Counter(list(map(int,input().split(' '))))
ans = 0
m = max(A.keys())
L = [1]*(10**6+1)
for i in sorted(A.keys()):
    if A[i] > 1:
        continue
    ans += L[i]
    for j in range(i,m+1,i):
        L[j] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
seen = set()
maxN = 1e6
count = 0
for i in range(1, n):
    if arr[i] == arr[i-1]:
        seen.add(arr[i])
for num in arr:
    if num not in seen:
        count += 1
        curr = num
        while curr <= maxN:
            seen.add(curr)
            curr += num
print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True for _ in range(10**6 + 5)]
dic = {}
if len(a) == 1:
    print(0)
    exit()

for i in a:
    if i in dic:
        continue
    dic[i] = True
    now = 2 * i
    while (10**6 + 3 > now):
        check[now] = False
        now += i

ans = 0
for i in a:
    if check[i] and i not in dic:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
d={}

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

else:
    p_check=[0 for _ in range(A[0]+1)]
    dif=0
    for a in d:
        if d[a]>1:
            dif+=1
        p_check[a]=True
        n=2
        if a*n<=A[0]:
            while a*n<=A[0]:
                p_check[a*n]=False
                n+=1
    prime=[]
    for j in range(A[0]+1):
        if p_check[j]:
            prime.append(j)
    ans=len(prime)-dif
print(ans)

Submission status: Wrong Answer

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
ans = 0
for a in A:
    if dic[a] > 1: continue
    else:
        ans += 1
        idx = 1
        while a*idx <= 10**6:
            dic[a*idx] += 1
            idx += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
L = list(map(int,input().split()))
L.sort(reverse=True)
count = 0
for n in np.array(range(N)):
    if n != N-1:
        L_s = L[n+1:]
    else:
        L_s = L[n-1:n]
    for l_s in L_s:
        if L[n]%l_s == 0:
            break
    else:
        count += 1

print(count)

Submission status: Wrong Answer

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

def get_prime_factors(n):
    dd = defaultdict(lambda: 0)
    if n > 1:
        i = 2
        while i * i <= n:
            if n % i == 0:
                dd[i] += 1
                n /= i
                i = 2
            else:
                i += 1
        dd[n] += 1
    return dd

def factor_with(n, A):
    idx = 0
    orig_n = n
    i = A[idx]

    while i * i <= n or idx >= len(A):
        i = A[idx]

        if A[idx] == orig_n:
            idx+= 1
        elif n % i ==0:
            n /= i
            idx = 0
        else:
            idx += 1
    return n

    
def solve(N: int, A: "List[int]"):
    
    A = sorted(list(A))
    
    count = 0
    divs = []
    for i in range(len(A)):
        f = True

        if i + 1 < len(A):
            if A[i-1] == A[i] or A[i] == A[i+1]:
                continue
        else:
            if A[i-1] == A[i] or len(A)==1:
                continue
               

        for div in divs:
            if A[i] % div == 0:
                f = False
                break
        if f:
            divs.append(A[i])

    count = len(divs)

        
    # dd = defaultdict(lambda: (0, 10**6+1))
    
    # for a in A:
    #     d = get_prime_factors(a)

    #     flag = True
    #     for prime, value in d.items():
    #         dd_val, dd_mn = dd[prime]
            
    #         if a % dd_mn==0:
    #             flag = False
    #             break

    #         dd[prime] = (dd_val + value, min(dd_mn, a))

    #     if flag:
    #         count+= 1

    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict, Counter

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    # _, primes = sieve(100001)
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    cA = Counter(A)
    Amax = max(A)
    dp = [True] * (Amax + 1)
    checked = defaultdict(bool)

    for a in A:
        if checked[a]:
            continue
        if dp[a]:
            checked[a] = True
            for k in range(1, 100000):
                if a + k * a <= Amax:
                    dp[a + k * a] = False
                else:
                    break
            
    ans = 0
    for a in A:
        if dp[a] and cA[a] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(set(list(map(int, input().split())))), reverse=True)
n = len(A)
count = 0
for i in range(n):
    for j in range(n-1, i-1, -1):
        if i != j and A[i] % A[j] == 0:
            break
        if j == i:
            count += 1
    if i == n-1 and N != n:
        count -= 1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
line = sorted(list(map(int,input().split())))
one = 0
for i in range(n):#one 
  if line[i] == 1:
    one += 1
  else:
    break
for i in range(n):#1にする
  if line[i] != 1:
    for j in range(i+1,n)[::-1]:         
      if line[j] == line[i]:
        line[i] = 1
        line[j] = 1
      elif line[j] % line[i] == 0:
        line[j] = 1
      elif i>one-1 and line[i] == 1:
        break 
  else:
    continue
linn = sorted(line)
count = 0
for i in range(n):#count
  if line[i] !=1:
    count += 1  
count += one
print(count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

search_dict = {}
for i,j in combinations(A,2):
    search_dict[i] = search_dict.get(i,set())
    search_dict[i].add(j)
    search_dict[j] = search_dict.get(j,set())
    search_dict[j].add(i)
    
ans = len(search_dict.keys())
for key in search_dict.keys():
    for value in search_dict[key]:
        if key%value == 0:
            search_dict[key].clear()
            ans-=1
            break
print(ans)