Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

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

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

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

unique=[]

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

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

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

ans=0

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

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
maxa=max(a)
cnt=[0]*((10**6)+1)

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

unique=[]

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

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

for elem in unique:
    for i in range(elem*2,maxa,elem):
        cnt[i]=1

ans=0

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

l = [1]*len(A)

for i in range(len(A)-1):
  if A[i] > A[-1]//2:
    break
    
  if l[i] == 1:
    for j in range(i+1,len(A)):
      if A[j]%A[i] == 0:
        l[j] = 0
        
lis = [A[k] for k in range(len(A)) if l[k] == 1]
ans = len(lis)
  
c = Counter(a)
  
for k,v in c.items():
  if v >= 2:
    ans -= 1
      
print(ans)

Submission status: Wrong Answer

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

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

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

unique=[]

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

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

for elem in unique:
    for i in range(elem*2,max(a),elem):
        cnt[i]=1

ans=0

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

l = [1]*len(A)

for i in range(len(A)-1):
  if l[i] == 1:
    for j in range(i+1,len(A)):
      if A[j]%A[i] == 0:
        l[j] = 0
        
lis = [A[k] for k in range(len(A)) if l[k] == 1]
ans = len(lis)
  
c = Counter(a)
  
for k,v in c.items():
  if v >= 2:
    ans -= 1
      
print(ans)

Submission status: Wrong Answer

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

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

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

unique=[]

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

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

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

ans=0

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import sqrt
N = int(input())
A = [int(v) for v in input().split()]

m = max(A)
l = [1 for i in range(m+1)]
for v in sorted(A):
    if v > sqrt(m):break
    for j in range(2*v, m+1, v):
        l[j] = 0

ans = 0
c = Counter(A)
for a in A:
    if c[a] > 1:continue
    ans += l[a]
print(ans)

Submission status: Wrong Answer

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

dp = [0] * (mx+1)
for i in a:
    if dp[i] == 1:
        continue
    for j in range(2, mx):
        if i * j > mx:
            break
        dp[i*j] = 1

cnt = 0
for i in a:
    if dp[i] == 0 and a.count(i) == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

argv = input().split()
intList = [int(num) for num in argv]
intList.sort()

i = 0
j = 0

while i < N:
  j = i + 1
  while j < N:
    if (intList[j] % intList[i]) == 0:
      del intList[j]
      N = N - 1
    else:
      j += 1
  i += 1

print(len(intList))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

def nd():
    ans = 0
    l = [1 for _ in range(len(A))]
    
    ind = 0
    i = A[ind]
    
    while i <= A[-1]//2:
      if l[A.index(i)] == 1:
        j = 2 * i
        while j <= A[-1]:
          if j in set(A):
            l[A.index(j)] = 0
          j += i
      ind += 1
      i = A[ind]
          
    table = [A[i] for i in range(len(A)) if l[i] == 1]
    ans = len(table)
    
    dic = Counter(a)
    
    for k,v in dic.items():
      if v >= 2:
        ans -= 1
        
    return ans
  
print(nd())

Submission status: Wrong Answer

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

dp = [0] * (mx+1)
for i in sorted(set(a)):
    if dp[i] == 1:
        continue
    for j in range(2, mx):
        if i * j > mx:
            break
        dp[i*j] = 1

cnt = 0
for i in a:
    if dp[i] == 0 and a.count(i) == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

def nd():
    ans = 0
    l = [1 for _ in range(len(A))]
    print(l)
    ind = 0
    i = A[ind]
    
    while i <= A[-1]//2:
      if l[A.index(i)] == 1:
        j = 2 * i
        while j <= A[-1]:
          if j in set(A):
            l[A.index(j)] = 0
          j += i
      ind += 1
      i = A[ind]
          
    table = [A[i] for i in range(len(A)) if l[i] == 1]
    ans = len(table)
    
    dic = Counter(a)
    
    for k,v in dic.items():
      if v >= 2:
        ans -= 1
        
    return ans
  
print(nd())

Submission status: Wrong Answer

Solution code:
import numpy as num
print("lol test")

Submission status: Wrong Answer

Solution code:

import copy
n = int(input())
list_a = list(map(int, input().split()))  #リスト入力

list_a = list(set(list_a))
list_a.sort(reverse=True)
# print(list_a)

count = 0
if len(list_a) == 1:
    print(0)
else:
    for i in range(len(list_a)):
        ai = list_a[i] 
        new_list = list_a[i+1:]  #  全くの別物としてコピー
#         print(new_list)
        data2 = []
        booler = True
        for j in range(len(new_list)):
            aj = new_list[-j]
