Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
import math
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()

d = defaultdict(int)

for i in a:
	d[i]+=1

arr = []
for i in d:
	if d[i]==1:
		arr.append(i)
arr.sort()

if len(arr)==0:
	print(0)
	exit()

maxa = max(arr)

ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

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

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
N =input()
A = list(map(int, input().split()))
N=int(N)
s=0
A2 = [-1] #重複
LS =[-1]
for i in range(0,N):
  k=1
  P =A[i]
  if P in A2:
    pass
  else:
    while P*k<=10^6:
      LS.append(P)
      k+=1
    A2.append(P)
for j in range(0,N):
  if A[j] in A2:
    pass
  else:
    if LS.count(A[j]) ==1:
      s+=1
      
print(s)

Submission status: Wrong Answer

Solution code:
N =input()
A = list(map(int, input().split()))
N=int(N)
s=0
A1 =A
A2 = [-1]
B = [-1]
LS =[]
for i in range(0,N):
  k=1
  P =A1[i]
  if P in A2:
    if P in B:
      pass
    else:
      B.append(P)
  else:
    while P*k<=2*10^5:
      LS.append(P)
      k+=1
    A2.append(P)
for j in range(0,N):
  if A[j] in B:
    pass
  else:
    if LS.count(A[j]) ==1:
      s+=1
      
print(s)

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

d = defaultdict(int)

for i in a:
	d[i]+=1

arr = []
for i in d:
	if d[i]==1:
		arr.append(i)
arr.sort()

if len(arr)==0:
	print(0)
	exit()

maxa = max(arr)

ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

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

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

    MAX = 2000005
    T = [0]*MAX

    ans = 0
    for a in A:
        if T[a]:
            continue
        else:
            ans += 1
            for i in range(2*a, MAX, a):
                T[i] += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

max_a = max(a)
ok = [False] * (max_a + 1)
sorted_a = sorted(a)

