Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

if a[0] == 1:
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

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

print(ans)

Submission status: Wrong Answer

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

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

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

    return arr

  
n = int(input())
a_list = list(sorted(list(map(int,input().split()))))
sosuu = []
hukusuu = []

for i in range(len(a_list)-1,0,-1):
  if a_list[i] == a_list[i-1]:
    hukusuu.append(i)
    hukusuu.append(i-1)
    
hukusuu = sorted(list(set(hukusuu)),reverse=True)
for i in hukusuu:
  a_list.pop(i)

if len(a_list) == 0:
  print(0)
else:
  for i in range(len(a_list)-1,-1,-1):
    hoge = factorization(a_list[i])
    if len(hoge) == 1 and hoge[0][1] == 1:
      sosuu.append(a_list[i])
      a_list.pop(i)
  sosuu = sorted(sosuu)
  a_list = sorted(a_list)
  while 1:
    if len(a_list) == 0:
      break
    num = a_list.pop(0)
    iranai = False
    for i in sosuu:
      if num % i == 0:
        iranai = True
        break
      elif num < i*2:
        break
    if iranai == False:
      sosuu.append(num)
      sosuu = sorted(sosuu)

  print(len(sosuu))

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[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:
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(u[i]) >= 2:
      counter += 1
      break
    elif u[i] == n[j]:
      pass
    elif u[i] % n[j] == 0:
      counter += 1
      print(u[i],n[j])
      break
    else:
      pass

print(l - counter)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right

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

flag = [False for _ in range(n)]
i = 0
for i in range(n):
	if flag[i]:
		continue
	num = a[i]
	index = bisect_right(a,num)
	if i != index-1:
		for j in range(i,index):
			flag[j] = True
	index = bisect_left(a,num*2)
	if index >= len(a):
		break
	for j in range(index,n):
		if a[j] % num == 0:
			flag[j] = True

#print(a)
#print(flag)
print(flag.count(False))

Submission status: Wrong Answer

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

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[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if arr==[]:
        arr[n] = 1

    return arr

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    factors_dict = collections.defaultdict(int)

    count = 0
    counted_items = set()

    for i, a in enumerate(A):
        if A.count(a) > 1:
            continue
        primes = factorization(a)

        count_flag = True
        for k, v in primes.items():
            if not factors_dict[k] == 0 and not factors_dict[k] > v:
                count_flag = False
                break
        if count_flag == True:
            count += 1
            counted_items.add(a)
            for k, v in primes.items():
                factors_dict[k] = max(v, factors_dict[k]) if factors_dict[k] != 0 else v
            continue
        else:
            break_flag = False
            for c in counted_items:
                if a % c == 0:
                    break_flag = True
                    break
            if break_flag == False:
                count += 1
                counted_items.add(a)

    print(count)
    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import collections

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    
    N = II()
    A = LI()
    As = sorted(A, reverse=True)
    ans = N
    c = collections.Counter(As)

    #if N == 1:
        #print(0)
    if len(set(A)) == 1:
        print(0)
    elif c[1] != 0:
        if c[1] == 1:
            print(1)
        else:
            print(0)
    else:
        for i in range(N-1):
            print("i", i)
            k = N-1
            if c[As[i]] >= 2:
                ans -= 1
                if i == N-2:
                    ans -= 1
            else:
                for j in range(N):
                    if k == i:
                        break
                    elif As[i] % As[k] == 0:
                        ans -= 1
                        break

                    k -= 1

        print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import copy

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

a.sort()

b = copy.deepcopy(a)
flag = []
num = []

for i in range(n):
    if i in flag:
        continue
    for j in range(i+1, n):
        if j in flag:
            continue
        if a[j] % a[i] == 0 and a[j] in b:
            flag.append(j)
            continue
        num.append(a[j])

print(len(num))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=N
for i in range(N-1):
  if A[i]==A[i+1]:
    ans-=1
  else:  
    for k in range(0,i):
      if A[i]%A[k]==0:
        ans-=1
        break
      if A[k]>(A[i])**(1/2):
        break
for i in range(N-1):
  if A[N-1]%A[i]==0:
    ans-=1
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
def solve():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    ans = []
    while a:
        p = a[0]
        if len(a) > 1:
            if p == a[1]:
                a = [e for e in a if e != p]
                continue
        ans.append(p)
        a = [e for e in a if e % p != 0]
    print(len(ans))






if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    A.sort()
    divisible = [False] * N

    for i in range(N):
        for j in range(i, N):
            if not divisible[j] and i != j:
                if A[j] % A[i] ==0:
                    divisible[j] = True

    print(divisible.count(False))

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    a_set = set(a)
    eli = []
    res = 0
    pre = -1
    pref = 1
    for e in range(10 ** 3 + 1):
        if e in a_set:
            eli.append(e)
    for i in a:
        flag = 1
        for e in eli:
            if i != e and i % e == 0:
                flag = 0
        if pref and pre == i:
            flag = 0
            pref = 0
            res -= 1
        elif pre == i:
            flag = 0
        else:
            pref = 1
        if flag:
            res += 1
        pre = i
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
ans = 0
B = A
A.sort()
if A[0] == 1:
  print(1)
elif [i for i in A if i % A[0] != 0] == []:
  print(0)
else:
 while True:
    A = [i for i in A if i % A[0] != 0]
    if B == A:
      print(ans)
      break
    else:  
      ans +=1
      B = A

Submission status: Wrong Answer

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

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]

ans=0

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

if len(set(A))==1:
    print(0)
    exit()
A=merge_sort(A)
DP=[0]*N
DP[0]=0
for i in range(1,N):
    for j in reversed(range(i)):
        if A[i]%A[j]==0:
            DP[i]+=1
            break
print(N-sum(DP))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
A.sort()
D=defaultdict(int)
for some in A:
    D[some]+=1

n = 10**6
prime = {i for i in range(2, n)}
for i in range(2, n):
    if i in prime:
        for j in range(i*2, n, i):
            if j in prime:
                prime.remove(j)
ans = 0
for i in range(N):
    if D[A[i]] == 1:
        flag=True
        for j in range(i):
            if A[i] % A[j] == 0:
                flag = False 
                break
            if A[j]**2 > A[i]:
                break
        if flag:
            ans += 1
    else:
        pass
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

ans = 0
flag = False
for i, num in enumerate(A):
    for j, num in enumerate(A):
        if(i != j and (A[i] % A[j] != 0)):
            flag = True
        elif(i == j):
            continue
        else:
            flag = False
            break

    if(flag):
        ans = ans + 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
S=[]
S.append( [A[0],0] )
for a in A[1:]:
  flag=0
  for s in S:
    if a%s[0]==0:
      if s[0]==a: s[1]+=1
      flag=1
      break
  if flag==0:
    S.append( [a,0] )

ans=0
for s in S:
  if s[1]==0:
    ans+=1
print(S)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter
import sys

input=sys.stdin.readline

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

#O(nlogn)
A.sort()

if len(A) == 0:
  print(0)
if len(A) == 1:
  print(1)


cnt= 0 if len(A)>1 and A[0]!=A[1] else -1

while len(A)>0:
  #iの先頭要素を取り出す
  a = A[0]
  prev_len_A=len(A)
  #aで割り切れるやつは削除する
  A = [a_ for a_ in A if a_ % a != 0]
  cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
a = int(input())
numbers = [int(i) for i in input().split()]
b = 0
numbers = numbers[0:a]
for i in numbers:
    for j in numbers:
        if i%j == 0 and numbers.index(i) != numbers.index(j):
            break
    else:
        b += 1
print(b)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
ans=[1]*n
c=[]
for i in range(n):
  if a[0]!=a[i]:
    c.append(False)
    break
if False not in c:
  print(0)
else:
  for i in range(n):
    if ans[i]==1:
      for j in range(i+1,n):
        if a[i] %a[j] == 0:
          ans[i]=0
        elif a[j] %a[i] == 0:
          ans[j]=0
  print(sum(ans))

Submission status: Wrong Answer

Solution code:
def get_erato(data):
    prime = []
    limit = len(data)**0.5
    count = 0
    while True:
        p = data[0]

        if limit <= count:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
        if len(data)==0:
            return prime+data
        count+=1


N = int(input())
A = list(map(int,input().split()))
A.sort()
A = [item for item in A if A.count(item)==1]
ans = []
if len(A)>0:
    ans = get_erato(A)
print(len(ans))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    import collections
    def input():
        return sys.stdin.readline()[:-1]
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    B=[0]*N
    for i in range(N):
        if B[i]==0:
            for j in range(i+1,N):

                if A[j]%A[i]==0:
                    B[j]=1
    c=collections.Counter(A)
    sa=0
    for k in c.values():
        if k!=1:
            sa+=1
    
    result=0
    for l in B:
        if l==0:
            result+=1
    print(result-sa)

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
i = 1
for e in a:
  j = i
  while j<len(a):
    if a[j]%e!=0:
      j += 1
      continue
    else:
      del a[j]
  i += 1
if len(a)==1 and a[0]!=1:
  print(0)
else:
  print(len(a))

Submission status: Wrong Answer

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

for i in range(N):
  AS=set(A)
  M=len(AS)
  for j in range(M):
    B=AS.pop()
    if A[i]==B:
      break
    elif A[i]%B==0:
      break
    j+=1
  else:
    x+=1

print(x)

Submission status: Wrong Answer

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

setA = set(A)
result = 0

if N == 1:
    print(0)
else:
    for i in range(N):
        tmp = A[i]
        A[i] = 0
        setA = set(A)
        A[i] = tmp
        if 1 in setA:
            continue

        for a in setA:
            if a == 0:
                continue
            if A[i] % a == 0:
                break
            elif A[i] <= a:
                result += 1
                break
        else:
            result += 1

    print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    count = 0
    for j in range(N):
        if A[i]%A[j] != 0 and i != j: 
            count += 1
            if count == N-1:
                ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(list(set(a)),reverse=True)
if len(a) == 1:
    ans = 0
else:
    ans = 1
for i in range(len(a)):
    for j in range(len(a)-1,i,-1):
        if j == i+1:
            if a[i] // a[j] != a[i] / a[j]:
                ans += 1
                break
        if a[i] // a[j] != a[i] / a[j]:
            continue
        else:
            break
print(ans)

Submission status: Wrong Answer

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

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
flag=0
cnt=0
for i in range(n):
    for j in range(i+1,n):
        if i==j:
            pass
        elif a[i]%a[j]==0:
            flag=1
            break
    if flag==0:
        cnt+=1
    else:
        flag=0
print(cnt)

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
import numpy as np
from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
dbl = set([i[0] for i in c.items() if i[1] >= 2])

A.sort()
A = np.array(A)
Ac = np.copy(A)
ans = 0
for i in range(N):
    if Ac[i] == 0:
        continue
    elif A[i] not in dbl:
        ans += 1
    B = Ac % Ac[i]
    Ac = Ac * B

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 = []
A_set = list(set(A))
flag = False
if len(A_set) == 1:
    print(0)
else:
    for i in range(len(A_set)):
        flag = False
        for j in range(len(div)):
            if(A_set[i]%div[j] == 0):
                d_num -= 1
                flag = True
                break
        if flag == False:
            div.append(A_set[i])
    print(d_num-len(A)+len(A_set))

Submission status: Wrong Answer

Solution code:
# D - Not Divisible

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

b = [1]*n
for i in range(n):
    for j in range(i):
        #print(i,j)
        #print(a[i], "%", a[j] )
        if a[i]%a[j]==0:
            b[i]=0
            break

#check
#print(b)

print(sum(b))

Submission status: Wrong Answer

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

alist.sort(reverse=True)
results = [True for i in range(n)]

for i in range(len(alist)):
    result = False
    if results[i]!=False:
        ai = alist[i]
        if ai == 1:
            results[i] = True
        else:
            for j in reversed(range(i,len(alist))):
                result = True
                aj = alist[j]
    #            print("{}[{}] {}[{}] {}/{}".format(ai,i,aj,j,(ai==aj),(ai%aj==0)))
                if i!=j and (ai==aj):
                    results[j] = False
                if i!=j and (ai%aj  == 0):
                    result = False
                    break
    results[i] = result

print(results.count(True))

Submission status: Wrong Answer

Solution code:

import sys
import math
import itertools
import collections

# 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 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 solve(N:int,A:list) -> int:
    A.sort()
    if(A[0] == 1):return 0
    counter = 0
    primes = []
    no_primes = []
    black = []
    for a in A:
        if is_prime(a):
            if a in primes:
                if (a in black)== False:
                    counter -=1
                    black.append(a)
            else:
                counter += 1
                primes.append(a)
        else:
            no_primes.append(a)
    for n in no_primes:
        primes.sort()
        for p in primes:
            if n < p:
                counter += 1
                primes.append(n)
                break
            elif n % p == 0:
                break
    return counter
def main():
    N = int(input())
    A = list(map(int,input().split()))
    # solve()
    print(solve(N,A))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=list(set(a))
ans=[]
if len(a)==1:
    print(0)
    quit()
for i in range(len(a)):
    for j in range(len(a)):
        if a[i]%a[j]==0 and i!=j:
            ans.append(a[i])
            #割り切れたやつを追加
print(len(a)-len(set(ans)))

Submission status: Wrong Answer

Solution code:
import copy
import numpy as np

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

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

ary = np.array(al)

def divide(ar, i):
    new = ar%ar[i]
    ans = ar[new!=0]
    ans = np.append(ar[i], ans)
    return ans

j = 0
arra = ary
while True:
    if j < len(arra):
        if arra[j]*2 <= np.max(arra):
            arra = divide(arra, j)
            j += 1
        else:
            j += 1
            continue
    else:
        break
print(len(arra))

Submission status: Wrong Answer

Solution code:
import sys
import copy as cp
# from numba import jit
# @jit
def fac_serch():
    n = int(input())
    all_num = list(map(int,input().split()))
    all_num.sort()
    factor = []
    tmp_fac = list()
    if(all_num[0] == all_num[-1]):
        print(0)
        sys.exit()
    while(len(all_num)!=0):
        now_factor = all_num.pop(0)
        factor.append(now_factor)
        if(len(all_num) == 0):
            break
        tmp_fac = []
        for i in range(len(all_num)):
            # print(all_num,i)
            if(all_num[i]%now_factor != 0):
                tmp_fac.append(all_num[i])
        all_num = cp.copy(tmp_fac)
    return len(factor)
print(fac_serch())

Submission status: Wrong Answer

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

li.sort(reverse=True)
ans = []
kotae = 0
for i in range(a):
    for j in range(i+1,a):
            if not li[i] % li[j] == 0:
                ans.append(i)
    if ans.count(i) == a-1:
        kotae += 1
print(kotae)

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])
    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 = list(map(int, input().split()))