#             print(ai, aj, ai%aj)
            if ai % aj == 0:

                booler = False
                break
        if booler == True:
            count += 1


    print(count)

Submission status: Wrong Answer

Solution code:

import copy
n = int(input())
list_a = list(map(int, input().split()))  #リスト入力

list_a.sort(reverse=True)

count = 0
for i in range(n):
    ai = list_a[i] 
    new_list = list_a[i+1:]  #  全くの別物としてコピー
#     print(new_list)
    data2 = []
    booler = True
    for j in range(len(new_list)):
        aj = new_list[-j]
#         print(ai, aj, ai%aj)
        if ai % aj == 0:
            
            booler = False
            break
    if booler == True:
        count += 1


print(count)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

argv = input().split()
argv.sort()
divisible = 0
count = 0
  
for i in range(N):
  divisible = 0
  
  for j in range (i+1, N):
    if i == j:
      continue
    elif (int(argv[i]) % int(argv[j])) == 0:
      divisible = 1
      break
      
  if divisible == 0:
    count += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

new = [key for key, val in Counter(a).most_common() if val == 1]
prime = [1] * 1000010

for i in new:
    for j in range(i + i, 1000001, i):
        prime[j] = 0

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, *A = map(int, open(0).read().split())

C = Counter(A)
B = sorted(k for k, v in C.items() if v == 1)
if not B:
    print(0)
    quit()

lim = B[-1] + 1

memo = set()
ans = 0
for k in B:
    if k in memo:
        continue
    ans += 1
    memo |= set(range(k, lim, k))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

cnt = 0
for i in range(N):
    Ai = A[i]
    tmp = 0
    for j in range(N):
        if i == j:
            continue
        Aj = A[j]
        if Ai == Aj:
            continue
        if Ai % Aj != 0:
            tmp += 1
        else:
            break
    else:
        if tmp > 0:
            cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

new = [key for key, val in Counter(a).most_common() if val == 1]
dp = [0] * 1000010

for i in new:
    for j in range(0, 1000005, i):
        dp[j] += 1

ans = 0
for i in new:
    if dp[i] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

new = [key for key, val in Counter(a).most_common() if val == 1]
dp = [0] * 1000010

for i in new:
    for j in range(0, 1000001, i):
        dp[j] += 1

ans = 0
for i in new:
    if dp[i] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
n = int(input())
A = list(map(int, input().split()))

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

d = defaultdict(int)

for key in A:
    d[key] += 1

if len(d) == 1: # 全部同じ数
    print(0)
    sys.exit()

B = list(d)
B.sort()

if B[0] == 1: # 1が含まれる場合
    print(d[1])
    sys.exit()
len_B = len(B)
flag = [0 for i in range(B[-1]+1)]

for i in B:
    t = i
    while t <= B[-1]:
        flag[t] += 1
        t += i

ans = 0
for i in B:
    if flag[i] == 1 and d[i] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:





# template by 3xC and starkizard.
# contributors: 

#####################################################################################
from __future__ import division, print_function 

import sys
import os
from collections import Counter, deque, defaultdict
import itertools
import math
import io


"""Uncomment modules according to your need"""


# from bisect import bisect_left, bisect_right, insort
# from heapq import heappop, heapify, heappush
# from random import randint as rn
# from Queue import Queue as Q
# from copy import deepcopy
# from decimal import *
# import re
# import operator

#####################################################################################
# this enables you to write python3 code with PyPy2 (Python 2)
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

#####################################################################################

"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""Uncomment next 4 lines if doing huge recursion"""
# import threading
# threading.stack_size(1<<27)
# sys.setrecursionlimit(10000

def prepare_factorial(mod=mod):
    """ returns two lists, factorial and inverse factorial modulo argument by default 10**9 +7 """
    # Comment code out when you don't need inverse factorial or vice versa
    fact = [1]
    for i in range(1, 200005):
        fact.append((fact[-1] * i) % mod)

    ifact = [0] * 200005
    ifact[200004] = pow(fact[200004], mod - 2, mod)
    for i in range(200004, 0, -1):
        ifact[i - 1] = (i * ifact[i]) % mod
 
    return fact, ifact

def modinv(n, p):
    """ returns N inverse modulo p """
    return pow(n, p - 2, p)
 
def ncr(n, r,  fact, ifact):
    """ takes 4 arguments: n , r and factorial and inverse factorial lists"""
    t = (fact[n] * (ifact[r]*ifact[n-r]) % MOD)% MOD
    return t


def get_n(Sum):    
    """this function returns the maximum n for which Summation(n) <= Sum"""
    ans = (-1 + sqrt(1 + 8*Sum))//2
    return ans

