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()))
a.sort()
flag = [True] * (a[-1]*3)
for i, num in enumerate(a):
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        flag[num] = False
        continue
    for j in range(2, a[-1]//num+2):
        flag[j*num] = False
counter = 0
for i in a:
    if flag[i]:
        counter += 1
print(counter)

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 = max(a_list)
  dp = [True for i in range(biggest+1)]
  for i in a_list:
    for j in range(2*i,biggest+1,i):
      dp[j] = False
  ans = 0
  for i in a_list:
    if dp[i] == True:
      ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
n = int(input())
a = list(map(int,input().split()))
max_a = 10**6 +1 
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,math.ceil(max_a/ai)):
            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:
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+100)
dups=set()
fins=set()
for num in a:
    for i in range(2,10**10):
        if num*i > (maxa+50):
            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:
import sys
MX = 10**6
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    S = set(A)
    C = [0] * (MX + 1)
    for a in A:
        C[a] += 1
    ans = 0
    for a in A:
        if C[a] >= 2: continue
        for d in dv(a):
            if C[d] > 0:
                break
        else:
            ans += 1
    print(ans)

def dv(x):
    res = []
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            res.append(i)
            res.append(x // i)
    return res

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(float, input().split()))
A = np.sort(A)
D= np.ones(N)
ans= 0
for i in range(2, 1001):
    j=0
    c=1
    g=0
    while j<len(A):
        if A[j] % i == 0:
            if A[j] == i:
                g = 1
            if g == 1:
                A = np.delete(A, j)
                j -=1
                if c == 1:
                    ans += 1
                    c = 0
            if g == 0:
                while A[j] % i == 0:
                    A[j] /= i
                if A[j] == 1:
                    A = np.delete(A, j)
                    j -=1
                    if c == 1:
                        ans += 1
                        c = 0
            print(A)
        j += 1
q = ans+len(A)
if q < 2:
    print(0)
else:
    print(q)

Submission status: Wrong Answer

Solution code:
a = []
cnt = 0

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

for i in range(n):
    for j in range(n):
        if i == j:
            break
        if a[i] != a[j] and a[i] % a[j] == 0:
            cnt += 1
            break

if cnt == 0:
    print(0)
else:
    print(n-cnt)

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:
    for j in range(2*i,biggest+1,i):
      dp[j] = 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())
l=list(map(int,input().split()))
l.sort()
p=[1]*(l[-1]+1)
ans=0
for i in range(n):
  a=l[i]
  if p[a]==1:
    b=a
    while a<=l[-1]:
      p[a]=0
      a+=b
    if i<n-1:
      if l[i]==l[i+1]:
        pass
      else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
#ans=[1 for _ in range(N)]
size=len(A)
for i in range(N):
  j=i+1
  while size>j:
    if A[j]%A[i]==0:
      A.remove(A[j])
      size-=1
    j+=1
print(size)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = list(map(int,input().split()))
a.sort()
dp=[1]*(a[-1]+1)
d=2
ch=[]
m=0
for i in a:
    if i not in ch:
        while i*d<=a[-1]:
            dp[i*d]=0
            d+=1
        ch.append(i)
    else:
        dp[i]=0
ans=0
for i in a:
    if dp[i]==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import numpy as np

N = int(input())
A = sorted([int(i) for i in input().split()])
a = collections.Counter(A)
A = np.array([i[0] for i in a.items() if i[1] == 1])

if len(A) == 0:
    print(0)
else:
    dp = np.array([True for i in range(A[-1])])
    dp[:A[0]-1] = False
    ans = 0
    for i in range(A[-1]):
        if i+1 in A and dp[i] == True:
            n = i+1
            dp[A[np.where(A % n == 0)[0]]-1] = False
            dp[i] = True
        else:
            dp[i] = False
    print(np.sum(dp))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

# エラトステネスの篩っぽく処理
ans_list = [True for _ in range(A[-1] + 1)]
ans = 0

# ダブリを省くために先に数える
c = Counter(A)
original = [x for x in c.keys() if c[x] == 1]

