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

als = sorted(al)

from collections import Counter
c = Counter(als)

res = 0
kouho =[]

alss = list(set(als))
m = len(alss)

for i in range(m):
    j = alss[i]
    if c[j] >1:
        kouho.append(j)
        pass
    else:
        for k in kouho:
            if j % k ==0:
                break
        else:
            res += 1
            kouho.append(j)
            continue
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
import numpy as np
N = int(input())
A = [int(i) for i in input().split()] 
A.sort()
A = np.array(A)
 
ans = 0
while len(A)>0:
  div = A[0]
  ans += 1
  arr = np.mod(A, div)
  if len(A) > 2:
    if A[1] == div:
      ans -= 1
  A = A[arr>0]
    
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    prime = [1] * n
    for i in range(n):
        if prime[i] == 1:
            for j in range(i+1, n):
                if a[j] % a[i] == 0:
                    prime[j] = 0

    ans = sum(prime)
    print(ans if ans != 1 else 0)



if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def prime_fact(N):
    n = 2
    prime = []
    while n * n <= N:
        i = 0
        while N % n == 0:
            N //= n
            i += 1
        if i > 0:
            prime.append((n, i))
        n += 1
    if N != 1:
        prime.append((N, 1))
    return prime


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()

    ret = 0
    for i in range(N):
        N = A[i]
        st = prime_fact(N)
        flg = True
        for P, X in st:
            for x in range(1, X+1):
                if P ** x in A and P ** x != N:
                    flg = False
        if flg and A.count(N) == 1:
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A.sort()
d = deque()
for i in range(N-1):
    if A[i] != A[i+1]:
        d.append(A[i])
if A[N-1] != A[N-2]:
    d.append(A[N-1])

ans_que = deque()
ban = dict()
border = pow(10, 6)
while len(d):
    num = d.popleft()
    if ban.get(num) == None:
        ans_que.append(num)
        ban_num = num
        while ban_num <= border:
            ban[ban_num] = 1
            ban_num += num

print(len(ans_que))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
AA = [ False for i in range(N) ]

A.sort()

if A[0] == A[-1]:
  print(0)
else:
  for j in range(N):
    if j >= len(A):
      break
    for i in range(N):
      if i >= len(A):
        break
      if i == j :
        continue
      if A[i] % A[j] == 0:
        AA[i] = True
  count = 0
  for aa in AA:
    if aa == False:
      count += 1
  print(count)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = set(a)
b = c.copy()
for x in c:
    if (br(a,x) - bl(a,x)) >= 2:
        b.remove(x)
b = sorted(list(b))
print(b)
if len(b) == 0:
    print(0)
elif len(b) == 1:
    print(1)
else:
    ans = 1
    for i in range(1,len(b)):
        for j in range(0,i):
            if b[i] % b[j] == 0:
                break
            if j == i-1:
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    s = lower_divisors + upper_divisors[::-1]
    return s[1:]

n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
sy = set()
count = 0
if len(set(a)) == 1:
    print(0)
    exit()
ans = []
for i in range(n):
    flag = True
    for s in sy:
        if a[i] % s == 0:
            flag = False
            break
    if flag:
        ans.append(a[i])
    sy.add(a[i])
ans = Counter(ans)
for c,v in ans.items():
    if v == 1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
Nn = int(input())
List = list(set(list(map(int, input().split()))))
N = len(List)
count = 0
for i in range(N):
  x = List.pop(i)
  for j in range(N-1):
    if x % List[j] != 0:
      count += 1
      break
  List.insert(i, x)
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
len = len(A)
new = sorted(A, reverse=True)
cnt = 1
cnt2 = 1
for i in new:
  for j in new:
    if cnt != cnt2 and i%j == 0:
      len =len - 1
      break
    cnt2 += 1
  cnt += 1
print(len)

Submission status: Wrong Answer

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