ans = 0
for i in range(n):
    if ok[sorted_a[i]]:
        continue
    else:
        ans += 1
        for j in range(1, max_a // sorted_a[i] + 1):
            ok[sorted_a[i] * j] = True
        

count_a = Counter(a)
duplication_a = len([i for i in count_a.items() if i[1] >= 2])
print(ans - duplication_a)

Submission status: Wrong Answer

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

A.sort(reverse=True)

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

ans = 0

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

print(ans)

Submission status: Wrong Answer

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

bool_ary = [0] * original_ary[-1]

for num in original_ary:
    bool_ary[num-1] += 1
    if bool_ary[num-1] == 1:
        for multiple in range(num * 2, original_ary[-1], num):
            bool_ary[multiple-1] = 2

print(bool_ary.count(1))

Submission status: Wrong Answer

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

A = list(set(A))
A.sort(reverse=True)

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

ans = 0

for num, i in enumerate(A):
    for j in A[num+1:]:
        if i == j or i % j == 0:
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

B = set(A)

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

check_list = [0] * (10**6 + 1)
for i in B:
    for j in range(1, (10**6 // i)):
        if i * j > A[-1]:
            break
        check_list[i * j] += 1

count = 0
for i in B:
    if check_list[i] == 1:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

length = int(input())
As = list(map(int, input().split()))

As.sort()

# indexを数値と紐づけるために+1増やした数にする
check = np.zeros(10**6+1)

answer = 0

# 与えられた数列の小さいものから順にループ
for i in range(length):
    if check[As[i]] == 0:
        # 与えられた数値の倍数すべてに1を立てる
        # checkは0始まりのため、0と倍数要素に1が立つ
        check[::As[i]] = 1
        
        # 同じ数字が複数ある場合はカウントさせない
        if  i != (length - 1):
            if As[i] != As[i + 1]:
                answer = answer + 1

print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

length = int(input())
As = list(map(int, input().split()))

As.sort()

# indexを数値と紐づけるために+1増やした数にする
check = np.zeros(10**6+1)

answer = 0

# 与えられた数列の小さいものから順にループ
for i in range(length):
    if check[As[i]] == 0:
        # 与えられた数値の倍数すべてに1を立てる
        # checkは0始まりのため、0と倍数要素に1が立つ
        check[::As[i]] = 1
        
        # 同じ数字が複数ある場合はカウントさせない
        if  i != length - 1 and As[i] != As[i + 1]:
            answer = answer + 1

print(answer)

Submission status: Wrong Answer

Solution code:
N=input()
A = list(map(int, input().split()))
modofA=[]
T=True
sucl =[]
for i in range(0,int(N)):
  T=True
  C=A[i] % 2
  modofA.append(C)
  
  for j in range(0,int(N)):
    if T== False:
      break
    if i!=j:
      if A[i]>=A[j]:
        if j>i:
          D=A[j] % 2
        else:
          D=modofA[j]
        if C== D:
          if A[i] % A[j]==0:
            T=False

  if T==True:
    sucl.append(i)
print(len(sucl))

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    nums.sort()

    check = [False] * (10 ** 6 + 1)
    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            check[nums[i]] = True
    print(nums)
    ans = 0
    for i in range(n):
        if check[nums[i]] == False:
            ans += 1
        if i == 0 or (i > 0 and nums[i] != nums[i - 1]):
            cnt = nums[i] * 2
            while cnt < 10 ** 6 + 1:
                #print(cnt)
                check[cnt] = True
                cnt += nums[i]
        #print(ans)
    print(ans)

    
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
factor_cnt = [0] * (maxval+1)
factor_cnt[0] = 2
factor_cnt[1] = 2
for i in range(n):
    # if factor_cnt[a[i]] > 1:
    #     continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] <= 1 for v in a)
print(result)

Submission status: Wrong Answer

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

chofuku_dict = {}
chofuku = []

for a in A:
    if a not in chofuku_dict:
        chofuku_dict[a] = 1
    else:
        chofuku.append(a)
        
chofuku = set(chofuku)

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

bl = np.array([0] + [1]*A[-1])

ans = 0
for a in A:
    if bl[a] == 0:
        continue
    if a in chofuku:
        continue
    ans += 1
    bl[2*a::a] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N=input()
A = list(map(int, input().split()))
T=True
sucl =[]
for i in range(0,int(N)):
  T=True
  for j in range(0,int(N)):
    if T== False:
      break
    if A[i]>A[j]:
      if A[i] % A[j]==0:
        if i==j:
          pass
        else:
          T=False
  if T==True:
    sucl.append(i)
print(len(sucl))

Submission status: Wrong Answer

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

chofuku_dict = {}
chofuku = []

for a in A:
    if a not in chofuku_dict:
        chofuku_dict[a] = 1
    else:
        chofuku.append(a)
        
chofuku = set(chofuku)

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

bl = np.array([0] + [1]*A[-1])

ans = 0
for a in A:
    if bl[a] == 0:
        continue
    if a in chofuku:
        continue
    bl[a] = 0
    ans += 1
    bl[2*a::a] = 0
print(ans)

Submission status: Wrong Answer

Solution code:

import os
import sys
from io import BytesIO, IOBase


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    ans = 0
    k=max(arr)
    d = [0]*(k+1)
    for i in range(n):
        d[arr[i]]+=1
    for i in range(n):
        x=arr[i]
        if d[x]==1:
            ans+=1
            for j in range(x,k+1,x):
                d[j]+=1
        if x==1:
            for j in range(x,k+1,x):
                d[j]+=1

    print(ans)


# fast-io region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def write(*args, end="\n"):
    for x in args[:-1]:
        sys.stdout.write(str(x) + " ")
    sys.stdout.write(str(args[-1]))
    sys.stdout.write(end)


def r_array():
    return [int(x) for x in input().split()]


def r_int():
    return int(input())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

chofuku_dict = {}
chofuku = []

for a in A:
    if a not in chofuku_dict:
        chofuku_dict[a] = 1
    else:
        chofuku.append(a)
        
chofuku = set(chofuku)

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

bl = np.array([0] + [1]*A[-1])

ans = 0
for a in A:
    if a in chofuku:
        continue
    if bl[a] == 1:
        bl[a] = 0
        ans += 1
    bl[2*a::a] = 0
print(ans)

Submission status: Wrong Answer

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
factor_cnt = [0] * (maxval+1)
factor_cnt[0] = 2
factor_cnt[1] = 2
for i in range(n):
    if factor_cnt[a[i]] > 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] <= 1 for v in a)
print(result)

Submission status: Wrong Answer

Solution code:
N=input()
A = list(map(int, input().split()))
T=True
sucl =[]
for i in range(0,int(N)):
  T=True
  for j in range(0,int(N)):
    if T== False:
      break
    if A[i]<A[j]:
      break
    if A[i] % A[j]==0:
      if i==j:
        pass
      else:
        T=False
        
  if T==True:
    sucl.append(i)
print(len(sucl))

Submission status: Wrong Answer

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
factor_cnt = [0] * (maxval+1)
factor_cnt[0] = 2
factor_cnt[1] = 2
for i in range(n):
    if factor_cnt[a[i]] > 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] == 1 for v in a)