def sieve(n):
    """ returns a list of prime numbers till n """
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r



def divs(n, start=1):
    """ returns a list of all divisors till n """
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors



def divn(n, primes):
    """ returns the number of divisors, two arguments n and the sieve till n """
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t



def lrfind(d, x, default=-1):
    """ Takes 2 arguments an iterable and an element. returns a tuple (firstoccurence,lastoccurence) -1 if not found """
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return default, default
    else:
        return left, right

def gcd(x, y): # math.gcd is slower
    """ returns greatest common divisor of x and y """
    while y:
        x, y = y, x % y
    return x

def ceil(n, k): return n // k + (n % k != 0) #returns math.ceil but protecting against floating inconsistencies
def input(): return sys.stdin.readline().strip()
def ii(): return int(input()) #inputs integer
def mi(): return map(int, input().split()) # inputting space seperated variables for example x,y,z
def li(): return list(map(int, input().split())) #inputting a space seperated list of integers
def lw(): return input().split() #inputting a space seperated list of strings
def lcm(a, b): return abs(a * b) // gcd(a, b) #returns LCM of two arguments
def prr(a, sep=' ', end='\n'): print(sep.join(map(str, a)), end=end) #For printing an iterable with seperator sep as optional second argument (default : " "), ending character (default: "\n") as optional third
def dd(): return defaultdict(int) #returns a dictionary with values defaulted to 0
def ddl(): return defaultdict(list) #returns a dictionary with values defaulted to []


###################################################################

def main():
    n=ii()
    ar=li()
    hsh=[True]*n

    for i in range(n):
        if hsh[i]:
            for j in range(n):
                if j!=i and ar[j]%ar[i]==0:hsh[j]=False
    for i in range(1,n):
        if ar[0]%ar[i]==0:hsh[0]=False;break    
    ctr=0
    #print(hsh)
    for i in range(n):
        if hsh[i]:ctr+=1
    print(ctr,end='')

'''            
    for _ in range(int(sys.stdin.readline())):
        n=int(sys.stdin.readline())
        ar=list(map(int,sys.stdin.readline().split()))
        ar.sort()
        boolean=[False]*n
        for i in range(n-1):
            if ar[i+1]-ar[i]==1:boolean[i]=boolean[i+1]=True
        neven=0;nodd=0
        for i in range(n):
            if not boolean[i]:
                if ar[i]%2==0:neven+=1
                else:nodd+=1
        if neven%2==nodd%2==0:ans='YES'
        else:ans='NO'    
'''    


""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""
 
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
 
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
 
class IOWrapper(IOBase):
 
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda: self.buffer.read().decode('ascii')
            self.readline = lambda: self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')
 
""" main function"""

if __name__ == '__main__':
    main()
    # threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)

b = sorted(set(a))

for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6:
            break
        prime[num] = False
        num += i

ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
num = {x for x in a if a.count(x) > 1}
a = list(set(a))

# リストの逆順でpopで削除すると高速化できる
for i in reversed(range(len(a))):
    for j in range(i):
        if a[j] in num:
            continue
        else:
            if a[i] % a[j] == 0:
                a.pop(i)
                break
print(len(a)-len(num))

Submission status: Wrong Answer

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

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

for i in range(len(a)):
    temp=False
    for j in range(i+1,len(a)):
        if i!=j and a[i]!=0:
            if a[j]%a[i]==0:
                if a[j]!=0 and a[i]%a[j]==0:
                    temp=True
                a[j]=0
    if temp==True:
        a[i]=0
        
a=sorted(set(a))

if a[0]==0 or len(a)==1:
    a=a[1:]
    print(len(a))
else:
    print(len(a))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect

