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:
def NotDivisible():

    NumA = int(input())

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

    NumB = sorted(NumB)

    num = 0

    print(NumB)

    for i in range(NumA):

        result = [1]

        for j in range(i+1, NumA):
            data = NumB[j] % NumB[i]

            result.append(data)

        if min(result) == 0:
            num = num + 1

    print(num)

if __name__ == '__main__':
    NotDivisible()

Submission status: Wrong Answer

Solution code:
N =int(input())

A=list(map(int,input().split()))
count=0
for i in range(len(A)):
    for j in range(len(A)):
        if i!=j:
            r = round(A[i]%A[j],10)
            if r!=0:
                if A[i]!=A[j] and r!=0:
                    count +=1
                
print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
arg = list(map(int, input().split()))

ans = 0


for i in range(n):
    keisanflag = False
    iflag = False
    jflag = False
    for j in range(n):
        if i >= j:
            continue
        else:
            keisanflag = True
            if arg[i] == arg[j]:
                iflag = True
                jflag = True
                break

            elif arg[i] > arg[j]:
                num = arg[i] % arg[j]
                if num == 0:
                    iflag = True

            elif arg[j] > arg[i]:
                num = arg[j] % arg[i]
                if num == 0:
                    jflag = True

        if iflag and jflag:
            break

    if keisanflag == True:
        if iflag == False:
            ans += 1

print(ans)

Submission status: Wrong Answer

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

ans = 0
if N == 1:
    print(ans)
else:
    A = sorted(A)
    for i in range(N):
        if i == 0 and A[i] != A[i+1]:
            ans += 1
        else:
            for j in range(i):
                if A[i] % A[j] == 0:
                    break
                if j == i-1:
                    ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
count = 0
s = max(a)
for m in a:
    if a.count(m) ==1:
        if m <= s // 2:
            j=2
            while m * j <= s:
                if m * j in a:
                    a.remove(m*j)
                j += 1
    else:
        while m in a:
            a.remove(m)
print(len(a))

Submission status: Wrong Answer

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

for i in range(N):
    B = [b for b in B if b % A[i] != 0 or b == A[i]]
    print(B)

print(len(B))

Submission status: Wrong Answer

Solution code:
from collections import deque
import collections
from bisect import bisect
from bisect import bisect_right
from bisect import bisect_left
from bisect import insort
from bisect import insort_right
from bisect import insort_left


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

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

    c = collections.Counter(A)
    # 重複排除
    # A.sort()
    Au = [k for k, v in c.items()]
    Au.sort()
    # B = [k for k, v in c.items() if v == 1]
    # B.sort()

    ans = len(Au)
    for i, a in enumerate(Au):
        if c[a] != 1:
            ans -= 1
            continue
        r = bisect_right(Au, int(a ** 0.5)) + 1
        ok = True
        for b in Au[:min(r, i)]:
            if a % b == 0:
                ans -= 1
                break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    sum=n

    for i in range(n):      
        for j in range(0,n-1-i):
            if a[i]%a[n-1-j]==0:
                sum-=1
                break                
            if a[i]<2*a[n-1-j]:
                break
    if n!=1:
        if a[n-1]==a[n-2]:
            sum-=1
    else:
        sum=1

            

                
        


    print(sum)
if __name__=="__main__":
    main()

Submission status: Wrong Answer

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


A.sort(reverse = True)
B = []

for n0 in A:
    print(n0)
    for i in range(len(A)):
        i += 1
        if n0 <= A[-i]:
            break
        if n0 % A[-i] == 0:
            B.append(n0)
            break
for i in B:
    A.remove(i)
ans = 0
for num in A:
    if A.count(num) == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter

upper_bound = 200002

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

counter = Counter(nums)
dup = [key for key, value in counter.items() if value >= 2]

if 1 in dup:
	print(0)
	sys.exit()
elif 1 in counter.keys():
	print(1)
	sys.exit()

