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 math
n = int(input())
a = [int(i) for i in input().split()]
from collections import Counter
a_cnt = Counter(a)
a = []
for k, v in a_cnt.items():
    if v == 1:
        a.append(k)
a.sort()
if len(a) > 0:
    sosu = [a[0]]
    dummy = [a[0]]
    for i in a[1:]:
        aaa = True
        for s in dummy:
            if i % s == 0:
                aaa = False
                if math.gcd(s, i) != s:
                    dummy.append(i)                
                break
        if aaa:
            sosu.append(i)
            dummy.append(i)
    print(len(sosu))
else:
    print(0)

Submission status: Wrong Answer

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

ttable = [[False for i in range(N)] for j in range(N)]

for i in range(N):
  for j in range(i, N):
    if As[i] == As[j]:
      ttable[i][j] = True
      ttable[j][i] = True
    elif As[i] % As[j] == 0:
      ttable[i][j] = True
    elif As[j] % As[i] == 0:
      ttable[j][i] = True
cnt = 0
for i in range(N):
  if True in ttable[i]:
    cnt += 1

print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
A = sorted(A)
if A[0] == 1:
    if N >= 2 and A[1] == 1:
        print(0)
    else:
        print(1)
    exit()



from collections import Counter

c = Counter(A)

a = 0
D = []
for i in c.keys():
    D.append(i)
    if c[i] >= 2:
        a += 1

D = sorted(D)

ans = 0
B = [0]*(10**6+1)
for i in range(len(D)):
    if B[D[i]] == 0:
        ans += 1

    for j in range(D[i],10**6+1,D[i]):
        B[j] = 1

print(ans-a)

Submission status: Wrong Answer

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

ans = 0
  
while True:
  d = A.pop(0)
  
  if d in A:
    pass
  else:
    A = list(reversed([ a for a in A[::-1] if a % d != 0]))
    ans += 1
  if A:
    True
  else:
    break
  
print(ans)

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

        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:
N = int(input())
A = list(map(int, input().split()))

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

A.sort()
a_list = [A[0]]
ans = 0
if A[0] != A[1]:
    ans += 1
for i in range(1, N):
    if A[i] == A[i-1]:
        continue
    for a in a_list:
        if A[i] % a == 0:
            break
    else:
        a_list.append(A[i])
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def calc():
    n, *a = map(int, open(0).read().split())
    if n == 0:
        return 0
    if n == 1:
        return 0

    appear = {}
    for x in a:
        if x in appear:
            appear[x] = False
        else:
            appear[x] = True

    r = set(a)
    count = 0
    for x in r:
        s = r & divs(x)
        if not s and appear[x]:
            count += 1
    return count

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:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from math import gcd

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = set()
    for i,l in Counter(A).items():
        if l == 1:
            B.add(i)
    A = sorted(B)
    N = len(A)
    # L = [1] * (N+1)
    # for i in range(N):
    #     L[i+1] = (L[i]*A[i])//gcd(L[i],A[i])
    ans = 0
    # print(A)
    # print(L)
    A.sort()
    for i in range(N):
        flag = True
        for j in range(i):
            if A[i] % A[j] == 0:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
if len(A) == 1:
    print(1)
    quit()
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
    return [i for i in range(n + 1) if is_prime[i]]

B = []
if A[0] != A[1]:
    B.append(A[0])
for i in range(1,N-1):
    a = A[i]
    if a != A[i-1] and a != A[i+1]:
        B.append(a)
if A[-1] != A[-2]:
    B.append(A[-1])
if len(B) == 0:
    print(0)
    quit()
b = B[-1]
X = set(primes(b))
A = set(B)
B = list(A&X)
A = list(A-X)
A.sort()
B.sort()
ans = []
while len(A) > 1:
    a = A[0]
    C = []
    if a != A[1]:
        ans.append(a)
    for aa in A:
        if aa % a != 0:
            C.append(aa)
    A = C
ans1 = []
for gen in ans:
    for b in B:
        if gen % b == 0:
            break
        if b > gen:
            ans1.append(gen)
            break
print(len(ans1)+len(B))

Submission status: Wrong Answer

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

A.sort()
L = []
pre_val = A[0]
count = 0
for a in A:
    if pre_val == a:
        count += 1
    else:
        temp = [pre_val, count]
        L.append(temp)
        count = 1
        pre_val = a
L.append([pre_val, count])