for i in range(n):
    temp_count = 0
    for j in range(n):
        if i == j:
            continue
        if alist[i] % alist[j] != 0:
            temp_count += 1
        if temp_count == len(alist) - 1:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def soinsuu_bunkai(n):
    ret = {}
    p = 2
    while p * p <= n:
        while n % p == 0:
            ret[p]= ret[p]+1 if p in ret else 1
            n //= p
        p += 1
    if n != 1:
        ret[n] = 1
    return ret  

N,*A = map(int,open(0).read().split())
A.sort()
lst = []
for a in A:
    lst.append(soinsuu_bunkai(a))
    
#print(lst)  
cnt = 0
for i in range(N):
    flg = True
    for j in lst[i].keys():
        for k in lst[i+1:]:
            if j in k:
                flg = False
    if flg:
        cnt += 1
if cnt <= 1:
    print(0)
else:
    print(cnt + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, 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
    return lower_divisors + upper_divisors[::-1]
from collections import Counter
ans = 0
for i in range(n):
    if len(set(a) & set(make_divisors(a[i])))-1 == 0:
        ans += 1
cnt = Counter(a)
for i in cnt.values():
    if i > 1:
        ans -= i

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    if i != N-1:
        if A[i] == A[i+1]:
            continue
    elif i != 0:
        if A[i] == A[i-1]:
            continue
    
    flag = "OK"
    for j in range(i):
        if A[j] > A[i]/2:
            break
        if A[i]%A[j] == 0:
            flag = "OUT"
            break

    if flag == "OK":
        cnt += 1
    
print(cnt-1)

Submission status: Wrong Answer

Solution code:
def multi_diff(es):
    return es == [es[0]] * len(es) if es else False

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

if multi_diff(a):
    print(0)
else:
    a = list(set(a))
    a.sort()
    dele = []
    i = 0
    if len(a) == 1:
        print(1)
    else:    
        while i <= len(a)-1:
            for j in range(i+1, len(a)):
                if a[j] % a[i] == 0:
                    dele.append(j)
            for k in reversed(dele):
                a.pop(k)
            i += 1
            dele.clear()
        print(len(a))

Submission status: Wrong Answer

Solution code:
import numpy as np

def solve(A,N):
    value_count=0
    for i in range(len(A)):
        Ai=A[i]
        test_A=np.array(Ai)%A
        if(list(test_A).count(0)==1):
            value_count+=1
    return value_count
N=int(input())
A= np.array(list(map(int,input().split())))
if(len(list(set(A)))==1):
    print(0)
    exit()
A=list(set(A))

print(solve(A,N))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = sorted(list(map(int,input().split())))
if 1 < len(a):
    c = 1 if a[0] == a[1] else 0
else:
    c = 0
for i in range(3, n):
    x = a[i]
    for j in range(math.ceil(i/3)):
        if j == i:
            continue
        if (x % a[j] == 0) or (x % a[math.ceil(i/2)-j-1] == 0) or (x % a[math.ceil(i/2)+j+1] == 0) or (x % a[i-j-1] == 0):
            break
    else:
        continue
    c+=1
print(n-c)

Submission status: Wrong Answer

Solution code:
from math import sqrt
from sys import stdin
input = stdin.readline

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

is_continue = [False] * n

A.sort()
ans = 0

div_set = set([])


def div(x):
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            if i in div_set or x // i in div_set:
                div_set.add(x)
                return False
    div_set.add(x)
    return True


for i in range(n - 1):
    if A[i] in div_set:
        continue
    elif A[i] == A[i + 1]:
        div_set.add(A[i])
        continue
    elif div(A[i]):
        ans += 1

if A[n - 1] not in div_set and div(A[n - 1]):
    ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import Counter
from itertools import accumulate

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)
    A.sort()
    ans = [0]*N
    tmp = 1
    for i in range(N-1):
        tmp *= A[N-1-i]
        if tmp % A[N-2-i] == 0:
            ans[N-1-i] += 1
    ans = list(accumulate(ans))
    z = 0
    for i in range(N):
        if i == ans[i]:
            z += 1
    print(z)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A = set(A)
