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:
from collections import defaultdict

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

bool_list = [True] * (10 ** 6)

duplicate_dic = defaultdict(int)
for a in A:
    duplicate_dic[a] += 1
    if duplicate_dic[a] > 1:
        bool_list[a - 1] = False

for a in A_sort:
    for i in range(2*a, 10 ** 6, a):
        bool_list[i - 1] = False

print(sum([1 for a in A if bool_list[a - 1]]))

Submission status: Wrong Answer

Solution code:
n=int(input())
a = list(map(int, input().strip().split()))
a.sort()
lim=10**6+3
ans=0
multiples=[False]*lim

for i in range(n):
    if multiples[i]==True:
        continue
    if i!=n-1 and a[i]==a[i+1]:
        pass
    else:
        ans+=1

    for j in range(a[i],lim,a[i]):
        multiples[j]=True
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

bool_list = [True] * (10 ** 6)

duplicate_dic = defaultdict(int)
for a in A:
    duplicate_dic[a] += 1
    if duplicate_dic[a] > 1:
        bool_list[a - 1] = False

for a in A_sort:
    for i in range(2*a, 10 ** 6, a):
        bool_list[i - 1] = False

print(sum([1 for a in A_sort if bool_list[a - 1]]))

Submission status: Wrong Answer

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

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

Eratosthenes(a)

Submission status: Wrong Answer

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

for a in A:
	B[a] += 1

if max(B) == N:
	print(0)
else:
	for a in A:
		if B[a] > 0:
			i = 2
			b = a * i
			while b <= M:
				B[b] = 0
				i += 1
				b = a * i
	for i in range(len(B)):
		if B[i] > 1:
			B[i] = 0
	print(sum(B))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
result=0
flug = 0
if(len(a) == 1):
    print(1)
else:
    a.sort()
    dp = [True] * a[-1]
    flug = 1
    for j in range(n):
        if(dp[a[j]-1] == True):
            if(a[j] == a[j-1]):
                if(flug == 0):
                    result-=1
                    flug = 1
            else:
                print(a[j])
                result+=1
                flug = 0
            k = a[j] * 2
            while(k-1 < len(dp)):
                dp[k-1] = False
                k+=a[j]
                
    print(result)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

bool_list = [True] * (10 ** 6)

for duplicate_a in [a for a, cnt in Counter(A).items() if cnt >= 2]:
    bool_list[duplicate_a - 1] = False

for a in A_sort:
    for i in range(2*a, 10 ** 6, a):
        bool_list[i - 1] = False

print(sum([1 for a in A_sort if bool_list[a - 1]]))

Submission status: Wrong Answer

Solution code:
N = int(input())
a_list = [int(i) for i in input().split()]
count = 0
for i in a_list:
    flag_list = [j for j in a_list if i % j == 0]
    if len(flag_list) > 1:
        count += 1
    
print(count)

Submission status: Wrong Answer

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

for a in A:
    B[a] += 1

if max(B) == N:
    print(0)
else:
    for a in A:
        if B[a] > 0:
            i = 2
            b = a * i
            while b <= M:
                B[b] = 0
                i += 1
                b = a * i
    for b in B:
        if B[b] > 1:
            B[b] = 0
    print(sum(B))

Submission status: Wrong Answer

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

a.sort()
def Eratosthenes(x):
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in a:
        if not is_prime[i]:
            continue
        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 set(x):
            cnt += 1
    print(cnt)

Eratosthenes(a)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    A = list(set(A))
    if len(A) == 1:
        print(0)
        return

    A.sort()
    A_max = A[-1]
    divisible = [False] * (A_max + 1)

    for i in A:
        for j in range(2 * i, A_max+1, i):
            divisible[j] = True

    ans = 0
    for i in A:
        if not divisible[i]:
            ans += 1
        
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import math
def isPrime(n):
  if n == 1:
    return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False
  return True

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

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

if A[0] == 1 and A[1] == 1:
  print(0)
  exit()
if A[0] == 1 and A[1] != 1:
  print(1)
  exit()

