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:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
n=int(input())
l=sorted(list(map(int,input().split())))

cnt=0
for i in range(n):
    j=0
    while j<i and l[j]*2<=l[i]:
        if l[i]%l[j]==0:
            cnt+=1
            break
        j+=1
        
#print(n-cnt)
cnt2=0
cntt=0
for i in range(n-1):
    if l[i]==l[i+1]:
        if cntt==0:
            cntt+=2
        else:
            cntt+=1
    else:
        cnt2+=cntt
        cntt=0
if cntt>0:
    cnt2+=cntt    
print(n-cnt-cnt2)

Submission status: Wrong Answer

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

l.sort()

i = 0
while i < len(l):
    if l[i] > 500000:
        break
    if l[i] > l[-1]/2:
        break
    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)
    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:
n = int(input())
ls = list(map(int,input().split()))
ls.sort()
if ls.count(min(ls)) == n:
    k = 0
else:
    k = 1
for i in range(1,n):
    for j in range(i):
        if i == j:
            continue
        if ls[i] >=2*ls[j] or ls[i] == ls[j]:
            p = ls[i]/ls[j]
            if p % 1 == 0:
                break
    else:
        k += 1
print(k)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
from collections import defaultdict
d = defaultdict(int)
ans = 0
for i in range(N):
    d[a[i]] += 1