A = list(A)
i = 0
if len(A) == 1:
    print(0)
else:
    while i != len(A)-1:
        j = i+1
        while j < len(A):
            if A[j] % A[i] == 0:
                del A[j]
            else:
                j += 1
        i += 1
    print(len(A))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

A_list.sort(reverse=True)
ans_num = 0
reduce_flag = 1
for i in range(1, N):
    now_div = A_list.pop()
    temp_A_list = []
    temp_len = 0
    reduce_flag = 1
    ans_num += 1
    for j in range(len(A_list)):
        now_A = A_list[j]
        if now_A % now_div == 0:
            if now_A == now_div:
                ans_num -= reduce_flag
            reduce_flag = 0
        else:
            temp_A_list.append(now_A)
            temp_len += 1
    if temp_len == 0:
        break
    A_list = temp_A_list

print(ans_num)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
aaa=list(map(int,input().split()))
aaa.sort()
ko=0
if [aaa[0]==aaa[i] for i in range(n)]:
  ko=1
  
aa=deque(aaa)
count=0

while aa:
    a=aa.popleft()
    if len(aa)!=0:
        b=aa.popleft()
    else:
      b=float("inf")
    if a!=b:
        count+=1
    if b!=float("inf"):
      aa.appendleft(b)
    k=len(aa)
    co=0
    while co!=k:
      t=aa.popleft()
      co+=1
      if t%a!=0:
        aa.append(t)
        
print(count if ko==0 else 0)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
A = Counter(list(map(int, input().split())))
A_keys = list(A.keys())
A_keys.sort()
for key in A_keys:
    if A[key] == 0:
        break
    for x in A_keys:
        if x != key and x % key == 0:
            A[x] = 0
ans = 0
for key in A_keys:
    if A[key] > 1 or A[key] == 0:
        continue
    ans += 1
print(ans)

Submission status: Wrong Answer

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

A = list(set(A))
if len(A) == 1:
    print(0)
    exit()
A.sort()
count = 0
divisor_list = []
while len(A) >= 1:
    B = []
    count += 1
    item = A[0]
    for j in list(A):
        if j % item != 0:
            B.append(j)
    A = B

print(count)

Submission status: Wrong Answer

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

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

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

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

    return arr

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

    d = defaultdict(list)
    B = []
    for x in A:
        x_fac = factorization(x)
        B.append(x_fac)
        for y in x_fac:
            d[y[0]].append(x)
    assert len(A)==len(B)
    #print(A)
    #print(B)
    #print(d)
    not_divided = set()
    for i in range(N):
        bi = A[i]
        bi_fac = B[i]
        can_divide = False
        for y in bi_fac:
            for a in d[y[0]]:
                if bi % a == 0 and bi != a:
                    #print(a,bi)
                    can_divide = True
                    break
                elif a > bi:
                    break
            if can_divide:
                break
        if can_divide or bi in dup:
            continue
        else:
            not_divided.add(bi)
    #print(A)
    #print(dup)
    #print(not_divided)
    print(len(not_divided))
    #print(time.time() - t1)


if __name__ == "__main__":
    main()

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 = sorted(data)
#data = a.copy()
prime = []
limit = math.sqrt(10**7+1)
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:
N = int(input())
A = list(set(map(int,input().split())))
B = [True]*len(A)
count = 0
A.sort()
for i in range(len(A)):
    if B[i]:
        for j in range(i+1,len(A)):
            if A[j]%A[i]==0:
                B[j] = False
    if B[i]:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
ans_list = []