res = 0
for i in range(len(L)):
    flag = False
    Ai = L[i][0]
    for j in range(i):
        Aj = L[j][0]
        if Ai % Aj == 0:
            flag = True
            break
    if flag is False:
        if L[i][1] == 1:
            res += 1
        else:
            res += L[i][1] - 1
if len(L) == 1:
    print(0)
else:
    print(res)

Submission status: Wrong Answer

Solution code:
input()
A = sorted(map(int, input().split()))
B = 0
if 2 in A:
    A = [e for e in A if e % 2 !=0]
    B += 1

while True:
    p = A[0]
    if A.count(p) == 1:
        B +=1
    A = [e for e in A if e % p !=0]
    if not A:
        break
print(B)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(set(map(int, input().split())))
flag = True
count=0

if len(l) == 1:
  print(0)
else:
  for i in l:
    flag = True
    for j in l:
      if i != j:
        if i % j == 0:
          flag = False
          break
    
    if flag == True:
      count += 1
    flag = False

  print(count)

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 = sorted(a)

count = 0
for i in range(n):
    t = a[i]
    count+=1
    if i+1!=n:
        if t==a[i+1]:
            count-=1
            continue
    if i!=0:
        if t==a[i-1]:
            count-=1
            continue
    if is_prime(t): continue
    for j in range(i):
        if t%a[j]==0:
            count-=1
            break
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for i in range(n):
    j = i + 1
    while j < n:
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            break
        else:
            pass
        if j == n - 1:
            p += 1
        j += 1

print(p+1)

Submission status: Wrong Answer

Solution code:
import math

def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False

  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

n=int(input())
a=list(map(int, input().split()))
b=sorted(a)
if b[0]==b[-1]:
  print(0)
  exit()
tmp=set(b)
dic=list(tmp)

ans=0
prime=[]

for num in dic:
  if isPrime(num):
    prime.append(num)
    ans+=1

l=len(prime)