out = set()
for d in dup:
	if d not in out: # O(1)
		to_add = [d * i for i in range(1, 4 + upper_bound // d) if i not in out] # O(k)
		for y in to_add: # O(k)
			out.add(y)

nums = sorted([x for x in nums if x not in out])

cnt = 0
for x in nums:
	if x not in out:
		cnt += 1
		to_add = [x * i for i in range(1, 4 + upper_bound // x) if i not in out]
		for y in to_add:
			out.add(y)

print(cnt)

Submission status: Wrong Answer

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

no_list = [False] * N

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

print(N-sum(no_list))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

A_sorted=np.sort(list(A))
result=[]
a=A_sorted[0]
while A_sorted.size>0:
    a=A_sorted[0]
    if A_sorted.size==1:
        result.append(a)
        break
    A_sorted=A_sorted[1:]
    if a in A_sorted:
        A_sorted=A_sorted[A_sorted!=a]
        continue
    result.append(a)
    A_sorted=A_sorted[A_sorted%a!=0]
print(len(result))

Submission status: Wrong Answer

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

L = []
ans = 0
for i in range(N):
    NG = 0
    finish = 0
    X = A[i]
    for j in range(N):
        if i == j:
            continue
        if NG == 1:
            break
        if A[j] in L:
            continue
        else:
            #print(X, A[j], X % A[j])
            if X < A[j]:
                ans += 1
                finish = 1
                break
            if X % A[j] == 0:
                NG = 1
                break
            else:
                L.append(A[j])
    if NG == 0 and finish == 0:
        ans +=1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)
c = sorted(a)
r = []
if len(set(a)) == 1:
    print(0)
    exit()

for i in range(n):
    for k in c[:i]:
        if i in r:
            continue
        if b[i] % k == 0:
            r.append(i)
            break
print(n - len(set(r)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
from collections import defaultdict
from bisect import bisect_left


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization(n, primes):
    """
    nの素因数分解を求める
    """
    prime_factors = defaultdict(int)
    if n < 2:
        return prime_factors
    for p in primes:
        if p * p > n:
            break
        while n % p == 0:
            prime_factors[p] += 1
            n //= p
    if n > 1:
        prime_factors[n] = 1
    return prime_factors


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    is_prime = [True for i in range(n+1)]
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return primes


def solve(N, A):
    A.sort()
    primes = sieve(10**6)
    P = len(primes)
    T = [False for i in range(P)]
    ans = 0

    for a in A:
        factors = prime_factorization(a, primes)
        not_div = True
        for key in factors.keys():
            ix = bisect_left(primes, key)
            if T[ix]:
                not_div = False
            T[ix] = True
        if not_div:
            ans += 1
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if ok[i] == 1:
        continue
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
    if a[i] < 2:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:
        times = 1
        while a[i] * times < a[-1]:
            r = bisect.bisect_left(a, a[i] * times)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(r, l):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Wrong Answer

Solution code:
from collections import Counter
import time


s = time.time()
def make_divisors_exist(n):
    #divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if exists[i]:
                if i != n:
                    return True
            #divisors.append(i)
            i2 = n // i
            if i != i2: # choufuku
                if exists[i2]:
                    if i2 != n:
                        return True
                #divisors.append(i2)

    # divisors.sort()
    #return divisors
    return False



input = raw_input
input()
As_0 = map(int, input().split(" "))

out = 0

counter = Counter(As_0)
As = counter.keys()

max_A = max(As)
exists = [False] * (max_A + 1)

timeover = False
for A in As:
    exists[A] = True

s = time.time()
for A1, num in counter.items():
    e = time.time()
    tdiff = e-s

    if tdiff >= 1.86:
        #print(tdiff)
        break

    if num >= 2:
        continue
    
    exist = make_divisors_exist(A1)

    if not exist:
        out += 1

print(out)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def prime_fact(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 Counter(a) #カウンターを返す（要素と出現回数）


def main():
    n = int(input())
    nums = list(map(int,input().split()))
    #prime_factors = list(map(prime_fact,nums))
    #prime_factors_to_s = list(map(str,prime_factors))
    #prime_factors_string = list(map(lambda x:",".join(x),prime_factors_to_s))
    #ind = dict()
##    for i in range(n):
##        if not i in ind:
##            ind[nums[i]] = [i] #インデックスを保存
##        else:
##            ind[nums[i]].append(i) #重複も一応……)
    nums.sort()
    fact_counters = [prime_fact(n) for n in nums]
    undivisable = [True] * n
    #print(nums)
    print(nums)
    for i in range(n-1):

        if not undivisable[i]:
            continue #すでに何かで割られた数はスルー(それより小さい数で割れる)
        divisor = fact_counters[i]
        for j in range(i+1,n):
            for key in divisor.keys():
                flag = True
                if fact_counters[j][key] <= divisor[key]:
                    continue
                else:
                    undivisable[j] = False
                    print(j,nums[j],"is divisorble! by",nums[i],key)
                    break
            if nums[j] == nums[i]:
                undivisable[i] = False
        #print(nums[i],undivisable)

    print(undivisable.count(True))



if __name__ == '__main__':
    main()

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
    same_count = 0
    for j in range(n):
        if i == j:
            continue
        if alist[i] == alist[j]:
            same_count += 1
            continue

        if alist[i] % alist[j] != 0:
            temp_count += 1
        if temp_count == len(alist) - same_count+1:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from numba import jit

def main():
    n = int(input().strip())
    L = list(map(int, input().strip().split()))
    seen = Counter()
    ans=0
    
    for x in L:
        seen[x]+=1
    
    def loop():
        ans=0
        for x in L:
            if seen[x]>1 or x!=1 and 1 in seen:
                continue
        
            tmp=2
            while tmp**2<=x:
                if x%tmp and (tmp in seen or x/tmp in seen):
                    break
                tmp+=1
            else:
                ans+=1
        return ans
    print(loop())
if '__main__' == __name__:
    main()

Submission status: Wrong Answer

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

s = 0
for i in a:
  t = 0
  for j in b:
    if i%j == 0 and j != i:
      t += 1
  if j != i and t == 0:
    s += 1
print(s)

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

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

a.sort(reverse=True)
cnt = 0
for i in range(1,len(a)+1):
    for j in reversed(range(i,len(a))):
        if is_prime(a[i-1]):
            if a[i-1] in a[i+1:]:
                cnt += 1
                break
        if a[i-1] % a[j] == 0:
            cnt += 1
            break
if a[n-1] % a[n-2] == 0:
    cnt += 1
print(n - cnt)

Submission status: Wrong Answer

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

count = 0
for i in range(1, N):
    B = A[:i]
    a = A[i]
    bit = 0
    for b in B:
        if a%b == 0:
            bit = 1
            break
    if bit == 0:
        count+=1
if A[0] not in A[1:]:
    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N=int(stdin.readline())
A=[int(x) for x in stdin.readline().rstrip().split()]

flags=[False]*N
his=[]

for i in range(N):
    for j in range(N):
        if i==j:
            continue
        if A[i]%A[j]==0:
            break
        if A[i]%A[j]!=0 and A[i] not in his and j==(N-1):
            flags[i]=True
            his.append(A[i])

print(flags.count(True))

Submission status: Wrong Answer

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

a_list.sort()
#print(a_list)

Ans=n

for start in range(0,n):
    for tmp in range(0,n):
        if start == tmp:
            break
        if a_list[int(start)] == a_list[int(tmp)]:
            break
        if a_list[int(start)]%a_list[int(tmp)] == 0:
            Ans-=1
            break

print(Ans)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
D = list(set(A))
D.sort(reverse=True)
E = D.copy()
ret = 0
C = collections.Counter(A)
for c in C.keys():
    if C[c] > 1:
        E.remove(c)
        ret += C[c]

for i in range(len(E)):
    for j in range(len(D)-1,i,-1):
        if E[i] % D[j] == 0:
            ret += 1
            break
print(N - ret)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
lis = []
for i in range(n):
    if i != 0:
        if a[i] == a[i - 1]:
            lis.append(a[i])
lis = list(set(lis))
sa = set(a)
sl = len(sa)
sa = list(sa)
for i in range(sl):
    count = 0
    for j in range(sl):
        if i == j:
            pass
        elif a[i] in lis:
            pass
        elif count == 0:
            if sa[i] % sa[j] == 0:
                count = 1
        else:
            break
    else:
        if count == 0:
            ans += 1
print(ans)

Submission status: Wrong Answer

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

count = 0
precount = 0

for i in range(N):
    if i == N - 1:
        if all(AA[i] % AA[k] != 0 for k in range(i-1)):
            count += 1
    else:
        if all(AA[i] % AA[k] != 0 for k in range(i-1)) and AA[i] != AA[i+1]:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import sys
def main():
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  a.sort()
  ans=0
  if n==1:
    ans+=1
  elif a[0] != a[1]:
    ans+=1
  for i in range(1,n):
    flg=0
    if a[i] == a[i-1]:
      ans-=1
    elif i!=n-1:
      if a[i] == a[i+1]:
        ans-=1
    for j in range(i):
      if a[i]%a[j]==0:
        flg=1
        break
      elif a[i]<a[j]*2:
        ans+=1
        flg=1
        break
    if flg==0 and j==i-1:
      ans+=1
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()

a.sort()
maxa = max(a)+1
for i in a:
	if a.count(i)>=2:
		a.remove(i)
		while i in a:
			a.remove(i)


ans = [0]*maxa
for i in a:
	ans[i] = 1



for j in a:
	if ans[j]==0:
		pass
	for i in range(j*2,10**6+1,j):
		if i>maxa-1:
			break
		ans[i] = 0

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
from numba import jit

@jit
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    if len(set(A)) == 1:
        print(0)
        return
    A.sort()

    ans = 0
    while len(A) > 0:
        a = A.pop(0)
        ans += 1
        A = [i for i in A if i % a != 0]

    print(ans)

resolve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

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


def isPrime(n):
    if n < 2:
        # 2未満は素数でない
        return False
    if n == 2:
        # 2は素数
        return True
    for p in range(2, n):
        if n % p == 0:
            # nまでの数で割り切れたら素数ではない
            return False
    # nまでの数で割り切れなかったら素数
    return True


def tagainiso(a, b):
    for i in range(2, int(max(a, b))):
        if a % i == 0 and b % i == 0:
            return False
    return True


for i in range(n):
    if a.count(a[i]) >= 2:
        continue
    if isPrime(a[i]):
        ans += 1
        # print(a[i])
        continue

    flg = True
    for j in range(n):
        if i == j:
            continue
        elif i != j and a[i] % a[j] != 0:
            continue
        elif i != j and a[i] % a[j] == 0:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

foundList = []
for i in range(0, N - 1, 1):
    for j in range(0, N - 1, 1):
        if i != j:
            if A[i] % A[j] != 0:
                if foundList == None or not i in foundList:
                    foundList.append(i)
print(len(foundList))

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)
    if len(set(a)) == 0:
        print(0)
    else:
        print(ans)



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

Submission status: Wrong Answer

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

a.sort()

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
s = set(A)
counter = Counter(A)
A.sort()
ans = [1]*(10**6+1)
for i in range(1,10**6):
    if i in s and ans[i]:
        tmp = i
        cnt = 2
        while tmp*cnt <= 10**6:
            ans[tmp*cnt] = 0
            cnt += 1
    else:
        ans[i] = 0
    if counter[i] != 1:
        ans[i] = 0
print(sum(ans)-1)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
a = collections.Counter(p)

if len(a) >1 and a[p[n-1]] == 1:
    count +=1
for i in range(len(p)):
    if a[1] >=1:
        break
    if a[p[i]]>1:
        continue
    for j in reversed(range(i+1,len(p))):
        if p[i]< p[j]*2 and not p[i]==p[j]:
            count +=1
            break
        if p[i]%p[j] ==0:
            break
        if j == i+1:
            count +=1
if count >=1:
    print(count)
else:
    print(count)

Submission status: Wrong Answer

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

    return divisors

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

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

if 1 in a:
    if a.count(1)==n:
        print(0)
    else:
        print(1)
    exit()
    
if a[0] in a[1:]:
    ans = 0
else:
    ans = 1

div = set([a[0]])
for i in a[1:]:
    x = set(make_divisors(i))
    if not x&div:
        ans += 1
    div.add(i)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict

input()
A = np.fromstring(input(), int, sep=' ')


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

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

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

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

    if np.random.rand() > 0.3:
        f[i+1:] &= (A[i+1:] % x != 0)

print(count)

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(0, len(A)-1):
  count1 = 0
  for j in range(1, len(A)-1-i):
    count1 += 1
    if coprime(A[i], A[j]) == True:
      break
    if count1 == len(A)-2-i:
      count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
alist=list(map(int, input().split()))

alist.sort()
#print(alist)
ans=0
for i in range(1,N):
    a=alist[i]
    aaa=[a]*i
    x=np.array(aaa)
    y=np.array(alist[0:i])
    amari=x%y
    if list(amari).count(0)==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

count = 0
for Ai in A:
  flag = 0
  double = 0
  for Aj in sortedA:
    if (Aj * 2) > Ai:
      break
    if Ai == Aj:
      double += 1
      continue
    if (Ai % Aj) == 0:
      flag = 1
      break
  if flag == 0 and double < 2:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter


#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


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

a_max = max(a)
div = [0]*(a_max+1)
c = Counter(a)
#print(c)
count = 0
already = []
for i in range(n):
    if c[a[i]] != 1:
        div[a[i]] = 1
        continue
    div_a = divisor(a[i])
    for j in div_a:
        if div[j] == 1:
            break
    else:
        count += 1
        div[a[i]] = 1

print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin

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

rest_lists = []

P.sort()

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

new_list = P
k = 0
while True:
    if len(new_list) == 0:
        break
    k += 1
    if 1+k >= len(new_list):
        break
    new_list = return_filtered(new_list[1+k], new_list)

print(len(new_list))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

p=[A[0]]
#print(ikiteru)
lis=[]
for i in range(1,N):
  flag=True
  if(i<N-1):
    if(A[i+1]!=A[i]):
      ans+=1
  elif(A[i-1]!=A[i]):
    ans+=1
  for q in p:
    if(A[i]%q==0):
      flag=False
  if flag:
    p.append(A[i])
print(len(p))
#print(x)