for a in A:
    if ans_list[a] == True and a in original:
        ans += 1
        i = 2
        while a * i <= A[-1]:
            ans_list[a * i] = False
            i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7


N = ri()
A = rl()
m = max(A)

import collections
cnt = collections.Counter(A)
A = []
for k, v in cnt.items():
	if v == 1:
		A.append(k)
N = len(A)

A.sort()
h = {}
for a in A:
	h[a] = 1
for i in range(N):
	b = A[i]
	while b <= m:
		b += A[i]
		if b in h:
			del h[b]
print(len(h))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
ans_list = []

def div(x):
  
  i = 1
  while i**2 < x:
    if x % i == 0 and i != 1:
      a = x/i
      if i in A:
        break
      elif a in A:
        break
    i += 1
    if i**2 > x:
      ans_list.append(1)
      break
  

for i in A:
  div(i)
sub = len(set(A)) 
if sub != len(A):
  print(sum(ans_list)-N + sub -1)
else:
  print(sum(ans_list))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
from collections import Counter
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))

    count = Counter(A)
    S = list(set(A))
    S.sort()
    max_A = max(A)
    a = int(max_A ** 0.5)

    bl = [True] *(max_A+1)

    for x in S:
        if x>a:
            break
        if bl[x] == False:
            continue
        t = x*2
        while t<=max_A:
            bl[t] = False
            t += x

    ans = 0
    for x in S:
        if count[x]==1 and bl[x]==True:
            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()