for i in range(N):
  x = A[i]
  if isPrime(x):
    if i - 1 >= 0 and x == A[i - 1]:
        cnt -= 1
        continue
    if i + 1 < N and x == A[i + 1]:
        cnt -= 1
        continue
    continue
    
  for j in range(min(i + 1, N)):
    if i == j:
      continue
    y = A[j]
    if x % y == 0:
      cnt -= 1
      break
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = map(int, input().split())
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        t = 2
        while a * t <= maxA:
            D[a * t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = np.array([int(i) for i in input().split()])

    max_dp = np.max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")

    for a in A:
        if dp[a] >= 2:
            continue
        fancy = np.arange(a, max_dp, a)
        dp[fancy] += 2
        dp[a] -= 1


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    """"ここに今までのコード"""

    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    count = 0
    while a != []:
        t = a[0]
        if len(a) == 1:
            count +=1
        elif a[0] != a[1]:
            count +=1
        a = [i for i in a if i % t != 0]
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [0] * (2 * 10 ** 5 + 1)
M = max(A)

for a in A:
  pass

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [0] * (2 * 10 ** 5 + 1)
M = max(A)

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
has_prime_factor = [0] * (maxval+1)
has_prime_factor[0] = 2
has_prime_factor[1] = 2
for i in range(n):
    if a[i] == 1:
        continue
    if has_prime_factor[a[i]] > 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        has_prime_factor[k] += 1

result = sum(has_prime_factor[v] <= 1 for v in a)
print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
a_list = [int(i) for i in input().split()]
count = 0
for i in a_list:
    flag_i = True
    for j in a_list:
        if  i is j:
            pass
        elif  i % j == 0:
            flag_i = False
    
    if flag_i:
        count += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    A = list(set(A))
    if len(A) == 1:
        print(0)
        return

    A.sort()
    A_max = A[-1]
    divisible = [False] * (A_max + 1)

    for i in A:
        j = 2
        while i * j <= A_max:
            divisible[i * j] = True
            j += 1

    ans = 0
    for i in A:
        if not divisible[i]:
            ans += 1
        
    print(ans)

if __name__ == '__main__':
    resolve()

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
has_prime_factor = [0] * (maxval+1)

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

result = sum(has_prime_factor[v] <= 1 for v in a)
print(result)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
A = sorted(list(map(int, input().split()))) + [0]

memo = ['Yes'] * (10**6+1)
ans = 0
 
for i in range(N):
    if memo[A[i]] == 'No' or A[i] == A[i+1]:
        continue
    for j in range(A[i], max(A)+1, A[i]):
        memo[j] = 'No'
    ans += 1
 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]

a = sorted(a)

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

count =0

for i in a:
    if ac[i]>0:
        print(i)
        if ac[i] == 1:
            count += 1
        for j in a:
            if j%i==0 :
                ac[j]=0


print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [False] * (A[-1]+1)

for a in A:
    B[a] = True

for i in range(len(A)):
    a = A[i]
    if A[i-1] != A[i] and B[a] == True:
        for x in range(2*a, len(B), a):
            B[x] = False
    elif A[i-1] == A[i]:
        B[a] = False

print(sum(B))

Submission status: Wrong Answer

Solution code:
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = sorted(ZZ())
    cA = collections.Counter(A)
    MAX_A = 10 ** 6
    is_ok = [True] * (MAX_A + 1)

    if 1 in cA.keys():
        if cA[1] == 1: print(1)
        elif cA[1] >= 2: print(0)
        return

    for a in A:
        if not is_ok[a]: continue
        if cA[a] >= 2:
            is_ok[a] = False
            continue
        for i in range(2, MAX_A + 1):
            if a * i > MAX_A: break
            is_ok[a * i] = False

    ans = 0
    for a in range(MAX_A + 1):
        if is_ok[a] and a in cA.keys(): ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
try:
  n  = int(input())
  As = list(map(int, input().split()))
  As.sort(reverse=True)
  ans = 0
  
  for i in range(n):
    flag = True
    if As[i] in As[0:i] or As[i] in As[i+1:n]:
        flag = False
        break
    	
    for j in range(n-1,i,-1):
      #print(As[i], As[j])
             
      if As[i] % As[j] == 0:
        flag = False
        break
    #print(flag)
    if flag:
      ans += 1
  print(ans)
except EOFError:
  print(x)

Submission status: Wrong Answer

Solution code:
try:
  n  = int(input())
  As = list(map(int, input().split()))
  As.sort(reverse=True)
  ans = 0
  
  for i in range(n):
    flag = True
    if As[i] in As[0:i] or As[i] in As[i+1:n]:
        flag = False
        break
    	
    for j in range(n-1,i,-1):
      #print(As[i], As[j])
             
      if As[i] % As[j] == 0:
        flag = False
        break
    print(flag)
    if flag:
      ans += 1
  print(ans)