print(result)

Submission status: Wrong Answer

Solution code:

import os
import sys
from io import BytesIO, IOBase


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    ans = 0
    k=max(arr)
    d = [0]*(k+1)
    for i in range(n):
        d[arr[i]]+=1
    for i in range(n):
        x=arr[i]
        if d[x]==1:
            ans+=1
            for j in range(x,k+1,x):
                d[j]+=1
    print(ans)


# fast-io region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def write(*args, end="\n"):
    for x in args[:-1]:
        sys.stdout.write(str(x) + " ")
    sys.stdout.write(str(args[-1]))
    sys.stdout.write(end)


def r_array():
    return [int(x) for x in input().split()]


def r_int():
    return int(input())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6 + 5
factor_cnt = [0] * (maxval+1)
factor_cnt[0] = 2
factor_cnt[1] = 2
for i in range(n):
    if factor_cnt[a[i]] > 1:
        continue
    if a[i] == 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] == 1 for v in a)
print(result)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort()

    check = [True] * (10 ** 6 + 5)
    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            check[nums[i]] = False

    ans = 0
    for i in range(n):
        if check[nums[i]] == True:
            ans += 1
            cnt = nums[i] * 2
            while cnt < 10 ** 6 + 1:
                check[cnt] = False
                cnt += nums[i]
    print(ans)

    
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614


##### FAST INPUT #####
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
##### END OF FAST INPUT #####
#import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort()

    check = [True] * (10 ** 6 + 5)
    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            check[nums[i]] = False

    ans = 0
    for i in range(n):
        if check[nums[i]] == True:
            ans += 1
            cnt = nums[i] * 2
            while cnt < 10 ** 6 + 1:
                check[cnt] = False
                cnt += nums[i]
    print(ans)

    
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
factor_cnt = [0] * (maxval+1)
factor_cnt[0] = 2
factor_cnt[1] = 2
for i in range(n):
    if factor_cnt[a[i]] > 1:
        continue
    if a[i] == 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] == 1 for v in a)
print(result)

Submission status: Wrong Answer

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
factor_cnt = [0] * (maxval+1)
factor_cnt[0] = 2
factor_cnt[1] = 2
for i in range(n):
    if factor_cnt[a[i]] > 1:
        continue
    if a[i] == 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] <= 1 for v in a)
print(result)

Submission status: Wrong Answer

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

chofuku_dict = {}
chofuku = []

for a in A:
    if a not in chofuku_dict:
        chofuku_dict[a] = 1
    else:
        chofuku.append(a)
        
chofuku = set(chofuku)

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

bl = np.array([0] + [1]*A[-1])
ans = 0
for a in A:
    if a in chofuku:
        continue
    if bl[a] == 1:
        bl[a] = 0
        ans += 1
        bl[2*a::a] = 0
print(ans)

Submission status: Wrong Answer

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

num = [0]*(10**6+1)
for a in A:
    num[a] += 1

bai = [False]*(10**6+1)
cnt = 0
A = list(set(A))
A.sort()
for a in A:
    if bai[a]:
        continue

    if num[a] == 1:
        cnt += 1

    for i in range(a, 10**6, a):
        bai[i] = True
print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]
  tf=[True]*maxa
  r=0
  n-=1
  for i in range(n): # maxa以外の処理
    a_i=a[i]
    if tf[a_i-1] ==True: # これまでに素の場合のみ処理実行
      for j in range(a_i - 1,maxa,a_i):
        tf[j]=False
      if a_i < a[i+1]: # a[i]とa[i+1]が同値の場合を排除
        print(a_i)
        r+=1
  if tf[-1] == True: # maxaへの処理
     r+=1
  print(r)