def div(x):
  i = 1
  while i - 1 < x:
    if x % i == 0:
      if i in A:
        break
    if i == x:
      ans_list.append(1)
    i += 1
  

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    
        
    A=list(set(pin()))
    B=sorted(A)
    #print(B)


    if len(B)==1:
        print(0)#what?
        return
    
    
    must_see=[]
    must_see.append(B[0])
    
    """
    for cnt in range(1,10**7):
        if cnt>=N:break
        temp=B[cnt]
        cond=1
        for i in must_see:
            shit+=1
            if temp%i==0:
                cond=0
                break
        if cond==1:
            ans+=1
            must_see.append(temp)
    print(ans)
    """
    ans=B[:]
    x=[]
    for i in range(10**7):
        if i == len(ans):
            break
        
        temp=ans[i]
        if temp*2>B[-1]:
            break
        for j in ans:
        
            if j!=temp and j%temp==0:
                #iremasen
                continue
            else:
                #iremasu
                x.append(j)
        ans=x[:]
        #print(i,ans)
        x=[]
    print(len(ans))




#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0
if A[0] == 1:
    print(1)
    exit()
# ------------
is_prime = [True] * (10**6+1)
#print('a')
for i in range(n):
    #ll += 1
    #print(i)
    if is_prime[A[i]] == True:
        for j in range(2*A[i], 10**6+1,A[i]):
            is_prime[j] = False # その素数の倍数のやつ

 # -----------
for i in A:
    dic[i] += 1
cnt = 0
for a in A:
    if is_prime[a] and not dic[a] >= 2:
        #print(a)
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import math

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

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

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def make_divisors(n: int) -> list:
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if i == 1:
            continue
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

def main():
    n = i_input()
    num_list = i_list()

    num_list.sort()
    num_list = set(num_list)

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

    count = 0

    for num in num_list:
        yakusu_list = make_divisors(num)
        # if len(yakusu_list) == 0:
        #     count += 1
        #     continue
        # print(num, yakusu_list)
        for yakusu in yakusu_list:
            if yakusu in num_list:
                count += 1
                break

    print(n - count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from bisect import bisect_left
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
        index = bisect_left(dummy, i * 2)
        for s in dummy[:index]:
            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())
A = input().split()
A = [int(i) for i in A]
A.sort()
count=0
pak = []
for b, a in enumerate(A):
    for i in range(N):
        if A[i] % a ==0 and A[i] != a:
            count+=1
            A[i] = a
if count == 0:
    print(0)

Submission status: Wrong Answer

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

s = set()
x = a[0]

count = 0
for i in range(n):
    flg = True
    flg2 = False
    if i < n - 1 and a[i] == a[i + 1]:
        flg = False
        flg2 = True
    if a[i] in s:
        flg = False
        flg2 = False

    if flg:
        count += 1
    if flg or flg2:
        x = a[i]
        while x < 10 ** 6:
            s.add(x)
            x += a[i]
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

if len(set(search_list)) == 1:
    print(0)
    exit()

# エラトステネスの篩っぽく処理
ans_list = []
ans = 0

# ダブリを省くために先に数える
doubly = [x for x in search_list if search_list.count(x) > 1]

tmp = min(search_list)

while tmp <= max(search_list)/2:
    if tmp not in doubly:
        ans_list.append(tmp)
    search_list = [i for i in search_list if i % tmp != 0]
    if len(search_list) == 0:
        break
    else:
        tmp = min(search_list)

ans = len(ans_list) + len(search_list)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
def set_list(es):
    return len(list(set(es))) == 1
count = 0
if set_list(A):
    print(0)
    exit()
while A != []:
    if  len(A)>=2 and A[0] != A[1]:
        count += 1
    s = A.pop(0)
    B = [A[j] for j in range(len(A)) if A[j]%s != 0]
    A = B
    if set_list(A):
        print(count+1)
        exit()

Submission status: Wrong Answer

Solution code:
import numpy as np
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()))
a.sort()
flag = [True] * n
for i, num in enumerate(a):
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        flag[i] = False
        continue
    div = make_divisors(num)
    for d in div:
        if d == num:
            continue
        if d in a:
            flag[i] = False
print(np.count_nonzero(flag))

Submission status: Wrong Answer

