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()
A.append(-1)

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

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

Submission status: Wrong Answer

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

A.sort()
if len(A) == 1:
    print(1)
    sys.exit(0)
elif A[0] == A[-1]:
    print(0)
    sys.exit(0)
elif A[0] == 1:
    print(1)
    sys.exit(0)


d =[]

for i in range(len(A)):
    flag = True
    for j in d:
        if A[i] % j == 0:
            flag = False
            break
    if flag:
        d.append(A[i])

print(len(d))

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 = 2 * 10**6
    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(len(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(1, 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())) 

ans = [1]*n

if sum(a)/n == a[0] and sum(a)/n == a[-1]:
    print(0)
    exit()

a.sort()

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

print(sum(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A, reverse=True)
count=0
for i, a in enumerate(A):
  for j in range(i+1, N):
    if a % A[j]==0:
      break
  else:
    count+=1
if N>1 and A[-1] == A[-2]:
  count-=1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
nun_list = list(map(int, input().split()))
count=0
hoge = len(nun_list) - 1

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


for i in range(1,n+1):
    if is_prime(nun_list[i-1]):
        count+=1
        continue
    tmp = 0
    for j in range(1,n+1):
        if i != j:
            if nun_list[i-1] % nun_list[j-1]  == 0:
                break
            else :
                tmp+=1
    if tmp == hoge:
        count+=1
print(count)

Submission status: Wrong Answer

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

def solution(N, A):
    A = set(A)
    if len(A) <= 1:
        return 0

    count = 0
    divisibles = set()
    for a in A:
        divisible_flag = False
        if divisible_flag:
            continue
        for b in A:
            # print(a, b)
            if a != b and a % b == 0:
                divisibles.add(a)
                divisible_flag = True
                break
    return len((set(A) - divisibles))

print(solution(N, A))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
cnt = 0
if len(set(A))==1:
    cnt += 1

while(len(A)>1):
    head = A.pop(0)
    chk = [a % head == 0 for a in A]

    cnt += chk.count(True)
    dif = 0
    for c in chk:
        if c:
            del A[dif + 0]
            dif = 0
        else:
            dif += 1
print(N - cnt)

Submission status: Wrong Answer

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

count = 0
if N == 1:
  print(1)
else:
  p = []
  if A[0] != A[1]:
    count+=1
    p.append(A[0])
  for i in range(1,N):
    flag = 1
    if A[i] != A[i-1]:
      for j in range(len(p)):
        if A[i] % p[j] == 0:
          flag = 0
          break
      if flag == 1:
        count+=1
        p.append(A[i])
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
#if(n!=1 and len(set(a))==1):print(0);exit()
prime_q = []
for i in range(10**6+2):
    prime_q.append(True)
d = {}
rea = []
for i in a:
    try:d[i] += 1
    except:d[i] = 1

for i in d.keys():
    if(d[i] == 1):rea.append(i)

ans = 0
for i in rea:
    if(prime_q[i] == True):
        ans+=1
        c = 1
        while(True):
            try:prime_q[i*c] = False
            except:break
            c+=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=int(input())
list = list(map(int, input().split()))
list.sort()
ans=0
counter = Counter(list)
if(counter[list[0]]==N):
  print("0")

else:
  for i in range (0,N):
    res=0
    for j in range(0,N):
      if(i!=j):
        if(list[i] % list[j]==0):
          res+=1
          break
    if(0<res):
      ans+=1

  print(N-ans)

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[i] // A[j] == 2:
            break

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

print(res)

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 = [int(i) for i in input().split()]

a.sort()
b = [a[0]]
c = []

for i in range(1,len(a)):
    if not a[i] in b:
        d = make_divisors(a[i])
        b.append(a[i])
        for j in d[1:-1]:
            if j in b:
                b.pop(-1)
                break
    elif a[i] in c:
        continue
    else:
        c.append(a[i])
print(len(b)-len(c))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
ans=n
for i in range(1,n):
    for k in range(i):
        if a[i]%a[k]==0:
            ans-=1
            break
print(ans)

Submission status: Wrong Answer

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

A = sorted(A, reverse=True)
B = sorted(A)
answer = 0

for i, Anumber in enumerate(A):
    for k, Bnumber in enumerate(B):

        if i == N - 1 - k:
            answer = answer + 1
            break
        if Anumber % Bnumber == 0:
            break

print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(input().split())
s_1 = [x for x in set(a) if a.count(x)>1]
l = len(s_1)
for i in range(n):
    a[i] = int(a[i])
a.sort()
count = 0
for i in range(n):
    flag = 0
    for j in range(i):
        if a[i]%a[j] == 0 or a[i] == a[j]:
            flag += 1 
            break
    if flag == 0:
        count += 1 

print(count-l)

Submission status: Wrong Answer

Solution code:
from sys import stdin

n = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

rest_lists = []

P.sort()

def return_filtered(div, rl):
    new = []
    protect = True
    for tgt in rl:
        if protect and tgt == div:
            new.append(tgt)
            protect = False
        elif tgt == div and len(new) >0:
            new.pop()
        elif not tgt % div == 0:
            new.append(tgt)
    return new

new_list = P
for i, p in enumerate(P):
    if p == 1:
        continue
    new_list = return_filtered(p, new_list)

print(len(new_list))

Submission status: Wrong Answer

Solution code:
from collections import deque,Counter
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
N = i()
A = l()
A.sort(reverse=True)
A = deque(A)
ans = 0
num = 0
def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
for i in range(N):
    a = A[0]
    A.popleft()
    if a in A:
        ans += 1
        if len(A) == 2:
            ans += 1
        continue
    divs = dv(a)
    if divs:
        for d in divs:
            if d in A:
                num = 1
                break
        if num :
            ans += 1
        num = 0
print(N-ans)

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()

dup = []

i = 0;
while(i < len(array)):
    if(array[i] in dup):
        del(array[i])
    else:
        dup = dup + [j * array[i] for j in range(2, int(array[-1] / array[i] + 1))]
        i += 1
    
print(len(array))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
flag=[0 for i in range(N)]
ikiteru=list(range(N))
#print(ikiteru)
lis=[]
for i in range(N):
  if(flag[i]==0):
    if(i<N-1):
      if(A[i+1]!=A[i]):
        ans+=1
    elif(A[i-1]!=A[i]):
      ans+=1
    j=1
    while(j*A[i]<=max(A)):
      if(j*A[i] in A):
        flag[A.index(j*A[i])]=1
      j+=1
print(ans)
#print(x)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter

N,*A = map(int, open(0).read().split())
Asl = sorted(set(A))
dupe = len([x for x in Counter(A).values() if x > 1])
d = deque(Asl)
s = set()
ans = 0
for i in range(len(d)):
    temp = d.popleft()
    for x in s:
        if temp % x == 0:
            s.add(temp)
            break
    else:
        s.add(temp)
        ans += 1
print(ans-dupe)

Submission status: Wrong Answer

Solution code:
from collections import deque 
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = deque(a)
y = [min(a)]
t = 0
while a:
    v = a.popleft()
    x = 0
    for j in y:
        if v % j == 0:
            break
        else:
            x += 1
        if v == j:
            t += 1
        if x == len(y):
            y.append(v)
print(len(y) - t)

Submission status: Wrong Answer

Solution code:
'''
Author : Shubhanshu Jain;
'''

import math
import random;
from collections import defaultdict 
mod =1000000007
r1 = lambda : int(input());
rm = lambda : map(int,input().split());
rms = lambda : map(str,input().split());
rls = lambda : list(rm())

def def_value(): 
	return "nan"

dic = defaultdict(def_value);
def fact(n ):
    flag = True;
    x =int(n**.5);
    prime = True;
    for i in range(2,x+1):
        if(n%i==0):
            prime = False;
            if(n//i==i):
                if(dic[i]!="nan"):
                    # print(i,n)
                    flag = False;
            else:
                if(dic[i]!="nan" or dic[n//i]!="nan"):
                
                    # print(i,n)
                    flag = False;
    
    if(dic[n]!="nan"):
        return False;
    dic[n]=1;
    if(prime):
        return True;
    return flag;
        
    
    
def solve():
    n = r1();
    ls = rls();
    ans = 0;
    ls.sort();
    k = -1;
    for i in ls:
        if(fact(i)):
            # print(i)
            ans+=1;
    if(len(ls)!=1):
        if(ls[0]==ls[1]):
            ans-=1;
            
    print(ans)
            
        





	
solve();

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal
#import itertools


N=int(input())
#N,K = map(int,input().split())
#B,W = map(int,input().split())
#T=int(input())
A = list(map(int,input().split()))
#S=str(input())
#A=[p for p in range(2*10**5)]
n=len(A)
A=sorted(A,reverse=True)
A=np.asarray(A)

#print(A)
c=0
for i in range(n-1):
    if A[i]==A[i+1]:
        continue
    #print(i)
    p=np.where(A<int(math.sqrt(A[i])))
    p=np.append(p,n)
    #print(p)
    I=p[0]

#    print(A[i],I)
    for j in range(I,n):
        #print(' ',j)

        #print(A[i],A[j])
        if A[i]%A[j]==0:
            c-=1
            break
    c+=1

print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
    
i = 0
j = 1
div = 0
cnt = 0

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    elif A[i] % A[j] == 0:
      div = 0
      break
    else:
      div = 1
  if div == 1:
    cnt += 1

print(cnt)

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[i] % A[j] == 0:
                if j != i:
                    break
        else:
            ans += 1

print(ans)

Submission status: Wrong Answer

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

n = int(input())
li = list(map(int,input().split()))
li.sort(reverse=True)
ans = 0

if len(set(li)) == 1:
    ans = 0
else:
    for i,num in enumerate(li,1):
        temp = 0
        j_list = list(range(i,n))
        for j in j_list:
            if num % li[j] == 0:
                break
            else:
                temp += 1
        if temp == n - i:
            ans += 1
print(ans)

Submission status: Wrong Answer

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



ans = -1
while a:
  l = []
  x = a.pop(0)
  ans += 1
  a_c = a.copy()
  while a_c:
    i = a_c.pop(0)
    if i%x != 0:
      l.append(i)
  a = l
      
print(ans)

Submission status: Wrong Answer

Solution code:
def calc():
    n, *a = map(int, open(0).read().split())
    counts = set()
    double = set()
    r = set(a)
    for x in a:
        if x in counts:
            double.add(x)
            continue
        s = r & divs(x)
        if not s:
            counts.add(x)
    return len(counts) - len(double)

def divs(n):
    ds = set()
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            ds.add(i)
            if i != n // i:
                ds.add(n//i)
    return ds

print(calc())

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
if 0 in a:
    ans=0
else:
    cnt=n
    for i in range(1,n):
        for j in range(n):
            if i<=j:
                break
            else:
                if a[i] % a[j] == 0:
                    cnt -= 1
                    break
    ans=cnt
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    pA = sorted(set(A), reverse=True)
    # print(pA)
    cnt = 0
    for i in range(len(pA)-1):
        surplus_cnt = 0
        for j in range(i+1,len(pA)):
            # print(i,j,pA,cnt)
            if pA[i] % pA[j] == 0:
                surplus_cnt = 0
                break
            else:
                surplus_cnt += 1
        if surplus_cnt > 0:
            cnt += 1
    if len(set(A)) >= 2:
        cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

if __name__ == '__main__':
    n = int(input().strip())
    a = np.array(input().strip().split()).astype(int)

    bool_mat = []
    ans = 0

    if 1 in a:
        if 1 in a[1:]:
            print(0)
        else:
            print(1)
    else:
        if 2 in a:
            a = np.array([i for i in a if not i % 2 == 0 or i == 2])

        for i in a:
            bool_mat.append(a % i == np.zeros(len(a)))

        for i in np.sum(bool_mat, axis=0):
            if i == 1:
                ans += 1
        print(ans)

Submission status: Wrong Answer

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

def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

for i in range(n):
    l1  = make_divisor_list(a[i])
    print(l1)
    if len(set(a)) != 1:
        if len(list(set(l1)&set(a))) == 1:
            s += 1
    else:
        s = 0
print(s)

Submission status: Wrong Answer

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

A = list(set(A))

A.sort()

print(A)

flag = 0

for i in range(1, len(A)):
  list=[]
  for p in range(1, len(A)):
    if A[p] % A[0] == 0:
      list.append(A[p])
  for p in range(len(list)):
    A.remove(list[p])
  flag += 1
  del A[0]
  if len(A) == 1:
    flag += 1
    break
  if len(A) == 0:
    break
  print(A)
    
print(flag)

Submission status: Wrong Answer

Solution code:
import numpy as np

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
List = list(map(int,input().split()))
List.sort()
ans = [List[0]]

for i in range(1,N):
  a = List[i]
  b = np.gcd(a, ans)
  if max(b) == 1:
    ans.append(a)
    
print(len(ans))

Submission status: Wrong Answer

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 1:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

import collections





n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = []
for e in c.most_common():
  if e[1] == 1:
    data.append(e[0])

#data = a.copy()
prime = []
limit = math.sqrt(10**6)
while len(data) > 0:
  p = data[0]
  if limit < p:
    prime += data
    break
  prime.append(p)
  data = [e for e in data if e % p != 0]
  #print(data)

print(len(prime))

Submission status: Wrong Answer

Solution code:
X= int(input())
N=[int(x) for x in input().split(" ")]
result=0

N.sort()
#print(N)
ban_num=[]

for i in range(X):
    #print(ban_num)
    if i in ban_num:
        continue
    else:
        X_I=N[i]

        for j in range(X):
            X_J=N[j]
            if i==j:
                continue
            elif X_I%X_J==0:
                #print(j)
                ban_num.append(j)
                break
            elif j==X-1:
                result=result+1

print(result)

Submission status: Wrong Answer

Solution code:
import copy

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

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

ans = 0
count = 0
while count < len(a):
    x = a[count]
    comb = factorization(x)
    lst = []
    a2 = copy.deepcopy(a)
    a2.remove(x)
    count += 1
    for i in comb:
        for j in range(i[1]):
            lst.append(i[0]**(j+1))
    count2 = 0
    for y in lst:
        if y in a2:
            break
        else:
            count2 += 1
            continue

    if count2 == len(lst):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    a.sort()
    if a[0]==a[-1]:
        print(0)
    else:
        ans=1
        b=[a[0]]
        c=0
        for i in range(1, n):
            k=a[i]
            for j in b:
                if j==k:
                    ans-=1
                if k%j==0:
                   c=1
                   break
            if c == 0:
                b.append(k)
                ans+=1
            c=0
        print(ans)
resolve()

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.6))
    #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())
a = list(map(int, input().split()))
tf = False
for i in range(n):
  if tf:
    break
  for j in range(n):
    if i == j:
      break
    if a[i] % a[j] != 0:
      print(i+1)
      tf = True
      break
if tf == False:
  print(0)

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(n-len(res))

Submission status: Wrong Answer

Solution code:

import glob
import os
import bisect

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        N = int( self.input_data())
        A = list(map(int, self.input_data().split()))

        A_sorted = sorted(A)

        index = 0
        remove_list = [0]* (N+1)

        for index in range(0, N-1):
            if remove_list[index] == 1:
                continue
            next = bisect.bisect_left(A_sorted, A_sorted[index]*2)
            for i in range(next, len(A_sorted)):
                if A_sorted[i] % A_sorted[index] == 0:
                    remove_list[i] = 1
            if A_sorted[index] == A_sorted[index+1]:
                remove_list[index] = 1
                remove_list[index+1] = 1

        count = 0
        for i in remove_list:
            count += (1 - i)
        print(str(count-1))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Wrong Answer

Solution code:
line = input()
line = line.rstrip().split(' ')
n = int(line[0])

line = input()
line = line.rstrip().split(' ')
a = []
for i in line:
    a.append(int(i))

a.sort()

answer = 0

for i in range(len(a)):
    dividable = False
    for j in range(i + 1):
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            dividable = True
            break

    if dividable == False:
        answer += 1

print(answer)

Submission status: Wrong Answer

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

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 main():
    ans = 0
    for i in range(N):
        if cnt[A[i]] > 1:
            ans += 1
        divList = make_divisors(A[i])
        for val in divList:
            if cnt[val] > 0 and val != A[i]:
                ans += 1
                break

    print(N-ans)

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
if N==1:
    print(1)
    exit()
 
A.sort()
 
if A[0]==1 and A[1]==1:
    print(0)
    exit()
 
elif A[0]==1 and A[1]!=1:
    print(1)
    exit()
 
ans = N
i=0

while True:
    now=A[i]
    l=len(A)
    j=i+1
    while True:
        if j>=len(A):
            break
        if A[j]%now==0:
            ans-=1
            A.remove(A[j]) 
        else:
            j+=1
    i+=1
    if i >= len(A):
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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())
A = sorted(list(map(int, input().split())))
E = set()
ans = 0
C = Counter(A)
for k in C.keys():
    if C[k] >= 2:
        ans -= 1
        continue
    else:
        a = prime_factorize(k)
        tmp = 1
        for i in range(len(a)):
            tmp *= a[i]
            if tmp in E:
                break
            else:
                continue
        else:
            ans += 1
        E.add(k)
if ans == -1:
    ans = 0
print(ans)

Submission status: Wrong Answer

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

if N >=2 and len(set(A)) == 1:
	print(0)
	exit()

A = sorted(A)

for i in range (0, N):
	for ele in A[i+1::]: 
		if ele % A[i] == 0: 
			A.remove(ele) 

print(len(A))

Submission status: Wrong Answer

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

cnt = 0
for i in sorted(a):
  flg = True
  for j in sorted(a):
    if i == j: continue
    if i < j: break
    if i % j == 0:
      flg = False
      break
  if flg: cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict

input()
# A = np.fromstring(input(), int, sep=' ')
A = list(map(int, input().split()))

counter = defaultdict(int)
for x in A:
    counter[x] += 1

A = np.array(list(set(A)))
A.sort()

count = 0
f = np.ones_like(A, dtype=bool)
for i, x in enumerate(A):
    if not f[i]:
        continue
    # print(i, x, count, A, f)

    if counter[x] == 1:
        count += 1

    if x <= 10**3+1:
        f[i+1:] &= (A[i+1:] % x != 0)

print(count)

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

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

print(len(ans))