except EOFError:
  print(x)

Submission status: Wrong Answer

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

l.sort()
maxnum=l[len(l)-1]
flag=[0]*(maxnum+1)

for num in l:
    flag[num]+=1
    if flag[num]>1:
        continue
    for j in range(num*2, maxnum, num):
        flag[j]+=1
#print(flag)
ans=0

for num in l:
    if flag[num]==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
l=np.zeros(max(a)+1)
a.sort()
r=0
for i,j in zip(a,a[1:]):
    if l[i]==0:
        l[::i]=1
        if i!=j:
            r+=1
print(r)

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 = [0] * (maxval+1)

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

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

Submission status: Wrong Answer

Solution code:
def main():
  n, *A = map(int, open(0).read().split())
  m = max(A)
  lst = [0] *(m + 1)
  prep = 0
  for i in A:
    if i == prep:
      lst[i] += 1
      continue
    lst[2 * i::i] = [1] * len(lst[2 * i::i])
    prep = i
  res = 0
  for i in A:
    if lst[i] == 0:
      res += 1
  print(res)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
l=np.zeros(max(a)+1)
a.sort()
a+=[10**7]
r=0
for i,j in zip(a,a[1:]):
    if l[i]==0:
        l[::i]=1
        if i!=j:
            r+=1
            print(i)
print(r)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=True)
NG = 0

for i in range(N):
    for j in range(i+1, N):
        if A[i] == A[i-1]:
            NG += 1
            break
        else:
            if A[i] % A[j] == 0:
                NG += 1
                break

if A[0] == A[N-1]:
    NG += 1

res = N - NG
print(res)

Submission status: Wrong Answer

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

a.sort()
if a[0] == 1:
    if len(a) == 1 or a[1] != 1:
        print(1)
    else:
        print(0)
else:
    a_max = a[-1]
    seive = [True for _ in range(a_max + 1)]
    a += [-1]
    ret = 0
    add = 1
    for i in range(n):
        if a[i] != a[i+1]:
            if seive[a[i]]:
                ret += add
                add = 1
                j = 2 * a[i]
                while j <= a_max:
                    seive[j] = False
                    j += a[i]
        else:
            add = 0
    print(ret)

Submission status: Wrong Answer

Solution code:
import math


def dellist(items, indexes): return [
    item for index, item in enumerate(items) if index not in indexes]


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

li.sort()

# maxval = 10 ** 6

# li2 = list(set(li))

cnt = [0 for i in range(10**6)]
for i in range(n):
    cnt[li[i]-1] += 1
# print(cnt)

unique = list(set(li))
unique.sort()

# dp = [1 for i in range(maxval)]

i = 0
while 1:
    # if unique[i] > math.sqrt(maxval):
    #     break
    to_be_dropped = []
    for j in range(i+1, len(unique)):
        if unique[j] % unique[i] == 0:
            # dp[unique[j]-1] = 0
            to_be_dropped.append(j)
    unique = dellist(unique, to_be_dropped)
    i += 1
    if i >= len(unique):
        break
print(unique)

c = 0
for i in range(len(unique)):
    if cnt[unique[i]-1]>=2:
        c += 1
print(len(unique) - c)

Submission status: Wrong Answer

Solution code:
def main():
  n, *A = map(int, open(0).read().split())
  m = max(A)
  lst = [0] *(m + 1)
  prep = 0
  for i in A:
    if i == prep:
      lst[i] += 1
    lst[2 * i::i] = [1] * len(lst[2 * i::i])
  res = 0
  for i in A:
    if lst[i] == 0:
      res += 1
  print(res)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
try:
  n  = int(input())
  As = list(map(int, input().split()))
  As.sort(reverse=True)
  ans = 0
  
  for i in range(n):
    flag = True
    for j in range(i+1,n):
      # print(As[i], As[j])
       
      if As[i] == As[j]:
        flag = False
        break
             
      if As[i] % As[j] == 0:
        flag = False
        break
    if flag:
      ans += 1
  print(ans)
except EOFError:
  print(x)

Submission status: Wrong Answer