for i in dic:
  flag=1
  for j in prime:
    if i%j==0:
      flag=0
  
  if flag==1:
    prime.append(i)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N = int(sys.stdin.readline())
    X = list(map(int, sys.stdin.readline().split()))
    X.sort(reverse= True)
    ans = [0 for i in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            print(X[i]%X[j], X[i], X[j])
            if X[i]%X[j]==0:
                ans[i]+=1
                break
    z = ans.count(0)
    if z ==1:
        print(0)
    else:
        print(z)
            
            
            
    


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
INF = float('inf')
from collections import defaultdict
dic = defaultdict(lambda:INF)

used = defaultdict(lambda:0)
remove = defaultdict(lambda:0)

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

cnt1 = a.count(1)
if cnt1 == 1:
    print(1)
    exit()
elif cnt1 >1:
    print(0)
    exit()

from collections import Counter
def prime_factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

for aa in a:
    if used[aa]:
        remove[aa]=1
        continue
    c = prime_factorize(aa)
    flg = True
    for k in c.keys():
        if dic[k] == INF:
            dic[k] = aa//k
        elif (aa//k)%dic[k]==0:
            flg = False

    if flg:
        used[aa]=1

ans = sum(list(used.values()))-sum(list((remove.values())))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
 
A.sort(reverse=True)
for i in range(N):
  ans = True
  for j in range(i+1, N):
    if A[i] % A[j] == 0:
      break
    cnt += 1
      
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = list(map(int,input().split()))
a.sort()
d = deque(a)
e = deque(a)
#print(d)
for i in range(len(e)):
  for j in range(i+1,len(e)):
    if e[j] % e[i] == 0 and e[j] in d:
      d.remove(e[j])
      #print(d)
print(len(d))

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

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

A = Counter(A)
A = sorted(A.items(), key=lambda x: x[0])
# print(A)

ans = 0
divs = []
for i, n in A:
    flg = False
    if n > 1:
        continue
    for j in divs:
        if i % j == 0:
            flg = True
    if flg:
        pass
    else:
        divs.append(i)
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
a = list(map(int, input().split()))
yaku = [[] for _ in range(N)]
asort = sorted(a)

for i in range(N):
    tmp = bisect.bisect_left(asort, a[i])
    if tmp != N - 1:
        if a[i] == asort[tmp + 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)

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 == len(asort) - 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:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = set()
c = 0

for i in range(N):
    if i < N - 1:
        p = A[i + 1]
        if A[i] == A[i + 1]:
            B.add(A[i])
            continue
    Z = True
    for b in B:
        if A[i] % b == 0:
            Z = False
            break
    if Z:
        c += 1
        if A[i] <= 10 ** 3:
            B.add(A[i])
if N == 1:
    print(0)
else:
    print(c)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def primes_for(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, n+1):
        for j in range(i*2, n+1, i):
            is_prime[j] = False

    return [i for i in range(n+1) if is_prime[i]]


def main():
    N = INT()
    A = LIST()

    A.sort()
    P = primes_for(A[-1])
    c = Counter(A)
    ans = []
    for i in range(N):
        if A[i] in P:
            ans.append(A[i])
        else:
            for a in ans:
                if A[i] % a == 0: break
            else:
                ans.append(A[i])

    print(len([a for a in ans if c[a] == 1]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = list(set(a))
a.sort()
p = []

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

for a_i in a:
    if not p:
        p.append(a_i)
        continue
    warikireru = False
    for p_i in p:
        if a_i%p_i == 0:
            warikireru = True
            break
    if warikireru:
        continue
    else:
        p.append(a_i)

print(len(p))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
t=list(set(a))
l=len(t)
ans=l
for i in range(0,l):
  for j in range(0,l):
    if i!=j and t[i]%t[j]==0:
      ans=ans-1
      break
print(ans)

Submission status: Wrong Answer

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

count = 1

for i in range(n - 1):
    a_ = [t % a[i] for t in a]
    c = a_.count(0)
    
    if c == 1:
        count += 1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans = 0
for i in a:
    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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-06-14 21:22:25 +0900
# LastModified: 2020-06-14 22:20:19 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd

def main():
    n = int(input())
    a = list(map(int,input().split()))
    a.sort(reverse=True)
    count=0
    for i in range(0,n):
        for j in range(n-1,i,-1):
            if a[i]%a[j]==0:
                count+=1
                break
            if a[i]<a[j]*2:
                break

    if n>1 and a[n-1]==a[n-2]:
        count+=1

    print(n-count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A,reverse=True)
ans = 0
for i in range(N-1):
    x = 0
    for j in range(i+1,N):
        if A[i] % A[j] == 0:
            x += 1
    if x == 0:
        ans += 1
if A[N-1] != A[N-2]:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    if n==1:
        print(0)
        return

    arr.sort()
    #print(arr)
    ans=0
    for i in range(n):
        flg=0
        if i==0:
            if arr[i]!=arr[i+1]:
                ans+=1
            continue

        h=arr[i]//2+1
        for j in range(0,i):
            if arr[i]%arr[j]==0:
                flg=1
                break
            if arr[j] > h:
                break
        if flg==0:
            if (i+1)<n:
                if arr[i]==arr[i+1]:
                    flg=1
        if flg==0:
            ans+=1
    print(ans)
    return

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

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

Submission status: Wrong Answer

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

cnt = 0
for i in range(n):
    for j in range(1, n-i):
        if a[i]%a[i+j]==0:
            break
    else:
        try:
            if a[i]==a[-1]:
                if a[-1]!=a[-2]:
                    cnt += 1
                else:
                    pass
            else:
                cnt += 1
        except:
            pass
    continue

print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
A=sorted(set(A))
if len(A)==1:
    print(0)
else:
    for i in range(len(A)):
        k=0
        for j in range(i):
            if A[i]%A[j]==0:
                k=1
                break


        if k==0:
            
            ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
# from collections import Counter
a =  int(input())
A = list(map(int, input().split()))
A.sort()
d_num = a
div=[]
flag = False
for i in range(a):
    flag = False
    for j in range(len(div)):
        if(A[i]%div[j] == 0):
            d_num -= 1
            flag = True
            break
    if(flag==False):
        div.append(A[i])
    
print(d_num)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
li = list(set(list(map(int, input().split()))))
li.sort()

def del_(list_):
  key = list_.pop(0)
  new = [x for x in list_ if x % key != 0]
  return new

result = 0
i = 0
j = len(li)

if j == 1:  # 全部同じ数字
  print(0)
  sys.exit()
  
while i <= j:
  if len(li) > 1:
    li = del_(li)
    result += 1
  else:
    result += 1
    break
  i += 1

print(result)

Submission status: Wrong Answer

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

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;
    dic[n]=1;
    if(prime):
        return False;
    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] and fact(ls[0])):
            ans-=1;
            
    print(ans)
            
        





	
solve();

Submission status: Wrong Answer

Solution code:
N = int(input())
As = list(map(int, input().split()))
 
Fs = [1]*N
 
As.sort()
if N == 1:
  print(1)
  exit()

lst = [As[0]]

for i in range(1,N):
  if As[i] == As[i-1]:
    Fs[i] = 0
    if Fs[i-1] == 1:
      Fs[i-1] = 0
    continue
  for l in lst:
    flag = 1
    if As[i] < 2*l:
      break
    if As[i]%l == 0:
      Fs[i] = 0
      flag = 0
      break
    if flag == 1:
      lst.append(As[i])
        
print(sum(Fs))

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
count = 0
if(n == 1):
  print(1)
  sys.exit()
for i in range(1,n):
  flg = False
  for j in range(i):
    if(a[j] > a[i]/2):
      break
    if(a[i] % a[j] == 0):
      flg = True
      break
  if(flg == False):
    count += 1

if(a[0] != a[1]):
  count += 1
print(count)

Submission status: Wrong Answer

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

l = 0
nums_re = []
for i in set(nums):
    gs = nums.count(i)
    if gs >1:
        l += gs
        nums_re.append(i)
# print(nums_re)
# print(l)

for i in range(1, len(nums)):
    if nums[i] in nums_re:
        break
    for j in range(i):
        if nums[i]%nums[j] == 0:
            # print(i,j)
            # print(nums[i])
            # print(nums[j])
            # print('--')
            l += 1
            break
        
print(N-l)

Submission status: Wrong Answer

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

k = 0
b = 0
for l in range(n):
    if a[l] == 1:
        b = b + 1
        
if b == 0:
    for i in range(n):
        for j in range(n):
            if i == n-1 & j == n-1:
                break
            if a[j] != 0:
                if i != j:            
                    if a[i] % a[j] == 0:
                        a[i] = 0
                        break
                if j == n-1:
                    k = k + 1          
    print(k)
elif b == 1:
    print('1')
else:
    print('0')

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([A[0]])
ans = 1
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)

print(ans)

Submission status: Wrong Answer

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

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
#li.sort()
while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    #s_ba = math.ceil(math.sqrt(ba))+1
    #index = bisect.bisect_right(li, s_ba)
    tmp_li = li
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

def main():

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

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

    if A.count(A[0]) == 1:
        ans += 1

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
a_list = set(map(int, input().split()))

a_list = list(a_list)#sorted(list(a_list), reverse=True)
if len(a_list) == 1:
    print(0)
    sys.exit()
elif 1 in a_list:
    print(1)
    sys.exit()

counter = 0
while True:
    ai = 0
    rai = len(a_list) - 1
    while True:
        if rai <= 0:
            a_list.pop(ai)
            counter += 1
            break
        if a_list[ai] % a_list[rai] == 0:
            a_list.pop(ai)
            break
        rai -= 1
    if len(a_list) == 0:
        print(counter)
        break

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
hist = [ 0 for _ in range(1000000)]
for i in a:
  hist[i-1] += 1
a = list(set(a))

cnt = 0
for i in range(len(a)):
  flag = True
  if hist[a[i]-1] != 1:
    flag = False
  else:
    t = a[i] // 2
    for j in range(i):
      if a[j] > t:
        continue
      if a[i] % a[j] == 0:
        flag = False
        continue
  if flag:
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split())) 
res = 0
for i in range(n):
    for j in range(n):
        if  i == j:
           pass
        if a[j] >= a[i]:
            pass
        elif (a[i] == a[j]) or (a[i]%a[j] == 0):
            break
    else:
        res += 1
print(res)

Submission status: Wrong Answer

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

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

if len(a) == 1:
    print(0)
elif 1 in a:
    print(0)
else:
    count = 0
    for i in range(len(a)):
        if is_prime(a[i]):
            count += 1
        else:
            checker = 0
            for j in range(len(a)):
                if i != j and a[i] % a[j] == 0:
                    checker = 1
                    break
            if checker == 0:
                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:
        for b in A:
            if a != b and a % b == 0:
                divisibles.add(a)
    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(reverse = True)
p = 0

for i in range(n):
    j = i + 1
    while j < n:
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            break
        else:
            pass
        if j == n - 1:
            p += 1
        j += 1

print(p)