N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
ans = 0
d = [False]*(10**6+1)
for i in range(N):
    if c[A[i]] == 1:
        ok = True
        l = bisect.bisect_right(A, int(A[i]**0.5)+1)
        for j in range(min(N, l)):
            if A[i] % A[j] == 0 and (d[A[j]] or d[A[i]//A[j]]):
                ok = False
                break
        if ok:
            ans += 1
    d[A[i]] = True

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect

N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
ans = 0
d = [False]*(10**6+1)
for i in range(N):
    if c[A[i]] == 1:
        ok = True
        l = bisect.bisect_left(A, int(A[i]**0.5)+1)
        for j in range(min(N, l)):
            if A[i] % A[j] == 0 and (d[A[j]] or d[A[i]//A[j]]):
                ok = False
                break
        if ok:
            ans += 1
    d[A[i]] = True

print(ans)

Submission status: Wrong Answer

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

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

for i in range(len(a)):
    for j in range(len(a)):
        if i!=j and a[i]!=0:
            if a[j]%a[i]==0:
                a[j]=0
                
a=sorted(set(a))

if a[0]==0 or len(a)==1:
    a=a[1:]
    print(len(a))
else:
    print(len(a))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
a.sort()
cnt=[0 for i in range(a[-1]+1)]
for i in a:
  cnt[i]+=1

dp=[True for i in range(a[-1]+1)]
for i in range(len(cnt)):
  if cnt[i]>=2:
    dp[i]=False
    
for i in range(n):
  if dp[a[i]]==False:
    #print(dp)
    continue
  if a[i]*2<=a[-1]+1:
    for j in range(a[i]*2,a[-1]+1,a[i]):
      dp[j]=False
      #print(dp)

for i in range(n):
  if dp[a[i]]:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

for i in range(n):
  if dp[a[i]]==False:
    #print(dp)
    continue
  if a[i]*2<=a[-1]+1:
    for j in range(a[i]*2,a[-1]+1,a[i]):
      dp[j]=False
      #print(dp)

for i in range(n):
  if dp[a[i]]:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

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

print(len([i for i in A if dp[i]]))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
N = int(input())
A = list(map(int, input().split()) )
if(1 in A):
    if( len([i for i in A if i==1])==1):
        print(1)
        sys.exit()
    else:
        print(0)
        sys.exit()
A_uni = list(set(A))
A_max = max(A_uni)
A_dup = [a for a in set(A) if A.count(a) > 1]

isPrime = [False]*(A_max+1)
for a in A_uni:
    isPrime[a] = True
sqrtA_max = int(np.sqrt(A_max))+1
for i in range(sqrtA_max):
    if not isPrime[i]:
        continue
    for j in range(i*i, A_max+1, i):
        isPrime[j] = False
l = np.array(range(A_max+1))
isPrime = np.array(isPrime)
print( len( list( set(l[isPrime]) - set(A_dup))))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
b = [True] * 1000001

for i, a in enumerate(A):
  if not b[i]:
    continue
  for i in range(2, 1000001):
    t = a * i
    if t > 1000000:
      break
    b[t] = False

from collections import Counter
c = Counter(A)
for x, y in c.most_common():
  if y > 1:
    b[x] = False
  elif y == 1:
    break

count = 0
for a in A:
  if b[a]:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()) )
A_uni = list(set(A))
A_max = max(A_uni)
A_dup = [a for a in set(A) if A.count(a) > 1]

isPrime = [False]*(A_max+1)
for a in A_uni:
    isPrime[a] = True
sqrtA_max = int(np.sqrt(A_max))+1
for i in range(sqrtA_max):
    if not isPrime[i]:
        continue
    for j in range(i*i, A_max+1, i):
        isPrime[j] = False
l = np.array(range(A_max+1))
isPrime = np.array(isPrime)
print( len( list( set(l[isPrime]) - set(A_dup))))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import defaultdict 
from collections import Counter
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    #重複している要素は除外する
    dd = Counter(A)

    if dd[1] > 1:
        print(0)
        return

    A = [int(key) for key, val in dd.items() if val == 1]  
    A.sort()

    #isntDiv[x]:=Tureのときxは他の要素で割り切れない
    isntDiv = defaultdict(lambda: 1) 

    if len(A) == 0:
        print(0)
        return

    #最小の要素は他の要素で割り切れない
    isntDiv[A[0]] = 1
    cnt = 0
    for i in A:
        if isntDiv[i]:
            cnt += 1
            for j in range(i*2, A[-1]+1 , i):
                isntDiv[j] = 0
    print(cnt) 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(n):
  if dp[i]:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

M = 1000005
cnt = [0] * M

for i in range(n):
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(a[i], M, a[i]+1):
        cnt[j] += 1

ans = 0

for i in range(n):
    if cnt[a[i]] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
n = int(input())
A = list(map(int, input().split()))

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

d = defaultdict(int)

for key in A:
    d[key] += 1

if len(d) == 1: # 全部同じ数
    print(0)
    sys.exit()

B = list(d)
B.sort()

if B[0] == 1: # 1が含まれる場合
    print(d[1])
    sys.exit()
len_B = len(B)
flag = [0 for i in range(B[-1]+1)]

for i in B:
    t = i
    while t <= B[-1]:
        flag[t] += 1
        t += i

ans = 0
for i in B:
    if flag[i] == 1:
        ans += d[i]

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
b = [True] * 1000001

for i, a in enumerate(A):
  if not b[i]:
    continue
  for i in range(2, 1000001):
    t = a * i
    if t > 1000000:
      break
    b[t] = False

count = 0
for a in A:
  if b[a]:
    count += 1

print(count)

Submission status: Wrong Answer

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

    for i, a in enumerate(A):
        if i < N - 1 and A[i + 1] == a:
            dp[a] = True
            continue
        if dp[a]:
            continue
        r += 1
        dp[a::a] = [True] * len(dp[a::a])
    return r


print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    dp = [False] * (A[-1] + 1)
    B = set()
    r = 0
    for a in A:
        if a in B:
            r -= 1
            continue
        B.add(a)
        if dp[a]:
            continue
        r += 1
        dp[a::a] = [True] * len(dp[a::a])
    return r


print(main())

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import defaultdict 
from collections import Counter
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    #重複している要素は除外する
    dd = Counter(A)
    A = [int(key) for key, val in dd.items() if val == 1]  
    A.sort()

    #isntDiv[x]:=Tureのときxは他の要素で割り切れない
    isntDiv = defaultdict(lambda: 1) 

    if len(A) == 0:
        print(0)
        return

    #最小の要素は他の要素で割り切れない
    isntDiv[A[0]] = 1
    cnt = 0
    for i in A:
        if isntDiv[i]:
            cnt += 1
            for j in range(i*2, A[-1]+1 , i):
                isntDiv[j] = 0
    print(cnt) 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def divisor(n):
  i = 2
  res = set()
  res.add(1)
  while i * i <= n:
    if n % i == 0:
      res.add(i)
      res.add(n//i)
    i += 1
  return res

n = int(input())
a = list(map(int,input().split()))
counter = 0
for x in a:
  if not divisor(x) & (set(a) - {x}):
    counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
m = max(a)
count = [0 for _ in range(m + 1)]
ans = 0

for i in a:
    if count[i] != 0:
        count[i] = 2
        continue
    for j in range(i, m + 1, i):
        count[j] += 1

print(count)

for i in a:
    if count[i] == 1:
        print(i)
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 2
cnt = [0 for _ in range(M)]
A.sort()

for i in A:
    if cnt[i] != 0: # cnt[i]がそれまでに出てきた数値で割り切れていたとき
        cnt[i] = 2 # cnt[i]の倍数はどうせすでに1か2になっているので考慮しなくていい
        continue
    j = i
    while j < M:
        cnt[j] += 1
        j += i
ans = 0
for i in cnt:
    if i == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    S = set(A)
    if len(S) == 1:
        print(0)
        return
    #setによって同じ数を取り除く
    A = list(S) 
    A.sort()
    from collections import defaultdict 
    #isntDiv[x]:=Tureのときxは他の要素で割り切れない
    isntDiv = defaultdict(lambda: 1) 
    cnt = 0
    #最小の要素は他の要素で割り切れない
    isntDiv[A[0]] = 1
    for i in A:
        if isntDiv[i]:
            cnt += 1
            for j in range(i*2, A[-1]+1 , i):
                isntDiv[j] = 0
    print(cnt) 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
"""
考え方のポイント
・自分以外では割り切れないような数の個数を求める
　→ 数列の各項に対して〇（割り切れない）×がついていって、〇の個数を数える
・[2, 2]みたいな入力は、他の数で割り切れるようになるので、同じ数が入っていると絶対に×になる。

まずは入力が全部異なる前提で進める。
範囲内の整数からなる全て配列dを用意する。
→ 入力の数列を約数としてもつ数にチェックをしていく（Anに2が含まれていれば、2の倍数全てにチェック（+1)する）
→ チェック後にd[i]をみたとき、d[i]の約数がan中に何個存在するかが示されていることになる。（2∈Aiならd[5](=6)の値は必ず1以上になってる)
"""
N = int(input())
An = [int(i) for i in input().split()]
An.sort()
max_val = 10**6
d = [0] * max_val


# O(N) = O(2*10^5)
# d[i]のうち、配列の値の位置を+1しとく。d[0]は1の約数、d[1]は2の約数を示すことに注意。
for i in An:
    d[i-1] += 1
    # O(MlogM) = 6*10^6
    # 始めてその倍数がきたときだけ
    if(d[i-1] == 1):
        # [2, 2]などの重複がない場合（既にカウントされているものではない場合)
        # 倍数の位置にも2としておいて以降はみないようにする
        for val in range(i*2, max_val, i):
            d[val-1] = 2

print(d.count(1))

Submission status: Wrong Answer

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

if N == 1:
  print(1)
  exit(0)
#
A = list(set(A))
N = len(A)
if N == 1:
  print(0)
  exit(0)
#
A.sort()
ans = 0

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

print(ans)