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:


def get_prime_numbers(max_value: int):
    primes = [2]
    for i in range(3, max_value + 1, 2):
        if all(i % prime != 0 for prime in primes):
            primes.append(i)
    return primes


def q4():
    _ = input()
    A = [int(i) for i in input().split(" ")]

    primes = get_prime_numbers(1000)

    values = set()
    duplicates = set()
    values_dict = {}
    for i in range(len(A)):
        a = A[i]
        if a in values:
            duplicates.add(values_dict[a])
            duplicates.add(i)
        values_dict[a] = i
        values.add(a)

    ans_count = 0
    for i in range(len(A)):
        a = A[i]
        if i in duplicates:
            continue
        if a in primes:
            ans_count += 1
            continue
        ok = True
        for p in primes:
            if p in values and a % p == 0:
                ok = False
                break
            if a / p in values:
                ok = False
                break
        if ok:
            ans_count += 1

    print(ans_count)


q4()

Submission status: Wrong Answer

Solution code:

def get_prime_numbers(max_value: int):
    primes = [2]
    for i in range(3, max_value + 1, 2):
        if all(i % prime != 0 for prime in primes):
            primes.append(i)
    return primes


def q4():
    _ = input()
    A = [int(i) for i in input().split(" ")]

    primes = get_prime_numbers(1000)

    values = set()
    duplicates = set()
    values_dict = {}
    for i in range(len(A)):
        a = A[i]
        if a in values:
            duplicates.add(values_dict[a])
            duplicates.add(i)
        values_dict[a] = i
        values.add(a)

    print(duplicates)

    ans_count = 0
    for i in range(len(A)):
        a = A[i]
        if i in duplicates:
            continue
        if a in primes:
            ans_count += 1
            continue
        ok = True
        for p in primes:
            if p in values and a % p == 0:
                ok = False
                break
            if a / p in values:
                ok = False
                break
        if ok:
            ans_count += 1

    print(ans_count)


q4()

Submission status: Wrong Answer

Solution code:

def get_prime_numbers(max_value: int):
    primes = [2]
    for i in range(3, max_value + 1, 2):
        if all(i % prime != 0 for prime in primes):
            primes.append(i)
    return primes


def q4():
    _ = input()
    A = [int(i) for i in input().split(" ")]

    primes = get_prime_numbers(1000)

    values = set()
    duplicates = set()
    values_dict = {}
    for i in range(len(A)):
        a = A[i]
        if a in values:
            duplicates.add(values_dict[a])
            duplicates.add(i)
        values_dict[a] = i
        values.add(a)

    ans_count = 0
    for i in range(len(A)):
        a = A[i]
        if a in duplicates:
            continue
        if a in primes:
            ans_count += 1
            continue
        ok = True
        for p in primes:
            if p in values and a % p == 0:
                ok = False
                break
            if a / p in values:
                ok = False
                break
        if ok:
            ans_count += 1

    print(ans_count)


q4()

Submission status: Wrong Answer

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

a.sort()

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

ans = [1] * (a[n-1]+1)

for i in range(n):
    if i >= 1 and a[i] == a[i-1]:
        ans[a[i]] = 0

    else:
        j = 2
        while j*a[i] <= a[n-1]:
            ans[j*a[i]] = 0
            j += 1


sum = 0

print(sum)

Submission status: Wrong Answer

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


a.sort()

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

num = 1
count = 1

n = len(a)

for i in range(1,n):
    for j in range(num):
        if a[i] % a[j]== 0:
            count -= 1
            break
        #print(a[i],a[j])
    num += 1
    count += 1
    #print(a[i],count)
if a[0] == a[1]:
    count -= 1

print(count)

Submission status: Wrong Answer

Solution code:
counter = [0 for i in range(10**6+1)]
n = int(input())
a = sorted(list(map(int,input().split())))
for i in a:
  counter[i] += 1
l  = [0 for i in range(10**6+1)]
cou = 0
for i in range(n):
  b = a[i]
  if l[b]==0:
    cou += 1
    for j in range(b,10**6+1,b):
      l[j] = 1
    if counter[j]>=2:
      cou -=1
print(cou)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = sorted(list(map(int,input().split())))
t = list(Counter(a).values())
s = [i for i in t if i>=2]
#print(len(s))
l  = [0 for i in range(10**6+1)]
cou = 0
a = sorted(list(set(a)))
for i in range(len(a)):
  b = a[i]
  if l[b]==0:
    cou += 1
    for j in range(b,10**6+1,b):
      l[j] = 1
