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 = sorted(a)
s = set()
same_s = set()
ans = 0
for i in a:
    if i in s:
        same_s.add(i)
    if i not in s:
        same_s.add(i)
        ans +=1
        for j in range(10**6 // i + 1):
            s.add(j*i)
print(ans - len(same_s))

Submission status: Wrong Answer

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

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

        if A[j]*2 > A[i]:
            if A[i] % A[i-1] == 0:
                res -= 1
            break

if N >= 2 and A[0] == A[1]:
    res -= 1

print(res)

Submission status: Wrong Answer

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

A.sort()

dellist = list()
for i in range(N):
    for j in range(N):
        if A[i] % A[j]:
            dellist.append(i)

A = [A[i] for i in range(len(A)) if i in dellist]

cnt = 0
N = len(A)

for i in range(1, N+1):
    ai = A[i-1]
    for j in range(1, N+1):
        aj = A[j-1]
        if ai < aj and j != N:
            cnt += 1
            break
        if i == j and j != N:
            continue
        if ai % aj == 0 and j != N:
            break
        if j == N:
            cnt += 1
            break

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
for i in range(0,n):
  for j in range(0,i):
    if(arr[i]%arr[j] == 0):
      count += 1
      break
print(n-count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = Counter(A)
visited = [False] * N
res = 0

for i in range(N):
  if not visited[i] and c[A[i]] < 2:
    res += 1
    visited[i] = True
    for j in range(i+1, N):
      if not visited[j]:
        if A[j] % A[i] == 0:
          visited[j] = True

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
Alis = list(map(int, input().split()))
Alis.sort()
for a in Alis:
    if Alis.count(a) > 1:
        Alis.remove(a)
ans = 0
while Alis:
    ans += 1
    lis2 = []
    for j in range(1, len(Alis)):
        if Alis[j] % Alis[0]:
            lis2.append(Alis[j])
    Alis = lis2

print(ans)

Submission status: Wrong Answer

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

s = {}
max_ele = -10 ** 9
for i in range(n):
    s[arr[i]] = 1
    max_ele = max(max_ele, arr[i])

res = {}
for i in range(n):
    for j in range(arr[i]*2, max_ele + 1, arr[i]):
        if (j in s.keys()):
            res[j] = 1

if len(res) == 0:
    print(len(res))
else:
    print(len(s)-len(res))

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614


##### FAST INPUT #####
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        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")
##### END OF FAST INPUT #####
#import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    if n == 1:
        print(1)
        return
    nums = list(set(nums))
    nums.sort()
    if len(nums) == 1:
        print(0)
        return
    if nums[0] == 1:
        print(1)
        return
    
    n = len(nums)
    #nums = list(reversed(nums))
    checkList = [True] * n
    i = 0
    while i < n - 1:
        if not checkList[i]:
            i += 1
            continue
        j = i + 1
        
        pFront = j
        pRear = n - 1

        while True:
            pMid = (pFront + pRear) // 2
            if nums[pFront] * 2 >= nums[i]:
                j = pFront
                break
            if nums[pRear] * 2 < nums[i]:
                j = pRear
                break
            if nums[pMid] * 2 >= nums[i]:
                pRear = pMid - 1
            else:
                pFront = pMid + 1

        while j < n:
            if nums[j] % nums[i] == 0:
                checkList[j] = False
            j += 1
        i += 1
        #print(nums)
        #print(checkList)
    print(sum(checkList))


    
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans = []
for i in range(N):
    count = 0
    for j in range(N):
        if(i == j):
            continue
        if(A[i] % A[j] == 0):
            break
        else:
            count += 1
            if(count == N - 1):
                ans.append(i)
                break

print(len(set(ans)))

Submission status: Wrong Answer

Solution code:
import collections,math
def primeFactors(n): 
    num=1  
    val=0
    while n % 2 == 0: 
        val=1 
        n = n / 2
    if val==1:
        num=num*2
    for i in range(3,int(math.sqrt(n))+1,2):
        val=0
        while n % i== 0: 
            val=1 
            n = n / i
        if val==1:
            num=num*i
    if n > 2: 
        num=num*n
    return num
n=int(input())
l=list(map(int, input().split()))
l.sort()
d=collections.Counter(l)
cnt=0
if d[l[0]]==1:
    cnt=1
pro=l[0]
if l[0]%2==0:
    pro=2
else:
    num=primeFactors(l[0])
    pro=num
for i in range(1,len(l)):
    if l[i]%2==0 and pro%2!=0 and d[l[i]]==1:
        pro=pro*2
        cnt=cnt+1
    elif l[i]%2==1 and d[l[i]]==1 and l[i]%pro!=0:
        cnt=cnt+1
        pro=(pro*primeFactors(l[i]))%1000000
print(cnt)

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 - 1 == x:
    if x % i == 0:
      if i in A:
        break
    if i == x:
      ans_list.append(1)
    i += 1
  

for i in A:
  div(i)
  
print(sum(ans_list))

Submission status: Wrong Answer

Solution code:
n = int(input())
L = list(map(int,input().split()))
L = list(set(L))
l = len(L)
if l == 1:
    print(0)
    exit()
L.sort()
#print(L)
dp = [0]*(L[-1]+1)

for i in range(l):
    j = 1
    while L[i]*(j+1) < len(dp):
        #print(L[i],(j+1),len(dp))
        if not dp[L[i]*(j+1)]:
            dp[L[i]*(j+1)] = 1
        j +=1
#print(dp)
cnt = 0
for i in range(l):
    if dp[L[i]] == 0:
        cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
def main(n,A):
    c = []
    for i in range(n):
        for j in range(n):
            if i ==j:
                break
            if A[i]%A[j] == 0:
                c.append(i)

    c = set(c)
    print(n - len(c))

main(n,A)

Submission status: Wrong Answer

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

a.sort(reverse=True)
cnt = 0
for i in range(1,len(a)+1):
    for j in reversed(range(i,len(a))):
        if a[i-1] % a[j] == 0:
            cnt += 1
            break
if a[n-1] % a[n-2] == 0:
    cnt += 1
print(n - cnt)

Submission status: Wrong Answer

Solution code:
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    a2=set(a)
    a2=list(sorted(a2))
    num3=0
    if a2[0]==1:
        if a.count(1)==1:
            ans=1
        else:
            ans=0
    else:
        len2=len(a2)
        def c1(num1):
            return a.count(num1)
        def l1():
            return len(a2)
        for i in range(len2):
            num4=a2[i-num3]/min(a2)
            num=0
            if c1(a2[i-num3])==1:
                for j in range(i-num3):
                    if a2[i-num3]%a2[j]==0:
                        num=1
                        a2.remove(a2[i-num3])
                        num3+=1
                        break
                    if num4<a2[j]:
                        break
                if num==0:
                    ans+=1
    print(ans)

solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
print(a)
count = 0
bl = []
for i in range(n):
    t = a[i]
    count+=1
    if i+1!=n:
        if t==a[i+1]:
            count-=1
            bl.append(i)
            continue
    for j in range(i):
        if j in bl: continue
        if t%a[j]==0:
            count-=1
            bl.append(i)
            break
print(count)

Submission status: Wrong Answer

Solution code:
A1 = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
N = A1[0]
i_list=[]
for i in range(N):
  for j in range(N):
    if i!=j and p[i] % p[j]==0:
      i_list.append(i)
      break
new_list=[]
for i in range(int(len(i_list))):
  j=i_list[i]
  new_list.append(p[j])
print(new_list)
check = set(p) ^ set(new_list)
print(int(len(check)))

Submission status: Wrong Answer

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

if len(B)>=2:
    NotD = 0
    for T in range(1,len(B)):
        Target = B[T]
        Count = 0
        if A.count(Target)==1:
            for TT in range(0,T):
                BY = B[TT]
                if Target%BY==0:
                    break
                else:
                    Count += 1
            if Count==T:
                NotD += 1
    print(NotD+1)
elif len(B)==1 and len(A)==1:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

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

res = {}

sorted_p = sorted(pi)
for p in sorted_p:
    flag = True
    for div in res.keys():
        if p == div:
            flag = False
            res[p] += 1
            break
        elif div > (p/2):
            break
        elif p % div == 0:
            flag = False
            break
    if flag:
        res[p] = 1

res_count = 0
if N == 1:
    res_count = 1
elif len(res) != 1:
    for v in res.values():
        res_count += v

print(res_count)

Submission status: Wrong Answer

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

cnt = [0 for i in range(10 ** 6 + 1)]
bunpu = set()
for _a in a:
  bunpu.add(_a)
  cnt[_a] += 1

ans = n
for _a in a:
  flag = True
  i = 1
  while i * i <= _a:
    if _a % i == 0:
      if i in bunpu:
        flag = False
        break
      if i != 1 and _a // i in bunpu:
        flag = False
        break
    i += 2 if i >= 3 else 1
  if (not flag) or cnt[_a] > 1:
    ans -= 1

print(ans)

Submission status: Wrong Answer

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

if len(set(A)) == 1 or 1 in set(A):
    print(0)
    sys.exit()

heapq.heapify(A)
ans = []
while A:
    place = []
    d = heapq.heappop(A)
    ans.append(d)
    while A:
        tmp = heapq.heappop(A)
        if tmp % d != 0:
            place.append(tmp)
    for p in place:
        heapq.heappush(A, p)

print(len(ans))

Submission status: Wrong Answer

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
N=int(input())
hitoketa=[]
count=0
A=list(map(int,input().split()))
A=list(set(A))
if len(A)==1:
    print(0)
    exit()
A.sort()
owari=set()
#print(prime_factorize(12))
for i in range(len(A)):
    test=0
    for j in owari:
        if A[i]%j==0:
            test=1
            continue
    owari.add(A[i])
    if test==0:
        count+=1
print(count)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

c = {}
for i in a:
    if i in c:
        c[i] += 1
    else:
        c[i] = 1

a = []
for i in c.keys():
    if c[i] == 1:
        a.append(i)
a.sort()

b = set()

answer = 0
for i in a:
    d = set()
    for j in range(1, i):
        if i % j == 0:
            d.add(j)
            d.add(i // j)
        if j * j >= i:
            break

    f = True
    for j in d:
        if j in b:
            f = False
    if f:
        answer += 1
    b.add(i)

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import bisect

input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)
c = sorted(a)
r = []
if len(set(a)) == 1:
    print(0)
    exit()

for i in b:
    ind = bisect.bisect(c, i)
    for k in c[:ind]:
        if a.index(i) == a.index(k):
            continue
        if i % k == 0:
            r.append(i)
            break

print(n - len(set(r)))

Submission status: Wrong Answer

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

ans = 0 
a.sort(reverse=True)

for i in range(n):
    fl = 0
    for j in range(i+1,n):
        if i != j:
            if a[i] % a[j] == 0:
                fl += 1
                break
    if fl == 0:
        ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = list(map(int,input().split()))
A.sort()
#print(A)
ther = N

for i in range(N):
    if A[i]> A[N-1]//2:
        ther = i
        break

if ther == 0:
    print(0)
    exit()

#print(ther)
result = 0

for i in range(N):
    for j in range(ther):
        if A[i]!=A[j]:
            if (A[i]%A[j])==0:
                break
    else:
        result+=1

print(result)

Submission status: Wrong Answer

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

k = list(set(A))
if (len(k) == 1):
    print(0)
    exit()
j = 0
ans = deque()
while j <= N - 1:
    if (j < N - 1):
        if (A[0] == A[j] and A[j] == A[j + 1]):
            j += 1
            continue

    if (j == 0 and A[j] != A[j + 1]):
        ans.append(j)
        j += 1
        continue
    check = False
    for i in range(0, j):
        # iとjが同じとき
        if (i == j):
            continue

        if (A[j] % A[i] == 0):
            check = True
            break

        if (i < N - 2):
            if (A[j] % A[i + 2] == 0):
                check = True

    if (not check):
        ans.append(j)
    j += 1

print(len(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
def divisors(n):
	i = 1
	div = []
	while i <= math.sqrt(n):
		if (n % i == 0):
			if (n //i == i) : 
				div+=[i] 
			else:
				div+=[i,n//i]
		i+=1
	return div
	
n = int(input())
arr = list(map(int,input().split()))
d = defaultdict(int)
for i in arr:
	d[i]+=1
ans = 0
for i in arr:
	if d[i]!=1:
		continue
	temp = divisors(i)
	f = 0
	for j in temp:
		if j!=i:
			if d[j]==1:
				f = 1
				break
	if f==0:
		ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def div(arr, n):
    s = dict()


    max_ele = -10 ** 9
    for i in range(n):
        s[arr[i]] = 1

        max_ele = max(max_ele, arr[i])

    res = dict()
    for i in range(n):

        if (arr[i] != 0):

            for j in range(arr[i] * 2,max_ele + 1, arr[i]):

                if (j in s.keys()):
                    res[j] = 1
    return res


n = int(input())
a = list(map(int, input().split()))
if len(list(set(a))) == 1:
    print(0)
else:
    b=[]
    t=0
    c=div(a,n)
    for i in range(len(a)):
        if a[i] not in c:
            b.append(a[i])
    d={}
    for i in b:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for key,val in d.items():
        if val==1:
            t+=1
    print(t)

Submission status: Wrong Answer

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

if n != 1:
    if a[0] == a[1]:
        cnt -= 1

for i in range(1, n):
    for j in range(i):
        if i != n-1:
            if a[i+1] == a[i]:
                cnt -= 1
                break
        if a[i] % a[j] == 0:
            cnt -= 1
            break
        if a[j] > a[i]//2+1:
            break
print(cnt)

Submission status: Wrong Answer

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

def q(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
count = 0
if apple.count(1) >= 2:
    count = 0
elif apple.count(1) == 1:
    count = 1
else:
    for i in apple:
        if len(q(i)) == 1:
            if apple.count(i) >= 2:
                pass
            else:
                count += 1
        else:
            num = i
            result = [i for i in range(1, num+1) if num % i ==0]
            result = result[:-1]
            if len(set(result) & set(apple)) == 0:
                count += 1
            else:
                pass

print(count)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

upper_bound = 200002

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

dup = [key for key, value in Counter(nums).items() if value >= 2]

out = set()
for d in dup:
	if d not in out: # O(1)
		to_add = [d * i for i in range(1, 2 + upper_bound // d) if i not in out] # O(k)
		for y in to_add: # O(k)
			out.add(y)

nums = sorted([x for x in nums if x not in out])

cnt = 0
for x in nums:
	if x not in out:
		cnt += 1
		to_add = [x * i for i in range(1, 2 + upper_bound // x) if i not in out]
		for y in to_add:
			out.add(y)

print(cnt)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
a = collections.Counter(p)
if len(a) >1 and a[p[n-1]] == 1:
    count +=1
for i in range(len(p)):
    if a[p[i]]>1:
        continue
    for j in reversed(range(i+1,len(p))):
        if p[i]< p[j]*2 and not p[i]==p[j]:
            count +=1
            break
        if p[i]%p[j] ==0:
            break
        if j == i+1:
            count +=1
if count >=1:
    print(count)
else:
    print(count)

Submission status: Wrong Answer

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

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
flag=0
cnt=0
for i in range(n):
    for j in range(i+1,n):
        if i==j:
            pass
        else:
            if a[i]%a[j]==0:
                flag=1
                break
    if flag==0:
        cnt+=1
    else:
        flag=0
print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
A=list(sorted(set(list(map(int,input().split())))))
ans=0
N=len(A)
for i in range(N):
    B=A.copy()
    t=B[i]
    j=max(bisect.bisect_left(B,t**0.5),i)
#     print(t,j)
    del B[j:]
    arr=[]
#     print(B)
    if N>1:
        if all(list(map(lambda x: t%x!=0, B))):
            ans+=1
#             print(i)
print(ans)

Submission status: Wrong Answer

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

    a.sort()

    count = 0
    for ite1, i in enumerate(a):
        for ite2, j in enumerate(a):
            if ite1 == ite2: 
                pass
            elif i%j == 0:
                break
            elif ite2 == len(a)-1:
                count += 1
            elif ite1 == len(a)-1 and ite2 == ite1-1:
                count += 1

    print(count)

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)
    
A = sorted(A)
check_list = [0] * (10**6 + 1)

for a in A:
    check_list[a] = 1

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

Submission status: Wrong Answer

Solution code:
import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

prime=set(seachPrimeNum(1000))
N=int(input())
A=list(map(int,input().split()))
if 1 in A:
    count=A.count(1)
    if count>=2:
        print(0)
    else:
        print(1)
    exit()
A.sort()
B=[i for i in A if i not in prime]
prime_list=[i for i in A if i in prime]
C=B.copy()
for i in B:
    for j in C:
        if i!=j and j%i==0:
            C.remove(j)
            break
dict={}
non=[]
if len(C)>=1:
    for c in C:
        for i in prime_list:
            if c%i==0:break
        else:non.append(c)
    prime_list.extend(non)

ans=0
for i in prime_list:
    if i not in dict:
        dict[i]=1
    else:
        dict[i]+=1
for k,v in dict.items():
    if v==1:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
s=set(k) & set(A)
print(len(s))

Submission status: Wrong Answer

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

alist.sort(reverse=True)
results = [True for i in range(n)]

for i in range(len(alist)):
    if results[i]!=False:
        ai = alist[i]
        if ai == 1:
            results[i] = True
        else:
            for j in reversed(range(i,len(alist))):
                aj = alist[j]
    #            print("{}[{}] {}[{}] {}/{}".format(ai,i,aj,j,(ai==aj),(ai%aj==0)))
                if i!=j and (ai==aj):
                    results[j] = False
                if i!=j and (ai%aj  == 0):
                    results[i] = False
                    break

print(results.count(True))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
b=a.copy()
a=set(a)
for i in range(1,b[-1]+1):
    bi=b.count(i)
    if bi>=2:
        for j in range(bi):
            b.remove(i)
a=list(a)
a.sort()
n=len(a)
m=len(b)
for i in range(m):
    for j in range(n):
        if 2*a[j]-1>b[i]:
            break
        elif b[i]%a[j]==0:
            b[i]=0
            break
print(m-b.count(0))

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
import numpy as np
from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
dbl = set([i[0] for i in c.items() if i[1] >= 2])

A.sort()
A = np.array(A)
Ac = np.copy(A)
ans = 0
for i in range(N):
    if Ac[i] == 0:
        continue
    elif A[i] not in dbl:
        ans += 1
    B = A % A[i]
    Ac = Ac * B

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

(n) = map(int, sys.stdin.readline().strip().split())
list_input = list(map(int, input().split()))

# 1の数をカウント
counts_one = list_input.count(1)
if counts_one == 1:
    print(counts_one)
    sys.exit()
elif counts_one > 1:
    print(0)
    sys.exit()

# 全て同じ数字かチェック
counts_same = list_input.count(list_input[0])
if counts_same == len(list_input):
    print(0)
    sys.exit()

counts_two = list_input.count(2)

anti_ans = 0
list_a = list_input.copy()
for i in list_input:
    for iloop in range(len(list_a)-1):
        if i == 2 and counts_two == 1:
            break
        if i == 2 and counts_two >= 2:
            anti_ans += 1
            break
        if i != 2 and counts_two >= 2 and i % 2 == 0:
            anti_ans += 1
            break
        if i % list_a[iloop+1] == 0:
            anti_ans += 1
            break
    # a = list_a.pop(0)
    # list_a.append(a)
    list_a.append(list_a.pop(0))
print(len(list_input) - anti_ans)

Submission status: Wrong Answer

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

for j in range(n):
    a2=list(map(lambda x: x%a[j],a))
    if a2.count(0)==1:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
a = []
cnt = 0

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
print(a)
for i in range(n):
    for j in range(n):
        if i == j:
            break
        if a[i] % a[j] == 0:
            cnt += 1
            break

print(n-cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
A.reverse()
times = 0
for n,i in enumerate(A):
    flag = 0
    for j in list(range(n-1,n))+list(range(n+1,len(A))):
       
        if A[j]<=i:
            if i%A[j]==0:
                flag = 1
                break
    if flag == 0:            
        times+=1   
print(times)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
sa = set(a)
sl = len(sa)
sa = list(sa)
for i in range(sl):
    count = 0
    for j in range(sl):
        if i == j:
            pass
        elif count == 0:
            if sa[i] % sa[j] == 0:
                count = 1
        else:
            break
    else:
        if count == 0:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()



maxa = max(a)+1

ans = [0]*maxa
for i in a:
	ans[i] = 1



for j in a:
	for i in range(j*2,10**6+1,j):
		if i>maxa-1:
			break
		ans[i] = 0

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
p=[[] for i in range(n)]
ans=n

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

for i in range(n):
    p[i]+=make_divisors(a[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(input().split())
a = [int(i) for i in a]
if len(set(a)) == 1:
  print(0)
  exit()

ans=0
for i in range(len(a)):
  #print(i,a[i])
  x=a[i]
  l=[a[j] for j in range(len(a)) if int(x/2) >= a[j] or (j != i and a[j] == x)]
  s=0
  #print(l)
  for ii in l:
    #print("check:", ii)
    if x % ii == 0:
      break
    else:
      s+=1
  if s == len(l):
    ans+=1
  #print("ans",ans)

print(ans)