Solution code:
def resolve():
	N = int(input())
	A = list(map(int, input().split()))
	a_max = 10**6
	B = [0] * (a_max+1)
	for i in range(N):
		a = A[i]
		for j in range(a, a_max, a):
			B[j] += 1
	Y = 0
	for a in A:
		if B[a]==1:
			Y+=1
	print(Y)
resolve()

Submission status: Wrong Answer

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

T = [False]*(10**6+1)
for i in A:
    # iの2以上の倍数の値はTrueに
    for j in range(i*2, 10**6, i):
        T[j] = True

# ダブってる値は2以上に
D = [0]*(10**6+1)
for i in A:
    D[i] += 1

# TがFalseかつDが1の数を数える
ans = 0
for i in A:
    if T[i] == False and D[i] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
furui = [False] * (10**6+1)
ans = 0
for i in range(n):
    if i-1 >= 0 and a[i] == a[i-1]:
        continue
    if i+1 < n and a[i] == a[i+1]:
        continue
    if furui[a[i]] == False:
        ans += 1
        now = a[i]
        while now <= 10**6:
            furui[now] = True
            now += a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
s = set()
ans = 0
for i in sorted(set(a)):
    if c[i]==1:
        j=i*2
        while j<=1000000:
            s.add(j)
            j+=i
        if i not in s:
            ans+=1
            
print(ans)

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: "List[int]"):
    counts = {}
    for a in A:
        if not a in counts:
            counts[a] = 0
        counts[a] += 1

    M = max(A)
    s = set(A)
    ret = 0
    used = [False] * (M + 1)
    for i in range(1, M + 1):
        if used[i]:
            continue
        if not i in s:
            continue
        if counts[a] == 1:
            ret += 1
        j = 1
        while i * j <= M:
            used[i * j] = True
            j += 1
    print(ret)


def _hoge(N, A):
    for i, v in enumerate(A):
        if used[i]:
            continue
        if not (i < N - 1 and v == A[i + 1]):
            ret += 1
        for j in range(i + 1, N):
            if A[j] % v == 0:
                used[j] = True
    print(ret)


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:
n = int(input())
a = list(map(int, input().split()))

a.sort()
def Eratosthenes(x):
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in a:
        if not is_prime[i]:
            continue
        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:
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    cnt = 0
    div = []

    for i in range(n):
        # print(div)
        if i < n - 1 and a[i] == a[i + 1]:
            continue
        if i == 0:
            cnt += 1
        else:
            for j in range(len(div)):
                # print(div[j], a[i])
                if div[j] > (a[i] + 1) / 2:
                    cnt += 1
                    break
                if a[i] % div[j] == 0:
                    break
                if j == len(div) - 1:
                    cnt += 1
        div.append(a[i])
        # for j in range(n):
        #     if i != j:
        #         if a[i] % a[j] == 0:
        #             break
        #     if j == n - 1:
        #         cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
 
A_list = [int(n) for n in input().split()]
 
import numpy as np
 
A_array = np.array(A_list)
sort_A = np.sort(A_array)

n_array = np.zeros(10**6)
  
for a in sort_A:
    
    if n_array[a - 1] >= 2:
        continue
        
    a_times = np.array(range(a, 10**6+1, a))
    
    n_array[(a_times -1).astype(int)] += 1

(n_array[sort_A - 1] == 1).sum()

Submission status: Wrong Answer

Solution code:
from collections import Counter
M=10**7
_,*l=sorted(map(int,open(0).read().split()))
d=[1]*(M)
C=Counter(l)
s=0
for a,b in C.items():
    if b != 1:d[a]=0
    elif d[a]:s+=1
    for j in range(a,M,a):d[j]=0
print(s)

Submission status: Wrong Answer

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

    s_a.sort()

    dub_a = [0]*max(s_a)

    for i in l_a:
        dub_a[i-1] += 1

    dp = [1]*max(s_a)

    for i in s_a:
        if 2*i > 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 s_a:
        if dp[i-1]==1 and dub_a[i-1]==1:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
M=10**6+1
_,*l=sorted(map(int,open(0).read().split()))
d=[1]*(10**6+1)
C=Counter(l)
s=0
for a,b in C.items():
    if b != 1:d[a]=0
    elif d[a]:s+=1
    for j in range(a,M,a):d[j]=0
print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
#print(a)
b = [True]*n
for i in range(n):
  #print(i)
  if b[i] ==True:
    for j in range(n-1-i):
    #print(i+j+1)
      if a[i+j+1] % a[i] ==0:
        #print(i+j+1)
        b[i+j+1] = False