for i in range(1,1001):
    if d[i] == 1:
        ans += 1
        for j in range(1,2+10**6//i):
            d[j*i] = 0
    elif d[i] >= 2:
        for j in range(1,2+10**6//i):
            d[j*i] = 0
for i in range(1001,1000001):
    if d[i] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
def map_all(es):
    return all([e == es[0] for e in es[1:]]) if es else False
if map_all(A):
    print(0)
else:
    B = list(set(A))
    C = [x for x in set(A) if A.count(x) > 1]
    l = len(B)
    k = len(C)
    ct = 1-k
    for i in range(1,l):
        for j in range(i):
            if B[i]%B[j] == 0:
                break
            elif j == i-1:
                ct = ct +1
    print(ct)

Submission status: Wrong Answer

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



cnt = Counter(A)
A.sort()
ans = 0
for i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    idx = bisect.bisect_left(A, pow(A[i],0.7))
    #print(pow(A[i],0.5),idx)
    J = min(idx+1,i)
    #J = i
    ok = True
    for j in range(J):
        #print(i,j)
        if A[i] % A[j] == 0:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
num_list = list(map(int, input().split()))
count=0


for i in range(N):
  for j in range(N):
    if i == j:
      break
    if num_list[i] % num_list[j]==0:
      count = count + 1
      break
    

print(N-count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted([int(i) for i in input().split()])
ok=False
ans=0

val=a[-1]

for i in range(1,n):
    if a[n-i-1]!=a[n-i]:
        ok=True
    if val%a[n-i-1]!=0:
        if a[n-i-1]!=a[n-i]:
            ans+=1
        else:
            ok=True
    val*=a[n-i-1]
if ok:

    print(ans)
else:
    print(n-ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
count = defaultdict(int)
for i in a:
    count[i] += 1

MAX_SIZE = max(a)+1
isprime = [True] * MAX_SIZE  
prime = []  
SPF = [None] * (MAX_SIZE)

def manipulated_seive(N):  
    isprime[0] = isprime[1] = False

    for i in range(2, N):  

        if isprime[i] == True:  
            prime.append(i)  

            SPF[i] = i  

        j = 0
        while (j < len(prime) and
               i * prime[j] < N and
                   prime[j] <= SPF[i]): 
          
            isprime[i * prime[j]] = False

            SPF[i * prime[j]] = prime[j] 
              
            j += 1

manipulated_seive(MAX_SIZE)
prime = set(prime)

a.sort()
ans = 0
div = []
for i in range(n):
    if count[a[i]]==1:
        if a[i] in prime:
            div.append(a[i])
            ans+=1
        else:
            fl = 0
            for j in div:
                if j<=a[i]/2:
                    if a[i]%j==0:
                        fl = 1
                        break
                else: break
            if fl==0:
                div.append(a[i])
                ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

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

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

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

    ax = []
    ans = j = a0 = 0

    i = 1
    while i < N:
        a0 = A[i-1]
        for x in ax:
            if a0 % x == 0:
                i += 1
                break
        else:
            if a0 <= AX2:
                ax.append(a0)
            if a0 == A[i]:
                for i in range(i+1, N):
                    if a0 != A[i]:
                        break
                else:
                    break
                continue
            ans += 1
            i += 1

    if A[-2] != A[-1]:
        a0 = A[-1]
        for x in ax:
            if a0 % x == 0:
                break
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    resolve()

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 = [key for key, val in c.most_common() if val == 1]
#div = [make_divisors(i) for i in new]

ans = 0
for i in a:
    val = set(a) & set(a)
    if len(val) == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
in_data = [int(x) for x in input().split(' ')]
result = 0

for i in range(n):
  ok_flg = True
  for j in range(n):
    if max(in_data) > in_data[i]:
      ok_flg = False
      break
    if i == j:
      continue
    if in_data[i]%in_data[j]==0:
      ok_flg = False
      break
  if ok_flg:
    result += 1

print(result)

Submission status: Wrong Answer

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

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

flag = [0 for _ in range(N)]

for n in range(N):
    if is_prime(A[n]): 
        flag[n] = 2
    if n > 0 and A[n-1] == A[n]:
        flag[n-1] = 1
        flag[n] = 1    

for n in range(N):
    if flag[n] == 1: continue

    for i in range(n+1,N):
        if flag[i] == 1: continue

        if flag[i] == 0 and A[i]%A[n] == 0:
            flag[i] = 1

print(flag.count(0)+flag.count(2))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
D = dict(Counter(A))

res = 0
for n in A:
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            if i in D:
                break
            a = n // i
            if i != n // i:
                if n == a and a in D and D[a] > 1:
                    break
                if n != a and a in D:
                    break
    else:
        # print(n)
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
import math

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

#a.sort()
ans = 0
for i in range(n):
    cnt = 0
    for j in reversed(range(n)):
        if i != j:
            if a[j] % a[i] != 0:
                cnt += 1
                if cnt == n-1:
                    ans += 1
            else:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
df = [0]*n

for i in range(n-1):
  if a[i]==a[i+1]:
    df[i]=1
    df[i+1]=1

b=[]
for i in range(n):
  if df[i] == 0:
    b.append(a[i])

i = 0
for i in range(len(b)-1):
  if b[i] != -1:
    for j in range(i+1,len(b)):
      if b[j] == -1:
        continue
      if b[j] % b[i] == 0:
        b[j] = -1

ans=0
for i in range(len(b)):
    ans += 1 if b[i] != -1 else 0

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
yaku = [[] for _ in range(N)]
d = defaultdict(int)
for i in a:
    d[i] += 1
for i in range(N):
    if d[a[i]] != 1:
        continue
    for j in range(1, int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            yaku[i].append(j)
            if j != a[i] // j:
                yaku[i].append(a[i]//j)
asort = sorted(a)
cnt = 0

for i in range(N):
    cntF = True
    for j in yaku[i]:
        tmp = bisect.bisect_left(asort, j)
        if a[i] % asort[tmp] == 0:
            if tmp == N - 1:
                continue
            if a[i] == asort[tmp]:
                if asort[tmp] != asort[tmp + 1]:
                    continue
            cntF = False
            break
    if cntF:
        cnt += 1

print(cnt)

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!=1 and j!=i:
			if d[j]==1:
				f = 1
				break
	if f==0:
		ans+=1
print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    p = min(max(a), int(a[i] ** 0.5))
    for j in range(1, p + 1):
        if a[i] % j == 0:
            spl[i].append(j)
            if  j != a[i] // j and j != 1:
                spl[i].append(a[i] // j)
for i in range(n):
    if any(spl[i][j] in a for j in range(len(spl[i]))):
        pass
    else:
        ans += 1
        check[i] = 1
for i in range(n):
    list = a
    if check[i] == 1 and a.count(a[i]) > 1:
        ans -= 1
print(ans)

Submission status: Wrong Answer

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


N=int(input())
a=list(map(int, input().split()))
A=list(set(a))
if len(A) ==1:
    c=0
else:
    c=len(A)
for i in range(len(A)):
    # print(A[i])
    arr = factorization(A[i])
    # print(arr)
    A_ = A[:i]+A[i+1:]
    for j in range(len(arr)):
        for k in range(arr[j][1]):
            # print(pow(arr[j][0],k+1))
            if A_.count(pow(arr[j][0],k+1))>0:
                c-=1
                # print('C',c)
                break
        else:
            continue
        break

print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())

from collections import defaultdict

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

d = defaultdict(int)

for el in a:
    d[el] += 1

count = 0

d = sorted(d.items(), reverse=True)
# wm = d[0][0]

while len(d):
    a, c = d.pop()
    if c == 1:
#         print(f'count {a=}, {c=}, {count=}, {d=}')
        count += 1
    if a == 1:
        break
    if len(d):
        m = d[0][0]
    else:
        m = a - 1
    if a * 2 <= m:
        d = [elm for elm in d if elm[0] % a]
    else:
        count += len(d)
        break

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
p = list(map(int, input().split()))
p.sort(reverse=True)
lst = p[:]
jdg = True
temp = p[:]
ans = 0
while temp:
    lst = []
    q = temp.pop()
    for i in temp:
        if i%q!=0: lst.append(i)
        if i==q:jdg=False
    if jdg:
        ans += 1
    temp = lst[:]

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
ans = 0
def get_factor(n):
   arr = []
   for i in range(2, int(-(-n**0.5//1))+1):
       if n%i == 0:
           cnt=0
           while n%i == 0:
               cnt += 1
               n //= i
               arr.append(i**cnt)
   if n != 1:
       arr.append(n)
   return arr
for i, num in enumerate(A_list):
    fact_list = get_factor(num)
    not_div_flg = True
    for j in fact_list:
        if j in A_list[:i]+A_list[i+1:]:
            not_div_flg = False
            break
        
    if not_div_flg: ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import random

def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

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

ans = 0

if len(A) > 1:
    for i in range(len(A)):
        if is_prime(A[i]):
            ans += 1
            continue
        for j in range(i+1):
            if A[j] > math.sqrt(A[i]):
                ans += 1
                break
            if A[i] % A[j] == 0:
                if j != i:
                    break
        else:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
N= int(input())
A = list(map(int, input().split()))
A.sort()
prod = math.prod(A)

count = 0

for i in range(N):
    qualify = 1

    if i < N-1 and A[i + 1] == A[i]:
        continue

    if i > 1 and A[i - 1] == A[i]:
        continue

    max_index = np.searchsorted(A, A[i]/2+1)
    for j in range(max_index):
        if (A[i] % A[j]) == 0:
            qualify = 0
            break


    count += qualify


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

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1:
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]
 
 
def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
if a[0] < a[1]:
  ans = 1
else:
  ans = 0
s.add(a[0])
for nm,i in enumerate(a[1:]):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct):
      c.add(num(div))
  if c&s == set() and nm < n-2 and a[nm+2] != i:
    ans += 1
  s.add(i)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
SUPER_A=10**6+1
n=int(input())
a_array=list(map(int,input().split()))
a_array.sort()
div_dict=defaultdict(bool)
count=0
for i in range(n):
    if 0 < i and (a_array[i-1]==a_array[i]):
        count+=1
        continue
    elif i < n-1 and (a_array[i]==a_array[i+1]):
        count+=1
        continue
    a=a_array[i]
    if div_dict[a]:
        count+=1
    else:
        for i in range(1,SUPER_A//a):
            div_dict[i*a]=True
print(n-count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
flag = True
A = list(set(A))
if len(A) == 1:
    print(0)
else:
    A.sort()
    tmp = []
    i = 0
    isDelete = False
    while True:
        tmp.append(A[i])
        for j in range(i+1, len(A)):
            if A[j]%A[i] != 0:
                tmp.append(A[j])
        A = tmp.copy()
        tmp = tmp[:i+1]
        if i >= len(A) - 2:
            break
        i += 1

    print(len(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = sorted(map(int, input().split()), reverse=True)
b = 0
#print(A)
for i in range(n):
  if i != 0:
    if A[i] == A[i-1]:
      continue
#  j = i+1
  if i == n-1:
    b += 1
    continue
  j = n-1
  while j > i:
    if A[i]%A[j] == 0:
      break
    if j == i+1 or 2*A[j] > A[i]:
      b += 1
      break
    j -= 1
print(b)

Submission status: Wrong Answer

Solution code:
N=list(map(int,input().split()))
A=list(map(int,input().split()))
A.sort()
 
ans=[]
ans_=[]
for a in A:
    for ans_idx in range(len(ans)+1):
        if ans_idx == len(ans):
            ans.append(a)
            ans_.append(a)
            break
            
        ans_temp=ans[ans_idx]
        
        if a/2 < ans_temp:
            ans.append(a)
            ans_.append(a)
            break
            
        if a % ans_temp == 0:
            if a in ans_:
                ans_.remove(a)
            break
        
print(len(ans_))

Submission status: Wrong Answer

Solution code:
import random
def is_prime(q, k=3):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q-1)
        t = d
        y = pow(a, t, q)
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q-1 and t & 1 == 0:
            return False
    return True

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

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

a.sort()
#print(a)

ans = 0
div = []
divP = []
if a[0] == a[1]:
    pass
else:
    ans += 1

if is_prime(a[0]):
    divP.append(a[0])
else:
    div.append(a[0])

for i in range(1, n-1):
    if a[i] == a[i-1]:
        pass
    elif a[i] == a[i+1]:
        if is_prime(a[i]):
            divP.append(a[i])
        else:
            div.append(a[i])
    else:
        if is_prime(a[i]):
            ans += 1
            divP.append(a[i])
        else:
            flg = True
            for j in divP:
                if j*2 > a[i]:
                    break
                if a[i] % j == 0:
                    flg = False
                    break
            if flg:
                for j in div:
                    if j * 2 > a[i]:
                        break
                    if a[i] % j == 0:
                        flg = False
                        break
            if flg:
                div.append(a[i])
                ans += 1
    #print(i, a[i], div, ans)

if a[n-2] == a[n-1]:
    pass
else:
    if is_prime(a[n-1]):
        ans += 1
    else:
        flg = True
        for j in divP:
            if j * 2 > a[n-1]:
                break
            if a[n-1] % j == 0:
                flg = False
                break
        if flg:
            for j in div:
                if j * 2 > a[n-1]:
                    break
                if a[n-1] % j == 0:
                    flg = False
                    break
        if flg:
            ans += 1

print(ans)

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]
            cnt = 0
            for j in result:
                if j in apple:
                    break
                else:
                    cnt += 1
                    if cnt == len(result):
                        count += 1
                    else:
                        pass
print(count)

Submission status: Wrong Answer

Solution code:
# D

M = int(input())
B = list(map(int,input().split()))

# 降順に並べ替え
B.sort(reverse=True)

A = list(dict.fromkeys(B))

ans = 0
N = len(A)

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

if M == 1:
  ans += 1
elif A[N-2] != A[N-1]:
  ans += 1

print(ans)

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()))
b = set()
add = b.add
if len(set(a)) == 1:
    print(0)
    exit()
a.sort()
cnt = 0

for i in a:
    flg = True
    l = set(make_divisors(i))
    if len(l & b) == 0:
        cnt += 1
    add(i)
print(cnt)

Submission status: Wrong Answer

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


n = int(input())
a = list(map(int, input().split()))
A = []
for i in range(n):
    if a.count(a[i]) == 1:
        A.append(a[i])

n = len(A)
ans = 0
prime_1 = False
if 1 in a:
    prime_1 = True

for i in range(n):
    if is_prime(A[i]):
        if prime_1 == False:
            ans += 1
            continue
    flag = True
    for j in range(n):
        if i != j and A[i] % A[j] == 0:
            flag = False
            break
    if n != 1 and flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import exit
N = int(input())
if N == 1:
  print(1)
  exit()
A = list(map(int, input().split()))

ban = set()
D = set()
for a in A:
  if a in D:
    ban.add(a)
  else:
    D.add(a)
D = deque(sorted(list(D)))
ans = 0
while D:
  ini = D.popleft()
  if not ini in ban:
    ans += 1
  if len(D) == 0:
    break
  print(D)
  for i in range(len(D)):
    d = D.popleft()
    if d % ini != 0:
      D.append(d)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
c = 0
A = sorted(set(A))
if len(A) > 1:
    for i, ai in enumerate(A):
        l_ai = math.sqrt(ai)
        for j, aj in enumerate(A):
            if ai != aj and ai % aj == 0:
                break
            if l_ai < aj:
                c += 1
                break
print(c)

Submission status: Wrong Answer

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

a_l.sort()
result_list=[]
while len(a_l)>0:
  a = a_l.pop(0)
#  print(f'a:{a}')
  if len(a_l) == 0 or a != a_l[0]:
    result_list.append(a)
  tmp = []
  for _ in a_l:
    if _ % a != 0:
#      print(f'_:{_}')
      tmp.append(_)
  a_l = tmp
#print(result_list)
#print(len(result_list))

Submission status: Wrong Answer

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

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

now = 0
b = [True]*n
for i in range(n):
    if now < a[i] < now * 2:
        continue
    if i < n-1 and a[i] == a[i+1]:
        b[i] = False
        b[i+1] = False
    now = a[i]
    for j in range(i+1, n):
        if a[j] % a[i] == 0:
            b[j] = False
print(sum(b))

Submission status: Wrong Answer

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

sum = 0

if N == 1:
    print(1)

while True:
    X = A.pop(0) #左端をとる
    
    i = len(A)

    OK = True

    for Y in reversed(A):
        i -= 1

        if Y == X:
            OK = False
            A.pop(i)

        elif Y%X == 0:
            A.pop(i)

    if OK:
        sum += 1

    if len(A) == 0:
        break

print(sum)

Submission status: Wrong Answer

Solution code:
#D
import collections
n=int(input())
a_list=list(map(int,input().split()))
a_list.sort()
b_list=collections.Counter(a_list)
b_list=b_list.keys()
j_list=[a_list[0]]
if len(b_list)==1:
    ans=0
elif 1 in a_list:
    ans=1
else:
    ans=1
    for i in a_list:
        for j in j_list:
            if i%j ==0:
                break
        else:
            ans+=1
            j_list.append(i)
            #print(i)
print(ans)

Submission status: Wrong Answer

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

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
    lower_divisors.remove(1)
    return lower_divisors + upper_divisors[::-1]

divisors_list = {}
for i in range(1,1000001):
  divisors_list[i] = []

#for k,i in enumerate(A):
 # for j in make_divisors(i):
  #  divisors_list[j] = k

pass_li = {}
for i in range(N):
  pass_li[i] = 1

for i in range(N):
  tmp = pass_li[i]
  for j in divisors_list[A[i]]:
    pass_li[j] = 0
  pass_li[i] = tmp 
  
  
print(sum(pass_li.values()))

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = list(map(int, input().split()))
flags = {i: 0 for i in range(N)}

ans = []

for i in range(N):
    if flags[i]:
        continue

    x = A[i]
    for j in range(N):
        if i == j:
            continue
        y = A[j]

        if flags[j]:
            continue
        if x > y:
            if x % y == 0:
                flags[i] = 1
                break
        if x == y:
            flags[i] = 1
            flags[j] = 1
            break
        else:
            if y % x == 0:
                flags[j] = 1
                break
#print(flags)
print(N-sum(flags.values()))

Submission status: Wrong Answer

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


N=int(input())
a=list(map(int, input().split()))
A=list(set(a))
if len(A) ==1:
    c=0
else:
    c=len(A)
for i in range(len(A)):
    # print(A[i])
    arr = factorization(A[i])
    # print(arr)
    A_ = A[:i]+A[i+1:]
    for j in range(len(arr)):
        for k in range(arr[j][1]):
            # print(pow(arr[j][0],k+1))
            if A_.count(pow(arr[j][0],k+1))>0:
                c-=1
                print('C',c)
                break
        else:
            continue
        break

print(c)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=map(int,input().split())
a=[b for b in a]
A=sorted(a)
B=A[1:]
for d in A:
    for b in B:
        if b%d==0 and b==d:
            A.remove(b)
answers=[]
for d in A:
   if a.count(d)!=1:
       continue
   else:
       answers.append(a)
print(len(answers))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
ans = n
for num, count in a.items():
    if count > 1:
        ans -= count
        continue
    if 1 in a and num != 1:
        ans -= count
        continue
    if num % 2 == 0:
        if num == 2:
            continue
        if 2 in a or (num // 2) in a:
            ans -= count
            continue
    i = 3
    while i * i <= num:
        if num % i == 0:
            if i in a or (num // i) in a:
                ans -= count
                break
        i += 2
print(ans)

Submission status: Wrong Answer

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

cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

dame_set = set()

a.sort()
ret = 0

for val in a:
    if val in dup:
        i = 1
        cnt = 10 ** 6 // val
        while i <= cnt:
            tmp = i * val
            if tmp in dame_set:
                break
            else:
                dame_set.add(i * val)
                i += 1
    else:
        if val in dame_set:
            continue
        else:
            ret += 1
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                tmp = i * val
                if tmp in dame_set:
                    break
                else:
                    dame_set.add(i * val)
                    i += 1

print(ret)

Submission status: Wrong Answer

Solution code:

def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    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] = False
#    print(is_prime)
    return [i for i in range(n+1) if is_prime[i]]

def solve():
#    memo = [1]*n
    cnt = 0
    for l in range(N):
        if A[l] < n:
            continue
        for k in q:
            if A[l]%(k) == 0 and A[l] > (k):
                cnt += 1
                break
    print(cnt)

if __name__=="__main__":
    n = int(input())
    a = list(map(int, input().split()))
    A = list(set(a))
#    print(A)
    N = len(A)
#    print(N)
    q = primes(n)
    #print(q)


    solve()