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()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    i = 0
    for j in A:
        if i == j:
            isPrime[i] = False
        i = j
        if i > 10**3:
            continue
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter


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]


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

c = Counter(a)
new = []
for key, val in c.most_common():
    if val == 1:
        new.append(key)

ans = 0
for i in range(len(new)):
    flag = True
    for j in range(len(new)):
        if i != j and new[i] % new[j] == 0:
            flag = False
            break

    if flag:
        ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import random
#import time
from collections import defaultdict

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def main():
    #N = 20
    #A = [random.randint(1, int(1e6)) for _ in range(int(N))]
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    #t1 = time.time()
    A = list(set(A))
    N = len(A)
    A.sort()
#    B = [factorization(x) for x in A]
#    B.sort()

    d = defaultdict(list)
    B = []
    for x in A:
        x_fac = factorization(x)
        B.append(x_fac)
        for y in x_fac:
            d[y[0]].append(x)
    assert len(A)==len(B)
    #print(A)
    #print(B)
    #print(d)
    dp = [1] * (N+1)
    for i in range(1,N):
        bi = A[i]
        bi_fac = B[i]
        can_divide = False
        for y in bi_fac:
            for a in d[y[0]]:
                if bi % a == 0 and bi != a:
                    #print(a,bi)
                    can_divide = True
                    break
            if can_divide:
                break
        if can_divide:
            dp[i] = dp[i-1]
        else:
            dp[i] = dp[i-1] + 1
    print(dp[N-1])
    #print(time.time() - t1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A_set = list(set(A))
if len(A_set) == 1:
    print(0)
else:
    A_count = Counter(A)
    for i in range(len(A_set)):
        for j in range(len(A_set)):
            if(A_set[i]%A_set[j] == 0):
                A_set[i] = A_set[j]
                if(j != i):
                    d_num -= A_count[A_set[i]]
                break
    print(d_num)

Submission status: Wrong Answer

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