ans = [True] * len(A)


A.sort()

for i in range(len(A)):
        if A[i] > 1010:
                break
        for j in range(len(A)):
                if i == j:
                        continue
                if A[j] < A[i]:
                        continue
                if ans[j]:
                        if A[j] % A[i] == 0:
                                ans[j] = False


count = 0
for i in ans:
        if i:
                count += 1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

tmp = min(search_list)

while tmp <= max(search_list)/2:
    if search_list.count(tmp) == 1:
        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:
import copy 
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())))
new_A=list(set(A))
new_A.sort()
kotei_A=copy.copy(new_A)
tmp_A = copy.copy(new_A)
count=0

for i in kotei_A:
  tmp_A.remove(i)
  if(i//2!=1 and i%2==0 and 2 in new_A):
    new_A.remove(i)
    tmp_A = copy.copy(new_A)
    continue
  elif(i//3!=1 and i%3==0 and 3 in new_A):
    new_A.remove(i)
    tmp_A = copy.copy(new_A)
    continue
  elif(i//5!=1 and i%5==0 and 5 in new_A):
    new_A.remove(i)
    tmp_A = copy.copy(new_A)
    continue
  yaku=list(set(make_divisors(i)) & set(tmp_A))
  if(len(yaku)==0):
    count+=1
  else:
    new_A.remove(i)
  tmp_A = copy.copy(new_A)

if(len(new_A)==1):
  print(0)
else:
  print(count)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

res = {}

sorted_p = sorted(pi)
for p in sorted_p:
    flag = True
    for div in res.keys():
        if p == div:
            flag = False
            res[p] += 1
            break
        elif div > (p/2):
            break
        elif p % div == 0:
            flag = False
            break
    if flag:
        res[p] = 1

res_count = 0
if len(res) != 1:
    for v in res.values():
        res_count += v

print(res_count)

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
    if i == 0 and n > 1 and a[0] == a[1]:
        flg = False
    if a[i] in s:
        flg = False

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

Submission status: Wrong Answer

Solution code:
def prime_factorize_k(n):
    p = []
    while n % 2 == 0:
        if 2 not in p:
            p.append(2)
        n //= 2
    # 偶数はこれからは試さなくてよくなる
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in p:
                p.append(f)
            n //= f
        else:
            f += 2
    if n != 1 and n not in p:
        p.append(n)
    return p


n = int(input())
a = sorted(list(map(int, input().split())))
# print(a)
if len(set(a)) == 1:
    print(0)
    exit()

spl_list = set()
cnt = 0
for i in a:
    spl = set(prime_factorize_k(i))
    same = spl_list & set(spl)
    # print(spl, spl_list, same)

    if len(same) >= 1:
        continue

    if len(spl) == 1:
        spl_list = spl_list.union(spl)

    # print(spl, spl_list)
    cnt += 1
print(cnt)

Submission status: Wrong Answer

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

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

x = [A[0]]
for a in A[1:]:
    ok = True
    if is_prime(a): x.append(a)
    else:
        for i in x:
            if a%i == 0:
                ok = False
                break
        if ok: x.append(a)
print(len(x) if len(x) > 1 else 0)