print(b.count(True))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

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

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

A = list(map(int, input().split()))
A = [x for x in set(A) if A.count(x) == 1]
if len(A) <= 1:
    print(len(A))
    sys.exit()
A= sorted(A)    
max = A[-1]
memo = ['Y'] * (10**6+1)
ans = 0
 
for i, A_i in enumerate(A):
    if memo[A_i] == 'N':
        continue
    for j in range(A_i, max+1, A_i):
        memo[j] = 'N'
    ans += 1
    
print(ans)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    n = I()
    mylist = sorted(list(MI()))
    max_num = mylist[n-1] // 2
    start = mylist[0]
    input_list = [0] * n
    index = 0

    while len(mylist) >= 1:
        temp = mylist.pop(0)
        if not(temp in mylist):
            index += 1
        for j in set(mylist):
            if j % temp == 0:
                while j in mylist:
                    mylist.remove(j)
        if len(mylist) >= 1 and mylist[0] > max_num:
            break
    print(index+len(mylist))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os
import math
import collections

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 素因数分解モジュール
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    n = int(input())

    a_list = list(map(int, input().split()))
    a_list.sort()
    a_list = list(set(a_list))

    if len(a_list) == 1:
        print(0)
        return

    if a_list[0] == 1:
        print(n - 1)

    usage_prime_list = [False for i in range(1000001)]
    ans = 0
    for a in a_list:
        append = True
        counter = collections.Counter(prime_factorize(a))
        for key, val in counter.items():
            for i in range(1, val+1):
                if usage_prime_list[pow(key, i)]:
                    append = False
        if append:
            ans += 1

        usage_prime_list[a] = True

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

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 set(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())
li = list(map(int,input().split()))
li.sort()
cnt = 0


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

for i in li:
    for j in range(i,10**6+1,i):
        if cnt_li[j-1] > 1:
            break
        else:
            cnt_li[j-1] += 1

for k in li:
    if cnt_li[k-1] == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    cnt = 0
    div = []

    for i in range(n):
        if i < n - 1 and a[i] == a[i + 1]:
            continue
        if i == 0:
            cnt += 1
        else:
            for j in range(len(div)):
                if a[i] % div[j] == 0:
                    break
                if j == len(div) - 1:
                    cnt += 1
        div.append(a[i])
        # for j in range(n):
        #     if i != j:
        #         if a[i] % a[j] == 0:
        #             break
        #     if j == n - 1:
        #         cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
OKlist = [0]*(10**6+100)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        continue
    elif OKlist[A[i]] == 0:
        for j in range(1,10**6+10):
            if A[i]*j > 10**6:
                break
            else:
                OKlist[A[i]*j] += 1
    else:
        OKlist[A[i]] += 1
OKlist[max(A)] += 1
cnt = 0
for i in A:
    if OKlist[i] == 1:
        cnt += 1
        
        
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
OKlist = [0]*(10**6+100)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        continue
    elif OKlist[A[i]] == 0:
        for j in range(1,10**6+10):
            if A[i]*j > 10**6:
                break
            else:
                OKlist[A[i]*j] += 1
    else:
        OKlist[A[i]] += 1
OKlist[max(A)] += 1
cnt = 0
for i in A:
    print(OKlist[i])
    if OKlist[i] == 1:
        cnt += 1
        
        
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
#print(a)
b = [True]*n
for i in range(n):
  #print(i)
  if b[i] ==True:
    for j in range(n-2-i):
    #print(i+j+1)
      if a[i+j+1] % a[i] ==0:
        #print(i+j+1)
        b[i+j+1] = False
print(b.count(True))

Submission status: Wrong Answer

Solution code:
M=10**6+1
A=[0]*M
_,*l=sorted(map(int,open(0).read().split()))
for i in l:
    A[i]+=1
    if A[i]==1:
      for j in range(2*i,M,i):A[j]+=9
print(A.count(1))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

N = int(input())
 
A = list(map(int, input().split()))
A = [x for x in set(A) if A.count(x) == 1]
if len(A) <= 1:
    print(len(A))
    sys.exit()
 
A = np.array(sorted(A))
B = np.array([A[0]])
 
for i in range(len(A)-1):
    if np.all(A[i+1] % B != 0):
        B = np.append(B, A[i+1])
print(len(B))