Solution code:
def primes(n):
    is_prime = [i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0 for i in range(n + 1)]
    is_prime[1] = False
    is_prime[2] = is_prime[3] = is_prime[5] = is_prime[7] = True
    for p in range(3, int(n**0.5) + 1, 2):
        if not is_prime[p]:
            continue
        for i in range(p**2, n + 1, p):
            is_prime[i] = False
    return {i for i, p in enumerate(is_prime) if p}


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    if n == 1:
        print(1)
        return
    a.sort()
    if a[0] == 1:
        print(n - 1 + (a[1] == 1))
        return
    p = primes(max(a[-1], 10))
    b = set()
    c = 0
    for i, ai in enumerate(a):
        if i < n - 1 and ai == a[i + 1] or i > 0 and ai == a[i - 1]:
            b.add(ai)
            continue
        if ai in p:
            c += 1
            b.add(ai)
            continue
        for j in range(2, int(ai**0.5) + 1):
            if ai % j:
                continue
            if j in b or ai // j in b:
                break
        else:
            c += 1
            b.add(ai)
    print(c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
b = [False] * (max_a + 1)
a.sort()
a = a + [0]
b[a[0]] = True
count = 0
for i in range(1, n):
    flg = True
    if b[a[i]]:
        continue
    for j in range(i - 1, -1, -1):
        if a[i] % a[j] == 0 or a[i] == a[i+1]:
            flg = False
            b[a[i]] = True
            k = 2
            while k*a[i] < max_a:
                print(k)
                b[k*a[i]] = True
                k += 1
            break
    if flg:
        count += 1

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

Submission status: Wrong Answer

Solution code:
def get_primenumber(N):
    #素数リスト
    prime_list = [2]
    #3からNまでの数字を一つずつ取り出す
    for num in range(3,N+1,2):
      #取り出した数字が素数リストの要素で割れなければ素数リストに追加する
      if all( num % prime != 0 for prime in prime_list):
        prime_list.append(num)

    return prime_list

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

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

print(ans)

Submission status: Wrong Answer

Solution code:

_ = int(input())
a = sorted(list(set(map(int, input().split(" ")))))
n = len(a)
prime = []

while len(a) != 0:
    t = a[0]
    a = [ item for item in a if item % t != 0]
    prime.append(t)

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

Submission status: Wrong Answer

Solution code:
l = int(input())
n = [int(i) for i in input().split()]
u = n.copy()

n.sort()
u.sort(reverse=True)

counter = 0

for i in range(l):
  for j in range(l):
    if n.count(n[i]) >= 2:
      counter += 1
      break
    elif u[i] == n[j]:
      pass
    elif u[i] % n[j] == 0:
      counter += 1
      break
    else:
      pass

print(l - counter)

Submission status: Wrong Answer

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

A_list.sort()

cnt = 0

while len(A_list)>1:
    num = A_list.pop(0)
    if num != A_list[0]:
        cnt+=1
    A_small = [x for x in A_list if x < 2*num]
    len_small = len(A_small)
#    c = collections.Counter(A_small)
    while len(A_small)>1:
        num_s = A_small.pop(0)
        if num_s != A_small[0]:
            cnt+=1
        else:
            A_small = [x for x in A_small if x!=num_s]
    if len(A_small)==1:
        cnt+=1
    A_list = A_list[len_small:]
    A_list = [x for x in A_list if x%num!=0]

if len(A_list) == 1:
    cnt+=1

Submission status: Wrong Answer

Solution code:
from numba import jit
@jit
def func(n, a):
    ch = []
    count = 0
    for i in range(10**6+1):
        ch.append(0)
    for i in range(n):
        ch[a[i]] += 1
    for i in range(1, 10**6+1):
        if ch[i] >= 1:
            if i+(i//ch[i]) < 10**6+1:
                ch[i+(i//ch[i])] = ch[i]+1
    for i in range(10**6+1):
        if ch[i] == 1:
            count += 1
    print(count)
if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    func(n, a)