main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = [int(i) for i in input().split()]

    max_dp = max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")

    for a in A:
        if dp[a] >= 2:
            continue
        dp[np.arange(a, max_dp, a)] += 2
        dp[a] -= 1

    print(np.sum(dp == 1))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = [int(i) for i in input().split()]

    max_dp = np.max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")

    for a in A:
        if dp[a] >= 2:
            continue
        dp[np.arange(a, max_dp, a)] += 2
        dp[a] -= 1

    print(np.sum(dp == 1))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

a.sort()
cnt = 0
nmax = a[-1]
table = [True] * (nmax+1)
c = Counter(a)

for i in c.keys():
    if c[i] > 1:
        table[i] = False
for i in a:
    if not table[i]:
        continue
    cnt += 1
    for j in range(i*2, nmax+1, i):
        table[j] = False
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

a.sort()
cnt = 0
nmax = a[-1]
table = [True] * (nmax+1)
c = Counter(a)

for i in c.keys():
    if c[i] > 1:
        table[i] = False
for i in a:
    if not table[i]:
        continue
    for j in range(i*2, nmax+1, i):
        table[j] = False
print(cnt)

Submission status: Wrong Answer

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
has_no_factor = [True] * (maxval+1)
has_no_factor[0] = False
has_no_factor[1] = False
has_no_self = [True] * (maxval+1)
for i in range(n):
    if a[i] == 1:
        continue
    if not has_no_self[a[i]]:
        has_no_factor[a[i]] = False
        continue
    if not has_no_factor[a[i]]:
        continue
    for k in range(a[i]*2, maxval+1, a[i]):
        has_no_factor[k] = False
    has_no_self[a[i]] = False

result = sum(has_no_factor[v] for v in a)
print(result)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

a.sort()
cnt = 0
nmax = a[-1]
table = [True] * (nmax+1)
c = Counter(a)

for i in c.keys():
    if c[i] > 1:
        table[i] = False
for i in a:
    if not table[i]:
        continue
    if not a.count(i) > 1:
        cnt += 1
    for j in range(i*2, nmax+1, i):
        table[j] = False
print(cnt)

Submission status: Wrong Answer

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

l = np.array(l)

count  = 0
for i in range(len(l)):
    hoge = l%l[i]
    
    hoge[i] += 1
    if not(0 in hoge):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

bool_list = [True] * (10 ** 6)

duplicate_dic = defaultdict(int)
for a in A:
    duplicate_dic[a - 1] += 1
    if duplicate_dic[a - 1] > 1:
        bool_list[a - 1] = False

for a in A_sort:
    for i in range(2*a, 10 ** 6, a):
        bool_list[i - 1] = False

print(sum([1 for a in A_sort if bool_list[a - 1]]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

bool_list = [True] * (10 ** 6)

duplicate_dic = defaultdict(int)
for a in A:
    duplicate_dic[a] += 1
    if duplicate_dic[a - 1] > 1:
        bool_list[a - 1] = False

for a in A_sort:
    for i in range(2*a, 10 ** 6, a):
        bool_list[i - 1] = False

print(sum([1 for a in A_sort if bool_list[a - 1]]))

Submission status: Wrong Answer

Solution code:
#D
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
flag=[False for i in range(10**6+1)]

re=[]
for i in range(N):
    if flag[A[i]]:
        re.append(A[i])
    flag[A[i]]=True

ans=0
for i in range(1,10**6+1):
    if flag[i]:
        ans+=1
        for j in range(i,10**6+1,i):
            flag[j]=False
re=set(re)
print(ans-len(re))

Submission status: Wrong Answer

Solution code:
import numpy as np

try:
  n  = int(input())
  As = list(map(int, input().split()))
  As.sort(reverse=True)
  ans = 0
  
  for i in range(n):
    flag = True
    if As[i] in As[0:i] or As[i] in As[i+1:n]:
        flag = False
        continue
    	
    for j in range(n-1,i,-1):
      #print(As[i], As[j])
      if np.sqrt(As[i]) < As[j] :
        break
             
      if As[i] % As[j] == 0:
        flag = False
        break
    #print(flag)
    if flag:
      ans += 1
  print(ans)
except EOFError:
  print(n)