ans = 0
for i in range(N):
    if i == 0:
        if N != 1 and A[0] != A[1]:
            ans += 1
    else:
        if any(A[i] % A[i - j] == 0 for j in range(1, i + 1)):
            pass
        else:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def divisors(n):
    i = 2
    k = 0
    while i*i <= n:
        if n % i == 0 and ((n // i in A) or (i in A)):
            k += 1
        i += 1
    if k != 0:
        return False
    else:
        return True

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

cnt = 0
for j in A:
    if (j in A[:A.index(j)]) or (j in A[A.index(j)+1:]):
        continue
    elif divisors(j):
        cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
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]
    
def has_duplicates(seq):
    return len(seq) != len(set(seq))

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

for i in range(n):
    if i < n-1:
        if a[i] == a[i+1]:
            continue
    if i == 0:
        count += 1
    else:
        listi = make_divisors(a[i])
        b = a[:i]
        b = b + listi
        if has_duplicates(b) == False:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    if len(set(A)) == 1:
        print(0)
        return
    A.sort()
    pre = []
    cnt = 0
    for i in A:
        f = True
        for j in pre:
            if i % j == 0:
                f = False
        if f:
            cnt += 1
        pre.append(i)
    print(cnt)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    pool = set()
    count = 0
    for i in range(n):
        t = a[i]
        if i+1 < n and t == a[i+1]:
            pool.add(t)
        if t in pool:
            continue
        limit = t // 2 +1
        is_ok = True
        for j in pool:
            if j > limit:
                break
            elif t % j == 0:
                is_ok = False
                #print("bad", t, j)
                break
        if is_ok:
            #print("good", t)
            pool.add(t)
            count += 1
    print(count)

if __name__ == '__main__':
    main()

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(len(A)-1):
    flg = True
    for j in range(i+1, len(A)):
        if A[i] % A[j] == 0:
            flg = False
            break
    if flg == True:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

def get_prime_factors(n):
    dd = defaultdict(lambda: 0)
    if n > 1:
        i = 2
        while i * i <= n:
            if n % i == 0:
                dd[i] += 1
                n /= i
                i = 2
            else:
                i += 1
        dd[n] += 1
    return dd


def solve(N: int, A: "List[int]"):
    A = sorted(list(set(A)))
    if len(A) == 1:
        print(0)
        return
    
    count = 0

    dd = defaultdict(lambda: [0, -1])
    for a in A:
        d = get_prime_factors(a)

        flag = True
        for prime, value in d.items():
            dd_prime, dd_mn = dd[prime]
            
            if dd_mn == -1:
                dd_mn = a

            if dd_prime != 0 and a % dd_mn==0:
                flag = False

            dd[prime][0] += value
            dd[prime][1] = min(dd_mn, a)
        if flag:
            count+= 1

    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

a = [int(x) for x in input().split()]

a.sort()

ans = 0

for i in range(n):
	good = True
	for j in range(i):
		if a[i] % a[j] == 0:
			good = False
			break
	if good:
		ans += 1

if n > 1:
	if a[0] == a[1]:
		ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:

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

for i in range(1, n + 1):
    if len(a) < i:
        break
    t = a[0]
    a = list(filter(lambda x: x % t != 0, a)) + [t]

if len(a) == 1:
    print(0)
else:
    print(len(a))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import copy
from collections import Counter

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

counter = Counter(seq)
candidate = set(seq)

for k, v in counter.items():
    if v > 1:
        candidate.remove(k)
count = 0

for i, x in enumerate(sorted(candidate)):
    if x not in candidate:
        continue
    for y in copy.copy(candidate):
        if x == y:
            continue
        if y % x == 0:
            candidate.remove(y)

print(len(candidate))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


# def gcd(a, b):
#     if b == 0:
#         return a
#     return gcd(b, a % b)


# def lcm(a, b):
#     return a*b // gcd(a, b)


# def good(A, N):
#     # A = sorted(A)
#     ans = A[0]
#     # for i in range(1, N):
#     #     ans = fractions.gcd(A[i], ans)
#     for i in range(1, N):
#         ans = lcm(ans, A[i])
#     return ans

def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return is_prime


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
             return False
    return True


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def coprime(a, b):
    return gcd(a, b) == 1


def factorization(n):
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def main():
    N = I()
    A = LI()
    MX = 10**6 + 1
    ans = []

    # for i in range(N):
    #     n = []
    #     for j in range(N):
    #         if i == j:
    #             continue
    #         n.append(A[i] % A[j] != 0)
    #     if all(n):
    #         ans.append(i+1)

    # print(*ans)
    # print([A[i-1] for i in ans])

    a_map = Counter(A)

    n = MX
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = 1 in a_map
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        if i not in a_map:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False

    ans = 0
    for i in range(N):
        if is_prime[A[i]] and a_map[A[i]] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
#S = [[0 for j in range(3)] for i in range(2)]
S.sort()
if S[0]==1 and N==1:
    print(1)
    exit()
elif S[0]==1 and S[1]==0:
    print(0)
    exit()
elif S[0]==1:
    print(1)
    exit()
S.reverse()

candivcount=0
for i in range(N-1):
    for j in range(i+1,N):
        if S[i]%S[j]==0:
            candivcount+=1
            break
if S[N-2]==S[N-1]:
    candivcount+=1
    
print(N-candivcount)

Submission status: Wrong Answer

Solution code:
import collections
import math as mt 
def divisibilityCheck(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 n-len(res)
n=int(input())
l=list(map(int, input().split()))
d=collections.Counter(l)
num=divisibilityCheck(l,n)
for i in l:
    if d[i]>1 or i==0:
        num=num-1
print(num)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    m = A[-1]
    C = [False] * (m + 1)
    ans = 0
    for i in range(N):
        n = 1
        if C[A[i]] == False:
            if i == N - 1 or (i + 1 < N and not A[i] == A[i + 1]):
                ans += 1

        while True:
            nv = n * A[i]
            if nv > m:
                break
            if C[nv]:
                break
            else:
                C[nv] = True
            n += 1
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

count = 0
for i in range(len(a_uni)):
  if len(a_uni) == 1:
    print('0')
    exit()
  if is_prime(a_uni[i]):
    count += 1
    continue
  flg = 0
  for j in range(i):
    if a_uni[i] % a_uni[j] == 0:
      flg = 1
      break
  if flg == 0:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
good = N
i = 0
A = [int(x) for x in input().split()]
A.sort(reverse=True)
for i in range(N-1):
    counter = 0
    for j in range(i+1,N):
        if A[i]%A[j]==0:
            good -= 1
            break
print(good)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
c = list(range(n))
for i in range(n):
    for k in c:
        if(i != k):
            if(a[k] % a[i]==0):
                c.remove(k)
print(len(c))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
res = 0
f = False
for i in range(1, N):
    a = A[i]
    if a == A[i-1]:
        if f:
            res += 1
        else:
            res += 2
        f = True
        continue
    f = False
    sra = int(a ** 0.5) + 1
    for j in range(0, i):
        b = A[j]
        if a % b == 0:
            res += 1
            break
        if b > sra:
            break
print(N - res)

Submission status: Wrong Answer

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

l.sort()

i = 0
while i < len(l):
    if i != len(l)-1 and l[i] == l[i+1]:
        k = l[i]
        h = i
        while i < len(l) and l[i] == k:
            l.remove(k)
        i += 1
    else:
        l = l[:i+1] + [j for j in l[i+1:] if j % l[i] != 0]
        i += 1

print(len(l))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
a.sort()
b = []
ans = n

for i in a:
    flag = True
    for p in range(len(b)):
        j,k = b[p]
        if j > i/2:
            x,y = b[-1]
            if i == x:
                ans -= 1
                if y == 0:
                    ans -= 1
                    b[-1] = (x,1)
                flag = False
            break
        if i%j == 0:
            ans -= 1
            flag = False
            break
    if flag and i*2 < a[-1]:
        b.append((i,0))

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
counter = collections.Counter(A)
B = list(set(A))
count = 0
for i in range(len(B)):
    if counter[B[i]]>1:
        continue
    if B[i]==1:
        count += 1
        continue
    else:
        check = 0
        for j in range(2,int(B[i]**0.5)+1):
            if B[i]%j==0 and (j in counter or B[i]//j in counter):
                check += 1
                break
        if check==0:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
nums = list(map(int, input().split()))
count = [0]*N
nums.sort()
for i in range(N):
  fNum = nums[i]
  for j in range(1,i):
    if (count[j] == 1):
      continue
    elif (i == j):
      continue
    else:
      sNum = nums[j]
      if (sNum%fNum == 0):
      	count[j] += 1
answer = 0
for i in count:
  if (i == 0):
    answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
import math

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

A.sort()


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

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

if (A[0] == A[1]):
    count = 0
else:
    count = 1

for i in range(0, N):
    flag = True
    a = A[i]
    half_a = a/2
    for j in range(0, min(i + 2, N)):
        if (i != j and a % A[j] == 0):
            flag = False
            break

    if (flag):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import collections
import math
N = int(input())
A = input().split()

if N == 1:
  print(1)
else:
	for i in range(N):
		A[i] = int(A[i])
	A.sort()
	K = collections.Counter(A)
	num = list(K.keys())

	ans = len(num)
	lim = len(num)
	if len(num) == 1:
		print(0)
	else :
		for i in range(int(math.sqrt(len(num)))):
			if num[i] != 0:
				for j in range(i+1,len(num)):
					if num[j] != 0:
						if (num[j] % num[i]) == 0:
							ans -= 1
							num[j] = 0
                
		print(ans)

Submission status: Wrong Answer

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

a.sort()

for i in range(n):
    flag=True
    for j in range(n):
        if(((a[i]%a[j]) == 0) and (a[i] != a[j])):
            flag=False
    if(flag):
        x += 1

print(x)

Submission status: Wrong Answer

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

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

count = 0
found = False
for i in range(N):
    for j in range(N):
        if i != j:
            if A[i] % A[j] == 0:
                found = True
                break
            else:
                continue
        else:
            continue
    if not found:
        count = count + 1
    found = False
        


print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
cnt=0
v=[]
for i in range(n):
#  if not v:
#    cnt+=1
#    v.append(a[i])
  tmp=True  
  for j in range(n):
    if i==j:
      continue
    
    if a[i]%a[j]==0:
      tmp=False
      print(tmp,a[i],a[j])
  if tmp:
    cnt+=1
    v.append(a[i])
      
#print(v)
print(len(v))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

    ctr = Counter(A)
    memo = []
    dp = set()
    ans = 0

    for a in sorted(A):
        if a == 1:
            if ctr[a] == 1:
                ans = 1
            break

        if ctr[a] == 1:
            for v in memo:
                if v > int(a ** 0.5):
                    if a % v != 0:
                        ans += 1
                    break
                if a % v == 0:
                    break
            else:
                ans += 1

        memo.append(a)
        dp.add(a)

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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]

n=int(input())
A=list(map(int,input().split()))
tmp = {}
for a in A:
  tmp[a]=tmp.get(a,0)+1
A = [i for i in tmp if tmp[i]==1]
A.sort(reverse=True)
cnt = 0
for i,a in enumerate(A):
  ds = make_divisors(a)[:-1]
  isOK = True
  for d in ds:
    if d in A[i:]:
      isOK = False
      break
  if isOK:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors
for i in a:
    s=set(a)
    s.discard(i)
    if len(make_divisors(i)&s)==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
count = 0
if N == 1:
    print(0)
    exit()
for i in range(N):
    judge = True
    if i == 0:
        if A.count(A[i]) == 1:
            count += 1
        continue
    if A.count(A[i]) > 1:
        continue
    for j in range(i):
        if A[i] % A[j] == 0:
            judge = False
            break
    if judge:
        count += 1
print(count)

Submission status: Wrong Answer

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

# array = list(set(array) - set([x for x in set(array) if array.count(x) > 1]))
# array.sort()

i = 0;
while(i < len(array)):
    multi = [j * array[i] for j in range(2, int(array[-1] / array[i] + 1))]
    array = list(set(array) - set(multi))
    array.sort()
    i += 1
    
print(len(array))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    Pl = [A for A in input().split()]
    Pl = list(map(int, Pl))
    Pl.sort(reverse = True)
    #print(Pl)
    ans = len(Pl) * (len(Pl)-1) / 2
    #print(ans)
    count = 1
    for i in range(len(Pl)-1) :
        flag_i = 0
        flag_c = 0
        #print("--")
        #print(Pl[i])
        #print("--")
        for j in range(i+1 , len(Pl)) :
            val = Pl[i] % Pl[j]
            #print(val)
            if val != 0 and flag_i == 0:
                #print(i)
                flag_i = 1
                count += 1
            elif val == 0 and flag_c == 0 :
                flag_c = 1
        if flag_c == 1 and flag_i == 1 :
            count -= 1
    #print(Pl[:-1])
    if Pl[-1] in Pl[:-1] :
        count -= 1

    Pl = list(set(Pl))
    if len(Pl) == 1 :
        print("0")
    else :
        print(count)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()

x = A[0]
flag = True
for a in A:
    if a % x != 0:
        flag = False
if flag:
    print(0)
    exit()

used = [False] * A[-1]
ans = 0
for idx, a in enumerate(A):
    if used[a - 1]:
        continue
    ans += 1
    for j in range(2 * a, len(used) + 1, a):
        used[j - 1] = True
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys
import itertools
from math import gcd
from math import sqrt
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)
def is_prime(n):
   if n == 1:
       return False
   i = 2
   while i*i <= n:
       if n % i == 0:
           return False
       i += 1
   return True
def factorization(n):
   arr = []
   temp = n
   for i in range(2, int(-(-n**0.5//1))+1):
       if temp%i==0:
           cnt=0
           while temp%i==0:
               cnt+=1
               temp //= i
           arr.append(i**cnt)
   if temp!=1:
       arr.append(temp)
   if arr==[]:
       arr.append(n)
   arr.append(n)
   return arr

N = ii()
A = [el for el in mips()]
if 1 in A:
    print(0) 
    sys.exit(0)
ans = N
table = dict()
for i in range(1,max(A)+1):
    table[i] = []
##同じ数狩り
L = sorted(A)
count = 0
i = 0
while i < N-1:
    while L[i] == L[i+1]:
        count += 1
        i += 1
        if i >= N-1:
            break
    i += 1
    if count >= 2:
        ans -= (count)
    count = 0
check = set()
for el in A:
    if is_prime(el) and el not in check:
        ans += 1
        table[el].append(el)
        check.add(el)
    else:
        table[el] = factorization(el)
L = sorted(A,reverse = True)
for el in L:
    looking = table[el]
    if len(looking) == 1:
        continue
    for c in looking:
        if c in A:
            A.remove(c)
            ans -= 1
if ans < -2 : 
    print(0)
    sys.exit(0)
if ans == -2:
    print(1)
    sys.exit(0)
print(ans)

Submission status: Wrong Answer

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

A.sort()
counter_ = 0
i = 0
div = []
same_num = []
judge = True
for i in range(N):
    for div_ in div:
        if A[i] == div_:
            if A[i] not in same_num:
                same_num.append(A[i])
        if A[i] % div_ == 0:
            counter_ += 1
            judge = False
            break
    if judge:
        div.append(A[i])
        
print(N - counter_ - len(same_num))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

A.sort()
# print(A)

ans = 0
for i in range(N):
    is_ok = True
    half = A[i] / 2
    for j in range(i+2):
        if i == j:
            continue
        if j == N:
            break
        if A[i] % A[j] == 0:
            # print("break {} {}".format(i, j))
            is_ok = False
            break
        if A[j] > half:
            break
    if is_ok:
        # print(A[i])
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
a = sorted(list(map(int,input().split())))
l = []
l.append(a[0])
su = a[0]
cou =[]
for i in range(1,n):
    b = a[i]
    if gcd(b,su)!=1:
      for j in range(len(l)):
        if b==l[j]:
          cou.append(b)
          break
        if b%l[j]==0:
            break
      else:
          l.append(b)
          su *= b
    else:
      l.append(b)
      su *= b
print(len(l)-len(set(cou)))

Submission status: Wrong Answer

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

count = 0

for i in range(N):
    qualify = 1
    for j in range(i+1, N):

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

    if i > 1 and A[i - 1] == A[i]:
        qualify = 0

    count += qualify


print(count)