print(cou-len(s))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = sorted(list(map(int,input().split())))
t = list(Counter(a).values())
s = [i for i in t if i>=2]
#print(len(s))
l  = [0 for i in range(10**6+1)]
cou = 0
for i in range(n):
  b = a[i]
  if l[b]==0:
    cou += 1
    for j in range(b,10**6+1,b):
      l[j] = 1
print(cou-len(s))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())))
l  = [0 for i in range(10**6+1)]
cou = 0
for i in range(n):
  b = a[i]
  if l[b]==0:
    cou += 1
    for j in range(b,10**6+1,b):
      l[j] = 1
if a.count(a[0])==n:
  print(0)
  exit()
print(cou)

Submission status: Wrong Answer

Solution code:
import math
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
cccc=int(lista[n-1]/lista[0])+1
listde=set()
for i in range(n-1):
    if(lista[i]==lista[i+1] ):
        listde.add(lista[i])
t=0
for i in range(n):
    t=0
    for k in listde:
        
        if (lista[i]%k==0):
            t=1
            break
    if (t==0):
        s+=1
        if(lista[i]<=cccc):
            listde.add(lista[i])
print(s)

Submission status: Wrong Answer

Solution code:
import math
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
listde=set()
for i in range(n-1):
    if(lista[i]==lista[i+1] ):
        listde.add(lista[i])
t=0
for i in range(n):
    t=0
    for k in listde:
        
        if (lista[i]%k==0):
            t=1
            break
    if (t==0):
        s+=1
        if(lista[i]<=math.sqrt(lista[n-1])):
            listde.add(lista[i])
print(s)

Submission status: Wrong Answer

Solution code:
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
for i in range(n-1):
    if(i!=n-2):
        if (lista[i+1]==lista[i+2]):
            continue
    for k in range(i+1):

        if(lista[i+1]%lista[k]==0):
            break
        else:
            if(k==i ):
                s+=1
if(n!=1 and lista[0]!=lista[1]):
    s+=1
print(s)
                
        
        
        
    
5

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
inp = list(map(int,input().split()))
c=Counter(inp)
inp=[]
for item in c.keys():
    if c[item]==1:
        inp.append(item)
arr=[1]*len(inp)
inp.sort()
ans=0
for i in range(len(inp)):
    if arr[i]==0:
        continue
    else:
        ans+=1
        for j in range(i+1,len(inp)):
            if inp[j]%inp[i]==0:
                arr[j]=0