flag = [True] * (a[-1]*2)
for i, num in enumerate(a):
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        flag[num] = False
        continue
    for j in range(2, a[-1]//num+1):
        flag[j*num] = False
counter = 0
for i in a:
    if flag[i]:
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        for j in range(2,max+1):
            if i*j>max:
                break
            dp[i*j]=True
for i in a:
    if a.count(i)>1:
        dp[i]=True
cnt=0
for i in a:
    if dp[i]:
        cnt+=1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
C = Counter(A).most_common()

MAXN = pow(10,6)
B = [False]*(MAXN+1)
for c in C:
    if c[1] == 1:
        B[c[0]] = True

ans = 0
for i in range(MAXN + 1):
    if B[i]:
        ans += 1
        B[i::i] = [False]*(MAXN//i)
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:
import collections

N = int(input())
A = list(map(int, input().split()))
A = collections.Counter(A)
if 1 in A:
    if A[1] == 1:
        print(1)
    else:
        print(0)
    exit()

B = []
for i in A:
    if A[i] == 1:
        B.append(i)
B = sorted(B)
if len(B) == 0:
    print(0)
    exit()
mb = max(B)
ok = [True] * (max(B)+1)

for b in B:
    if not ok[b]:
        continue
    k = 2
    while k*b <= mb:
        ok[k*b] = False
        k += 1
ans = 0
for b in B:
    if ok[b]:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        tf[j]=True
      if a_i < a[i+1]:
        print(a_i)
        r+=1
  if tf[-1] ==False:
    r+=1
  print(tf)
main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    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] == 0:
            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:
N = int(input())
a = list(map(int,input().split()))
a2 = sorted(a,reverse = True)
c = 0
print(a2)
for i in range(N):
  d =0 #カウンタの初期化
  for j in range(N-i-1):
    if a[i] % a[i+j+1] == 0:
      d = 1
  if d == 0:
    c =c+1
print(c-1)

Submission status: Wrong Answer

Solution code:
import collections

def divisor(n):
    d = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            d.append(i)
            if i**2 == n:
                continue
            d.append(n//i)
    return d

n = int(input())
A = list(map(int, input().split()))
C = collections.Counter(A)

B = []
for i in C.items():
  if i[1] == 1: 
    B.append(i[0])

cnt = 0
for b in B:
  tmp = set(divisor(b)) & set(B) 
  if len(tmp) == 1: cnt +=1
    
print(cnt)

Submission status: Wrong Answer

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

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

if sum(ok) == 1:
    print(0)
else:
    print(sum(ok))

Submission status: Wrong Answer

Solution code:
import copy

N = input()
data = input().split()
original = data.copy()
data2 = original.copy()
olddata = []

res_count = 0
loop_count = 0

for num in data:
    flag = 0
    olddata.clear()
    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:
import sys

def remove(N, AList):
    values = []
    index = 0
    while(index < N-1):
        if(AList[index] != AList[index+1]):
            values.append(AList[index])
            index += 1
        else:
            index += 1
            while(index < N and AList[index-1] == AList[index]):
                index+= 1
    if(AList[N-2]!=AList[N-1]):
        values.append(AList[N-1])
    return values


def Sieve(N, AList):
    AList.sort()
    AList = remove(N, AList)

    N_NotDivisible = 0
    while( len(AList)>0 ):
        if(len(AList)> 1):
            N_NotDivisible+= 1
            value = AList[0]
            AList = [i for i in AList if(i%value!=0) ]
        else:
            N_NotDivisible+= 1
            break
    #print(Mins)
    return N_NotDivisible

if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()

    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict, Counter
import numpy as np
N = int(input())
A = [int(i) for i in input().split()] 
c = Counter(A)
s = list(set(c))

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

for x in s:
  num = x * 2
  while num < 10 ** 6:
    dp[num] = False
    num += x

ans = 0
for a in A:
  if c[a] == 1 and dp[a] == True:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=[1 for _ in range(N)]
for i in range(N):
  j=i+1
  while len(A)>j:
    if A[j]%A[i]==0:
      A.remove(A[j])
    j+=1
print(len(A))

Submission status: Wrong Answer

Solution code:
N = int(input())
L = list(map(int, input().split()))
#N=10
#L=[33,18,45,28,8,19,89,86,2,4]
#N=5
#L=[3,8,11,16,24]

List=list(set(L))
#print(List)
List.sort()
#print(List)
#N=2
#List=[3,3,11,16,24]
#List=[5,5,5,5]
#List=[2,5]
a=0
#ns=List[N-1]/2
#print(ns)
for i in range(len(List)):
    #if i>ns:
     #   break
    
    for u in range(i):
 #       print(i,u,List[i],List[u])
        if List[i]%List[u]==0:
            a+=1
            print('#',i,u)
            break
#print(a)
if len(List)==1:
    print(0)
else:
    print(N-a)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

# エラトステネスの篩っぽく処理
ans_list = [True for _ in range(A[-1] + 1)]
ans = 0

# ダブリを省くために先に数える
c = Counter(A)
original = [x for x in c.keys() if c[x] == 1]

for a in original:
    if ans_list[a] == True:
        ans += 1
        i = 2
        while a * i <= A[-1]:
            ans_list[a * i] = False
            i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    black_list = []
    ans = 0
    for a in sorted(A_dict.keys()):
        for b in black_list:
            if a % b == 0 or b > a**(1/2):
                break
        else:
            if A_dict[a] == 1:
                ans += 1
            black_list.append(a)
    print(ans)
main()

Submission status: Wrong Answer

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

a.sort()

v = [True] * 1000010

for i in range(n):
    j = 2
    while a[i]*j < 1000010:
        v[a[i]*j] = False
        if (i > 1 and a[i-1] == a[i]) or (i < n-1 and a[i] == a[i+1]):
            v[a[i]] = False
        j += 1

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import gcd
import sys
MX = 10**6
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    S = set(A)
    C = Counter(A)
    ans = 0
    for a in A:
        if C[a] >= 2: continue
        for d in dv(a):
            if C[d] > 0:
                break
        else:
            ans += 1
    print(ans)

def dv(x):
    res = set()
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            res.add(i)
            res.add(x // i)
    return res

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(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(i+1<n and a[i] == a[i+1]):
            count += 1

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted([int(i) for i in input().split()])
b=[0 for i in range(max(a)+1)]

ans=0
for i in a:
    if b[i]==0:
        c=i
        while i<max(a)+1:
            b[i]=c
            i+=c
    else:
        if b[i]!=c:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
anstable = [0] * (10 ** 6 + 1)
d = defaultdict(int)
for i in a:
    d[i] += 1

u = []
for i, v in d.items():
    if v == 1:
        u.append(i)

for i in u:
    for j in range(i * 2, 10 ** 6 + 1, i):
        anstable[j] += 1

cnt = 0
for i in u:
    if anstable[i] == 0:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

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

    for i in a:
        x = 2
        while i * x < max_a:
            dp[i * x] = False
            x += 1

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


if __name__ == "__main__":
    main()

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
    if C[a] > 1:
        C[a] = 1
E = [0 for i in range(n)]
for i, a in enumerate(A):
    if C[a] > 1:
        E[i] = 1
    if a == 1:
        continue
    tmp = 1
    while tmp**2 <= a:
        if a % tmp == 0:
            if C[tmp] > 0:
                E[i] = 1
            if 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())
a = sorted(list(map(int,input().split())))
count = N
for i in range(N):
	for j in range(i):
		if a[i]%a[j] ==0 and i!= j:
			count = count -1
			break
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
pi = [int(i) for i in input().split()]

sorted_p = sorted(pi)
max_p = sorted_p[-1]
dp = [1 for i in range(max_p)]
ok = [0 for i in range(max_p)]
checked = []

for p in sorted_p:
    if dp[p-1] == 0:
        continue
    elif p in checked:
        dp[p-1] = 0
        ok[p-1] = 0
    else:
        for i in range(2,max_p//p+1):
            if dp[p*i-1] == 0:
                break
            else:
                dp[p*i-1] = 0
        checked.append(p)
        ok[p-1] = 1

print(sum(ok))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * (a[-1]+1)
for i, num in enumerate(a):
    #if num > a[-1]*0.5:
    #    break
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        flag[num] = False
        continue
    for j in range(2, a[-1]//num+1):
        flag[j*num] = False
counter = 0
#print(flag)
for i in a:
    if flag[i]:
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
def main1():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    ans=[0]*(10**6+1)
    if N ==1 :
        print(1)
        return 
    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 and A[i]!=A[i-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:
def actual(n, A):
    A = sorted(list(set(A)))

    if len(A) == 1:
        return 0

    judge_list = []
    while len(A) > 0:
        a_i = A.pop()

        s = [(a_i != a_j) and (a_i % a_j == 0) for a_j in A]

        judge_list.append(not any(s))

    return judge_list.count(True)

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

print(actual(n, A))

Submission status: Wrong Answer

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

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

for a in A:
    X[a] += 1
for a in A:
    if X[a] > 1:
        continue
    if Ans[a]:
        ans += 1
        for i in range(1, ma):
            if i * a > ma:
                break
            Ans[i * a] = False

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

# エラトステネスの篩っぽく処理
ans_list = [True for _ in range(A[-1] + 1)]
ans = 0

# ダブリを省くために先に数える
c = Counter(A)
original = [x for x in c.keys() if c[x] == 1]

for a in original:
    if ans_list[a] == True:
        ans += 1
        i = 2
        while a * i < A[-1]:
            ans_list[a * i] = False
            i += 1

print(ans)

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 not L[i]:
        continue
    if A[i] == 1:
        ans += 1
    else:
        continue
    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()))
A.sort()

dlen = A[-1]+3
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())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

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

while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    ba = math.ceil(math.sqrt(ba))
    se = set(make_divisors(ba))
    l1_l2_and = set(li) & set(se)
    if len(l1_l2_and)==0:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

a=sorted(a)

dp=[True]*(max(a)+1)

cnt=0
for i in range(n):
    b=a[i]

    if dp[b]==True:
        cnt+=1
    
    k=1
    while b<=max(a):
        dp[b]=False
        b/=k
        k+=1
        b=int(b*k)

print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import collections
import bisect
# import sympy


N = int(input())

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

A.sort()
setA = set(A)

Amax = A[len(A) - 1]
dp = [True for i in range(Amax + 1)]
ans = 0
for i in range(len(A)):
    if i < len(A) - 1:
        if A[i] == A[i + 1]:
            continue
    if i > 0:
        if A[i] == A[i - 1]:
            continue

    if dp[A[i]] == True and A[i] in set(A):
        c = 2
        ans += 1
        while(c * A[i] <= Amax):
            dp[c * A[i]] = False
            c += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

# エラトステネスの篩っぽく処理
ans_list = [True for _ in range(A[-1])]
ans = 0

# ダブリを省くために先に数える
c = Counter(A)
original = [x for x in c.keys() if c[x] == 1]

for a in original:
    if ans_list[a-1]:
        ans += 1
        i = 2
        while a * i < A[-1]:
            ans_list[a * i] = False
            i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
a = []
cnt = 0

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

for i in range(n):
    for j in range(n):
        if i == j:
            break
        if a[i] != a[j] and a[i] % a[j] == 0:
            cnt += 1
            break

print(n-cnt)

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 = [0]*(U+1)
C = Counter(A)
ans = 0
for a in A:
  if C[a] > 1:
    continue
  if B[a]:
    continue
  ans += 1
  for j in range(a, U+1, a):
    B[j] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(map(int,input().split()))
ans=0
dp=[True]*(max(A)+1)
for i in range(N):
    if not dp[A[i]]:
        continue
    if i<N-1 and A[i+1]==A[i]:
        dp[A[i]]=False
        continue
    ans+=1
    for j in range(1000001):
        if A[i]*j>max(A):
            break
        dp[A[i]*j]=False
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
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():
    mod=10**9+7
    N=I()
    A=LI()
    M=10**6+5
    dp=[1]*M
    A.sort()
    L=[A[0]]
    for i in range(1,N):
        if A[i]!=L[-1]:
            L.append(A[i])
        else:
            dp[A[i]]=0
            
    for i in range(len(L)):
        temp=L[i]
        if dp[temp]==1:
            temp+=L[i]
            while temp<M:
                dp[temp]=0
                temp+=L[i]
        
    ans=0        
    for i in range(len(L)):
        if dp[L[i]]==1:
            ans+=1
            
            
    

         
            
    print(ans)
                
    
    


main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

# エラトステネスの篩っぽく処理
ans_list = [True for _ in range(A[-1])]
ans = 0

# ダブリを省くために先に数える
c = Counter(A)
original = [x for x in c.keys() if c[x] == 1]

for a in original:
    if ans_list[a-1]:
        ans += 1
        i = 2
        while a * i < A[-1]:
            ans_list[a * i] = False

print(ans)

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 in range(MAX, 0, -1):
    if arr[i]:
        arr[i*2::i] = 0

print(arr.sum())

Submission status: Wrong Answer

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


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

if N == 1:
    print(1)
    exit()
    
A = sorted(A)
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    divisors = make_divisors(A[i])[:-1]
    check_ok = True
    for d in divisors:
        check_list[d] += 1
for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
aa = sorted(set(a))
count = 0

li = [0]*(max(a)+1)

for i in aa:
    if li[i]>0:
        count += 1
        #print(i)
    k = i    
    while k < max(a)+1:
        li[k]+=1
        k+=i
#print(li)
if len(a)==len(aa):
    p=0
else:
    p=len(a)-len(aa)+1
print(n-count-p)

Submission status: Wrong Answer

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

dp = [0] * (10**6 + 10)

cnt = 0
for i, x in enumerate(arr):
    if dp[x] == 0:
        for y in range(1, (10**6 + 10) // x):
            dp[y * x] = 1
        if i < n - 1:
            if x == arr[i + 1]:
                continue
        cnt += 1
    else:
        continue

print(cnt)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
i = 0
while a:
    if a.count(a[0]) == 1:
        i+=1
    a = list(filter(lambda x: x%a[0] >0,a))
print(i)

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return
    if A[0] == 1:
        print(0 if A[1] == 1 else 1)
        return

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da < 2:
            dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
    print(dp.count(1))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

A.sort()
max_num = max(A)
#sub_count = [x for x in set(A) if A.count(x) > 1]
A = list(set(A))

i = 0
count = 0
while True:
    if A == []:
        break
    if A[0] == max_num:
        count += 1
        break
    count += 1
    look = A[0]
    del A[0]
    del_num = []
    for j in range(len(A)):
        if A[j] % look == 0:
            del_num.append(j)
    del_num = sorted(del_num, reverse=True)
    for j in del_num:
        del A[j]

print(count)