print (ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    A_max = A[-1]
    g = []
    table = [True]*(A_max+1)
    for i,a in enumerate(A):
        if table[a]:
            if (i!=n-1 and a != A[i+1]) or (i==n-1 and a!=A[i-1]):
                g.append(a)
                temp = a
                while A_max >= temp:
                    table[temp] = False
                    temp+=a
    print(len(g))
main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    A_max = A[-1]
    g = []
    table = [True]*(A_max+1)
    for i,a in enumerate(A):
        if table[a]:
            if (i!=n-1 and a != A[i+1]) or (i==n-1 and a!=A[i-1]):
                g.append(a)
                for j in range(A_max//a):
                    table[a*(j+1)] = False
    print(len(g))
main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    A_max = A[-1]
    g = []
    table = [True]*(A_max+1)
    for i,a in enumerate(A):
        if table[a]:
            if (i!=n-1 and a != A[i+1]) or (i==n-1 and a!=A[i-1]):
                g.append(a)
                for j in range(A_max//a):
                    table[a*j] = False
    print(len(g))
main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    A_max = A[-1]
    g = []
    table = [True]*(A_max+1)
    for i,a in enumerate(A):
        if table[a] and i!=n-1 and a != A[i+1]:
            g.append(a)
            for j in range(A_max//a):
                table[a*j] = False
    print(len(g))
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
mp = defaultdict(int)
n = int(input())
a = list(map(int,input().split()))
seen = [False]*n
a.sort()
dub = 0
res = 0
for k in a:
    if mp[k]==1:
        dub+=1
    mp[k] += 1
for i in range(n):
    for j in range(i+1,n):
        if seen[j]:
            continue
        if a[j]%a[i]==0:
            seen[j] = True
            res += 1
#print(res,dub)
print(n-res-dub)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
mp = defaultdict(int)
seen = defaultdict(int)
n = int(input())
a = list(map(int,input().split()))
a.sort()
dub = 0
res = 0
for k in a:
    if mp[k]:
        dub+=1
    mp[k] += 1
for i in range(n):
    for j in range(i+1,n):
        if seen[a[j]]:
            continue
        if a[j]%a[i]==0:
            seen[a[j]] +=1
            res += 1
print(res,dub)
print(n-res-dub)

Submission status: Wrong Answer

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

ans = 0
for a in A:
  if li[a]:
    for i in range(a, l, a):
      li[i] = False
    ans += 1
print(ans)

Submission status: Wrong Answer

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

#ループ回数が大きくならないように止める
a=sorted(a,reverse=True)

c=[0]*n
for i in range(n):
    if a.count(a[i])>1:
        c[i]=+1
        continue
    for j in range (i+1,n):
        if a[i]<2*a[j]:
            continue
        elif a[i]%a[j]==0:
            c[i]=+1
            break

print(c)
print(c.count(0))

Submission status: Wrong Answer

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

c = Counter(A)
A = [i[0] for i in c.items() if i[1] == 1]

flag = True
if A == []:
  flag = False
else:
  A.sort()
ans = 0
i = 0
j = len(A)-1

while i < j:
  if A[j] % A[i] == 0:
    A.pop(j)
  j -= 1
  if j == i:
    ans += 1
    j = len(A)-1
    i += 1
  
if flag:
  ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
s = []
for i in range(n):
    if i > 0 and a[i] == a[i-1]: continue
    if i < (n-1) and a[i] == a[i+1]: continue
    s.append(a[i])

if not s: print(0); exit()

m = 10**6+10
d = [False] * (m+1)
ans = 0
for x in s:
    if not d[x]: ans += 1
    for i in range(x, m+1, x):
        d[i] = True
    
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
s = []
for i in range(n):
    if i > 0 and a[i] == a[i-1]: continue
    if i < (n-1) and a[i] == a[i+1]: continue
    s.append(a[i])

if not s: print(0); exit()

m = max(s)
d = [False] * (m+1)
ans = 0
for x in s:
    if not d[x]: ans += 1
    for i in range(x, m+1, x):
        d[i] = True
    
print(ans)

Submission status: Wrong Answer

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

A.sort()

for i in range(N-1):
    for j in range(i+1,N):
        if A[j]%A[i]!=0:
            l.append(i)
print(len(set(l)))

Submission status: Wrong Answer

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

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

A.sort()
Sum = 0

for i in range(N):
    
    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if i+1 < N:
            if A[i] != A[i+1]:
                Sum += 1
print(Sum)

Submission status: Wrong Answer

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

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

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break


        if i == N - 1:
            if A[i] != A[i - 1]:
                Sum += 1


print(Sum)

Submission status: Wrong Answer

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

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

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1,10**6):
            if A[i]*j <= 10**6:
                DP[A[i]*j] = 1
            else:
                break
        if i + 1 < N:
            if A[i] != A[i + 1]:
                Sum += 1
        else:
            if A[i] != A[i-1]:
                Sum += 1

print(Sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split(" "))))
m = max(A)
ans = 0
dp = [True]*m
for i in range(N-1):
  x = A[i]-1
  if dp[x] == True:
    for j in range(m//A[i]+1):
      dp[j*A[i]-1] = False
    if A[i] != A[i+1]:
      ans +=1
if dp[-1]:
  ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
ans = 0
dp = [True]*max(A)
A.sort()
for i in range(N):
  if dp[A[i]-1]:
    if i > 1:
      if A[i] == A[i-1]:
        dp[A[i]-1] = False
        continue
    for j in range(2,max(A)//A[i]+1):
      dp[j*A[i]-1] = False
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
count = 0
if A.count(A[0]) == len(A):
	A = []
for i in range(len(A)):
  if A == []:
    break
  mina = min(A)
  #print(format(mina))
  count += 1
  #print(len(A))
  for j in range(len(A)-1,-1,-1):
    #print(A[j])
    if A[j] % mina == 0:
    	A.pop(j)
    #print(j,len(A))
  #print(A)
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(1)
  exit()

a.sort()
if a[0] == 1:
  print(1)
  exit()

c = Counter(a)
s = list(set(a))
dp = [0] * (10**6 +1)

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

ans = 0
for x in a:
  if (c[x] == 1) & (dp[x] == 0):
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(1)
  exit()

a.sort()
if a[0] == 1:
  print(1)
  exit()

c = Counter(a)
a = list(set(a))
dp = [0] * (10**6 +1)

for x in a:
  t = x * 2
  while t <= 10**6:
    dp[t] = 1
    t += x

ans = 0
for x in a:
  if (c[x] == 1) & (dp[x] == 0):
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(1)
  exit()

a.sort()
if a[0] == 1:
  print(1)
  exit()

dp = [1 for _ in range(n)]

def div(k):
  global dp
  for i in range(k):
    if a[k]%a[i] == 0:
      dp[k] = 0
      if a[k] == a[i]:dp[i] = 0
      break
  if k < n-1:div(k+1)

for k in range(n):
  for i in range(k):
    if a[k]%a[i] == 0:
      dp[k] = 0
      if a[k] == a[i]:dp[i] = 0
      break

print(sum(dp))

Submission status: Wrong Answer

Solution code:
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(n)
  exit()

a.sort()
if a[0] == 1:
  print(1)
  exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(n)
  exit()

a.sort()
if a[0] == 1:
  print(n)
  exit()

Submission status: Wrong Answer

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

a.sort()
dp = [1] * n

def div(k):
  global dp
  if dp[k] != 0:
    for i in range(k):
      if a[k]%a[i] == 0:
        dp[k] = 0
        if a[k] == a[i]:dp[i] = 0
        break
    if k < n-1:div(k+1)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

num = 10**6

tmp = [True] * num

for i in a:
    if a.count(i) >= 2:
        tmp[i-1] = False


a = set(a)
for i in a:
    tmptmp = i + i
    while(tmptmp <= np.sqrt(num)):
        tmp[tmptmp-1] = False
        tmptmp += i

counter = 0
for i in a:
    if tmp[i-1]:
        counter += 1
        
print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

tmp = [True] * (10**6)
tmp = np.array(tmp)

a = np.sort(a)
for i in range(1, len(a)):
    if a[i] == a[i-1]:
        tmp[a[i]-1] = False

for i in a:
    tmptmp = i + i
    while(tmptmp <= np.sqrt(10**6)):
        tmp[tmptmp-1] = False
        tmptmp += i

counter = 0
for i in a:
    if tmp[i-1]:
        counter += 1
        
print(counter)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
DP = [True]*N
for i in range(N-1):
  for j in range(i+1,N):
    if DP[j]==True and A[j]%A[i]==0:
      DP[j] = False
if N >1 and A[0]%A[1]==0:
  DP[0]=False
print(sum(DP))

Submission status: Wrong Answer

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

cnt = n
c = 0
for i in range(n):
    for j in range(i+1, n):
        if A[i]%A[j] == 0:
            cnt -= 1
            break
        if i != 0 and A[i] == A[i-1]:
            cnt -= 1
    if i == n-1 and A[i] == A[i-1]:
        cnt -= 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
counter = 0
for i in range(N-1):
  flag = 1
  for j in range(i+1,N):
    if A[i]>A[j] and A[i]%A[j] == 0:
      flag = 0
      break
    elif A[j] >= A[i] and A[j]%A[i] == 0:
      flag = 0
      break
  if flag == 1:
    counter += 1
if min(A) == max(A):
  print(counter)
else:
  print(counter+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A =[[x,i+1] for i,x in enumerate(a)]
A.sort()
A = [[0,0]] + A + [[0,0]]

ind = deque()
for i in range(1,n+1):
  if (A[i-1][0] != A[i][0]) & (A[i][0] != A[i+1][0]):
    ind.append(i)
ind = list(ind)
for i in ind:
  for j in ind[::-1]:
    if A[j][0]%A[i][0] == 0:
      if i != j:
        ind.remove(j)

#A = [A[x] for x in ind]
print(len(ind))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

import itertools

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

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

A.sort()

check = [True for i in range(10**6+1)]
ans = 0
for a in A:
    if not check[a]:
        continue
    for j in range(2*a,10**6+1,a):
        check[j] = False

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

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

import itertools

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

A.sort()

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

check = [[True,False] for i in range(10**6+1)]
ans = 0
for a in A:
    if not check[a][0]:
        continue
    for j in range(2*a,10**6+1,a):
        check[j][0] = False

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = sorted(set(list(map(int, input().split()))))
    m = len(a)
    max_value = 10 ** 6
    dp = [False for _ in range(max_value + 1)]

    if 1 in a or m == 1:
        print(0)
        exit()

    for ai in a:
        dp[ai] = True

    for ai in a:
        for i in range(2 * ai, max_value + 1, ai):
            if dp[i]:
                dp[i] = False

    print(sum(dp))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = sorted(set(list(map(int, input().split()))))
    m = len(a)
    max_value = 10 ** 6
    dp = [False for _ in range(max_value + 1)]

    if 1 in a or m == 1:
        print(0)
        exit()

    for ai in a:
        dp[ai] = True

    for ai in a:
        if not dp[ai]:
            continue

        for i in range(2 * ai, max_value + 1, ai):
            if dp[i]:
                dp[i] = False

    print(sum(dp))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

a = sorted(a)
max_a = max(a)
dp = [1 for i in range(max_a+1)]
a_num = [0 for i in range(max_a+1)]
ans = 0

for i in a:
    a_num[i] += 1
    if a_num[i] == 2:
        dp[i] = 0

for i in a:
    if dp[i] == 0:
        continue
    else:
        ans += 1
        tmp = i
        while tmp+i <= max_a:
            tmp += i
            dp[tmp] = 0

print(ans)

Submission status: Wrong Answer

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

a = sorted(a)
dp = [1 for i in range(a[len(a)-1]+1)]
a_num = [0 for i in range(a[len(a)-1]+1)]
ans = 0

for i in a:
    a_num[i] += 1
    if a_num[i] == 2:
        dp[i] = 0

for i in a:
    if dp[i] == 0:
        continue
    else:
        ans += 1
        tmp = i
        while tmp+i <= a[(len(a)-1)]:
            tmp += i
            dp[tmp] = 0

print(ans)

Submission status: Wrong Answer

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

a = sorted(a)
dp = [1 for i in range(a[len(a)-1]+1)]
a_num = [0 for i in range(a[len(a)-1]+1)]
ans = 0

for i in a:
    a_num[i] += 1
    if a_num[i] == 2:
        dp[i] = 0
        ans -= 1
    elif a_num[i] == 1 and dp[i] == 1:
        ans += 1
        tmp = i
        while tmp+i <= a[len(a)-1]:
            tmp += i
            dp[tmp] = 0

print(ans)

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr=list(set(arr))
    n=len(arr)
    tb=[False]*(10**6 + 10)
    ans=0
    for i in range(n):
        x=arr[i]
        if tb[x]==False:
            ans+=1
        for j in range(x,10**6+5,x):
            tb[j]=True
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:
for i in range(1000000):
    i**2

Submission status: Wrong Answer

Solution code:
for i in range(int(1e6)):
    i**2

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

A.sort()
s = A[-1] + 1

dp = ['True'] * s
seen = set()

ans = 0
for i in range(len(A)):
	if i in seen:
		continue
	else:
		seen.add(i)

	x = A[i]
	if dp[x]:
		for y in range(x, len(dp), x):
			dp[y] = False

		if i == len(A) - 1:
			if dp[i]:
				ans += 1
		else:
			if x < A[i + 1]:
				ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

A.sort()
s = A[-1] + 1

dp = ['True'] * s
seen = set()

ans = 0
for i in range(len(A)):
	if i in seen:
		continue
	else:
		seen.add(i)

	x = A[i]
	if dp[x]:
		for y in range(x + x, len(dp), x):
			dp[y] = False

		if i == len(A) - 1:
			if dp[i]:
				ans += 1
		else:
			if x < A[i + 1]:
				ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
N = int(input())
A = defaultdict(int)
for i in input().split():
    A[int(i)] += 1
minus = 0
S = []
for key in A.keys():
    if A[key] >= 2:
        minus += 1
    S.append(key)
S = sorted(S)
Q = deque(S)
ans = 0
while Q:
    q = Q.popleft()
    ans += 1
    R = []
    while Q:
        M = Q.popleft()
        if M%q != 0:
            R.append(M)
    Q = deque(R)
print(ans - minus)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
a = list(set(A))
c = 0
    

for i in range(len(a)-1):
  k = 0
  for j in range(i+1,len(a)):
    if a[j+k] % a[i] == 0:
      del a[j+k]
      k -= 1
      
for x in a:
  if A.count(x) > 1:
    c += 1
      
print(len(a)-c)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
from collections import defaultdict
sort_A = sorted(A)
from collections import deque
Q = deque(sort_A)
ans = 0
while Q:
    M = Q.popleft()
    ans += 1
    R = deque([])
    while Q:
        q = Q.popleft()
        if q%M != 0:
            R.append(q)
    Q = R
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
from collections import defaultdict
cnt_A = defaultdict(int)
for a in A:
    cnt_A[a] += 1
NG_list = []
for key in cnt_A.keys():
    if cnt_A[key] >= 2:
        NG_list.append(key)
sort_A = sorted(A)
from collections import deque
Q = deque(sort_A)
ans = 0
while Q:
    M = Q.popleft()
    ans += 1
    R = deque([])
    while Q:
        q = Q.popleft()
        if q%M != 0:
            R.append(q)
    Q = R
print(ans-len(NG_list) )

Submission status: Wrong Answer

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

print(a.index(min(a)))

Submission status: Wrong Answer

Solution code:
from collections import Counter
def fun():
    n = int(input())
    num_list = list(map(int, input().split()))
    x = Counter(num_list)
    if 1 in x and x[1] > 1: 
        return 0
    elif 1 in x and x[1] == 1:
        return 1
        
    dp = [False] * (max(x)+1)
    for i in num_list:
        if x[i] == 1:
            dp[i] = True
    for i in num_list:
        if dp[i]:
            for j in range(i+i, len(dp), i):
                dp[j] = False
                
    # for idx, i in enumerate(dp):
    #     if i:
    #         print(idx)
    return sum(i for i in dp)
print(fun())

Submission status: Wrong Answer

Solution code:
# cook your dish here
from collections import Counter
def fun():
    n = int(input())
    num_list = list(map(int, input().split()))
    x = Counter(num_list)
    if 1 in x: return 0
    dp = [False] * (max(x)+1)
    for i in num_list:
        if x[i] == 1:
            dp[i] = True
    for i in num_list:
        if dp[i]:
            for j in range(i+i, len(dp), i):
                dp[j] = False
                
    # for idx, i in enumerate(dp):
    #     if i:
    #         print(idx)
    return sum(i for i in dp)
print(fun())

Submission status: Wrong Answer

Solution code:
# cook your dish here
from collections import Counter
def fun():
    n = int(input())
    num_list = list(map(int, input().split()))
    x = Counter(num_list)
    dp = [False] * (max(x)+1)
    for i in num_list:
        if x[i] == 1:
            dp[i] = True
    for i in num_list:
        if dp[i]:
            for j in range(i+i, len(dp), i):
                dp[j] = False
                
    # for idx, i in enumerate(dp):
    #     if i:
    #         print(idx)
    return sum(i for i in dp)
print(fun())

Submission status: Wrong Answer

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

A=[]
array=sorted(array)
for i in array:
    A.append(i)

dp=[True for i in range(N)]

for i in range(N):
    if dp[i] == False:
        continue
    for j in range(i+1,N):
        if A[j]%A[i]==0:
            dp[j]=False

if not N ==1:
    if A[0]==A[1]:
        dp[0]=False

num=0
for i in range(N):
    if dp[i] == True:
        num+=1

print(num)

Submission status: Wrong Answer

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

A=[0]
array=sorted(array,reverse=True)
for i in array:
    A.append(i)


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

Submission status: Wrong Answer

Solution code:
import array
import numpy as np

n = int(input())
arr = np.array(sorted(list(map(int,input().split()))))
brr = array.array('i',[1]*n)

for i in range(n):
    if brr[i]==0:
        break
    else:
        for j in range(i+1,n):
            if arr[j]%arr[i]==0:
                brr[j]=0
    if i<n-1 and arr[i]==arr[i+1]:
        brr[i]=0

print(sum(brr))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
a = int(readline())
n = list(map(int,readline().split()))
ans = 0
for num,m in enumerate(n):
    chk = set()
    N = n.copy()
    N[num] = n[num-1]
    ss = set(N)
    t = int(m**0.5)
    for i in range(1,t+1):
        if m%i == 0:
            chk.add(i)
            chk.add(m//i)
    if chk & ss == set():
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    n = int(raw_input())
    
    arr = map(int,raw_input().split())
    
    ans = 0
    
    max_ele = max(arr)
    
    arr.sort()
    
    marked = [False] * (max_ele+5)
    
    for i in range(n):
        diff_prev = i-1 < 0 or arr[i] != arr[i-1]
        diff_next = i+1 >= n or arr[i] != arr[i+1]
        num = arr[i]
        if diff_next and diff_prev:
            if not marked[num]:
                cur = num 
                ans += 1
                while cur <= max_ele:
                    marked[cur] = True
                    cur += num
    
    print(ans)
    

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a_li = list(map(int,input().split()))
dum = [0]*10**6
for i in a_li:
    for j in range(i*2,10**6,i):
        dum[j-1] = 1
print(dum)