Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int , input().split()))
sa = set()
for ai in a:
    if ai in sa:
        sa.discard(ai)
        continue
    sa.add(ai)

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

a = list(sa)
a.sort()

#print(a)
import numpy as np
U=10**6 + 5
is_prime = np.zeros(U,np.bool)
#is_prime[2] = 1
is_prime[1::] = 1
M = int(U**.5)+1
for ai in a:#range(3,M,2):
    if is_prime[ai]:
        is_prime[ai*2::ai] = 0
    #print(is_prime.nonzero()[0])

ans = 0
for ai in a:
    if is_prime[ai]:
        ans += 1

print(ans)

"""
p = list(range(10**6+10))

a = list(sa)
a.sort()

print(a)

import fractions
def lcm(a, b):
    return a * b // fractions.gcd(a, b)

ans = 1
l = 1
for i in range(n):
    if lcm(a[i], l) < a[i] * l:
        continue
    l = lcm(a[i], l)
    ans += 1
print(ans)

"""

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
from collections import Counter
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    A = list(geta(int))
    Amax = 10**6
    dp = [True for _ in range(Amax + 1)]

    A.sort()

    ans = 0

    C = Counter(A)
    for k in C:
        if C[k] > 1:
            ans -= 1

    for a in A:
        if dp[a]:
            ans += 1
            for j in range(a, Amax + 1, a):
                dp[j] = False

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math

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

dic = Counter(a)

ans = 0

memo = {}

def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primeNum = set(get_sieve_of_eratosthenes(10**6))

for ai in a:
    cnt = 0
    f = 1
    if ai not in memo:
        if ai in primeNum:
            if dic[ai] > 1:
                f = 0
        else:
            for i in range(1, int(math.sqrt(ai))+1):
                if ai % i == 0:
                    d = i
                    if d in dic:
                        cnt += dic[d]
                    if d == ai:
                        cnt -= 1
                    if cnt > 0:
                        f = 0
                        break
                    if i != ai // i:
                        d = ai // i
                        if d in dic:
                            cnt += dic[d]
                        if d == ai:
                            cnt -= 1
                        if cnt > 0:
                            f = 0
                            break
    else:
        f = memo[ai]
    ans += f
    memo[ai] = f

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, *A = map(int, open(0).read().split())

m = max(A) + 1
ok = [True] * m
ctr = Counter(A)
ans = 0
for a in sorted(A):
    if ok[a] and ctr[a] == 1:
        ans += 1
        
        for j in range(2 * a, m, a):
            ok[j] = False
            
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = Counter(list(map(int,input().split(' '))))
ans = 0
L = [1]*(10**6+1)
for i in sorted(A.keys()):
    if A[i] > 1:
        continue
    ans += L[i]
    for j in range(i,10**6+1,i):
        L[j] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(float, input().split()))
A = np.sort(A)
D= np.ones(N)
f= 0
for i in range(2, 1001):
    j=0
    c = 1
    g = 0
    while j<len(A):
        if A[j] % i == 0:
            if A[j] == i:
                g = 1
            if g == 1:
                A = np.delete(A, j)
                j -=1
                if c == 1:
                    f += 1
                    c = 0
            if g == 0:
                while A[j] % i == 0:
                    A[j] /= i
        j += 1
q = f+len(A)
if q < 2:
    print(0)
else:
    print(q)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(set(map(int, input().split())))
a.sort()
check = [True for _ in range(10**6 + 5)]
dic = {}
for i in a:
    if i in dic:
        continue
    dic[i] = True
    now = 2 * i
    while (10**6 > now):
        check[now] = False
        now += i

ans = 0
for i in a:
    if check[i] and i not in dic:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math

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

dic = Counter(a)

ans = 0

memo = {}

def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primeNum = set(get_sieve_of_eratosthenes(10**6))

for ai in a:
    cnt = 0
    f = 1
    if ai not in memo:
        if ai not in primeNum:
            if dic[ai] > 1:
                f = 0
        else:
            for i in range(1, int(math.sqrt(ai))+1):
                if ai % i == 0:
                    d = i
                    if d in dic:
                        cnt += dic[d]
                    if d == ai:
                        cnt -= 1
                    if cnt > 0:
                        f = 0
                        break
                    if i != ai // i:
                        d = ai // i
                        if d in dic:
                            cnt += dic[d]
                        if d == ai:
                            cnt -= 1
                        if cnt > 0:
                            f = 0
                            break
    else:
        f = memo[ai]
    ans += f
    memo[ai] = f

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
A.sort()
bl = [True] * (A[-1]+1)
answer = 0
for i, a in enumerate(A):
    if i < N-1 and A[i+1] == a:
        bl[a] = False
    elif bl[a]:
        answer += 1
        bl[a] = False
    next = a + a
    while next <= A[-1] and bl[next]:
        bl[next] = False
        next += a

print(answer)

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n <= 1:
        return False
    for b in range(2, int((n**(1/2))+1)):
        if n % b == 0:
            return False
    return True


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

cnt = 0
A_s = sorted(A)
for i in range(N):
    if A_s.count(A_s[i]) == 1:
        if is_prime(A_s[i]):
            cnt += 1
        else:
            flg = True
            for j in range(i):
                if A_s[i] % A_s[j] == 0:
                    flg = False
                    break
            if flg:
                cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
anstable = [0] * (10 ** 6 + 1)

for i in range(N):
    for j in range(a[i] * 2, 10 ** 6 + 1, a[i]):
        anstable[j] += 1

cnt = 0
for i in a:
    if anstable[i] == 0:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
 
import numpy as np
from collections import Counter


N = int(input())
A = np.array(readline().split(), np.int32)
count = Counter(A)
A = np.array([
    a for a, c in count.items() if c == 1
])
 
if len(A) != 0:
    A = np.sort(A)

i = 0
while True:
    if len(A) == 0:
        break
    pre = A
    a = A[i]
    A = np.delete(A, np.where((A % a == 0) & (A != a)))
    i += 1
    if i >= len(A):
        break

print(len(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * n
for i, num in enumerate(a):
    if num > a[-1]*0.5:
        break
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        flag[i] = False
        continue
    for j in range(i+1, n):
        if a[j]%num==0:
            flag[j] = False
counter = 0
#print(flag)
for i in range(len(flag)):
    if flag[i]:
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
from collections import Counter

input()
c = Counter(map(int, input().split()))
r = c[1] == 1
if c[1] == 0:
  for k, v in c.items():
    if v == 1:
      i = 2
      while i * i <= k:
        if k % i == 0 and  (i in c or k // i in c):
          break
        i += 1
      else:
        r += 1
print(r)

Submission status: Wrong Answer

Solution code:
N = int(input())
array = list(map(int, input().strip().split()))
array.sort()
ans = N
a = [True] * N
i = 0
for i in range(N):
    for j in range(i+1,N):
        if a[i] == False:
            break
        if ((array[j] % array[i] == 0 or array[j] == array[i]) and a[j] != False):
            a[j] = False
            ans -= 1
if (array[N-1] == array[N-2]):
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1

    ans = 0
    for i in range(N):
        x = A[i]
        if x > 1:
            if y[1] : continue
        if y[x] > 1: continue

        f = 1
        for j in range(2,int(math.sqrt(x))+1):
            if y[j] or y[x//j]:
                if i % j == 0:
                    f = 0
                    break
        ans += f

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
nums = sorted(list(a.keys()))
ans = n
for i, num in enumerate(nums):
    if a[num] > 1:
        ans -= a[num]
        continue
    if i == 0:
        continue
    search_range = nums[:i-1]
    for i in search_range:
        if num % i == 0:
            ans -= a[num]
            break
print(ans)

Submission status: Wrong Answer

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

def main():
    n = int(input())
    a= list(map(int, input().split()))
    a.sort()
    flag = [1]*(10**6+1)
    for i in range(n):
        if (flag[a[i]]==1):
            for j in range(2*a[i],10**6+1,a[i]):            
                flag[j] = 0


if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():

    n=int(input())
    As=list(map(int, stdin.readline().split()))
    As.sort()
    primes=[]
    answers=[]


    primes.append(100003)
    last=0


    found=True

    for a in As:
        if last == a:
            if found == False:
                answers.pop(-1)
            last=a
            found=True
            continue

        for p in primes:
            if a % p == 0 :
                found=True
                break
            else:
                found=False

        if found==False:
            if a!=1:
                primes.append(a)
            answers.append(a)
            last=a

        else:
            last=a

    print (len(answers))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

    A.sort()
    
    A=deque(A)

    escape=deque([])
    while len(A)>0:
        minute=A.popleft()

        flag=0

        length=len(A)
        A_=A.copy()
        while len(A_)>0:
            maximum=A_.pop()
            if maximum==minute:
                flag=1
            if maximum%minute==0:
                A.remove(maximum)
            if maximum/minute<2:
                break

        if flag!=1:
            escape.append(minute)


    print(len(escape))




if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    pool = set()
    count = 0
    limit = 10 ** 6 // 2 +1
    for i in range(n):
        t = a[i]
        if t in pool:
            continue
        for j in range(1, limit):
            x = t*j
            if x > limit:
                break
            pool.add(x)
        if not (n > i+1 and t == a[i+1]):
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

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

  d = [[] for _ in range(2 * (10 ** 6) + 1)]
  b = [0] * (2 * (10 ** 6) + 1)

  res = 0;

  for v in A:
    if len(d[v]) == 0:
      l = math.floor(math.sqrt(v))
      di = [1]
      for i in range(2, l+1):
        if v % i == 0:
          di.append(i)

          if i != l:
            di.append(v//i)

      d[v] = di

    b[v] += 1

  for v in A:
    is_divisible = False

    if(b[v] > 1):
      is_divisible = True;
    else:
      for i in d[v]:
        if(b[i] > 0):
          is_divisible = True
    
    if not is_divisible:
      res += 1

  print(res)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(map(int,input().split()))
s=set(A)
ans=0
dp=[True]*(max(A)+1)
for i in range(N):
    if i<N-1 and A[i+1]==A[i]:
        dp[A[i]]=False
        continue
    if not dp[A[i]]:
        continue
    ans+=1
    for j in range(100001):
        if A[i]*j>max(A):
            break
        dp[A[i]*j]=False
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    hurui = [0] * (10**7)
    prev = 0
    for a in A:
        hurui[a] = 1
        if prev == a:
            hurui[a] = 0
        prev = a
    for i in range(1010):
        if hurui[i] == 0:
            continue
        j = 2
        while j * i <= 10**6 + 100:
            hurui[i*j] = 0
            j += 1

    print(sum(hurui))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict, Counter

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    # _, primes = sieve(100001)
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    cA = Counter(A)
    Amax = max(A)
    dp = [True] * (Amax + 1)
    checked = defaultdict(bool)

    for a in A:
        if checked[a]:
            continue
        if dp[a]:
            checked[a] = True
            for k in range(1, 100000):
                if a + k * a <= Amax:
                    dp[a + k * a] = False
            
    ans = 0
    for a in A:
        if dp[a] and cA[a] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = Counter(list(map(int,input().split(' '))))
ans = 0
L = [1]*(10**6+1)
for i in sorted(A.keys()):
    if A[i] > 1:
        continue
    ans += L[i]
    for j in (i,A[-1],i):
        L[j] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(len(a)):
    for j in range(len(a)):
        if i <= j:
            break 
        elif a[i] % a[j] == 0:
            break
        if j == len(a) - 1:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
A = list(set(A))
N = len(A)
B = A
flag = 0
for i in range(N):
    C = []
    flag = 0
    for j in range(len(B)):
        if B[j] == A[i]:
            if flag == 0:
                C.append(B[j])
                flag = 1
        elif B[j] < A[i]:
            C.append(B[j])
        elif B[j] // A[i] != 0 and B[j] % A[i] != 0:
            C.append(B[j])
    B = C
 
if len(B) > 1:
    print(len(B))
else:
    print(0)

Submission status: Wrong Answer

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

A.sort()
max_num = max(A)
sub_count = [x for x in set(A) if A.count(x) > 1]

i = 0
count = 0
while True:
    if len(A) == 0 or A[0] == max_num:
        break
    count += 1
    look = A[0]
    del A[0]
    del_num = []
    for j in range(len(A)):
        if A[j] % look == 0:
            del_num.append(j)
    del_num = sorted(del_num, reverse=True)
    for j in del_num:
        del A[j]

print(count - len(sub_count))

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    A.sort()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1
    next_A = deque()
    for a in A:
        if count[a] == 1:
            next_A.append(a)
    A = list(next_A)
    if len(A) == 0:
        print(0)
        return
    if count[1] >=2:
        print(0)
        return
    if count[1] == 1:
        print(1)
        return


    def make_divisors(n):
        lower_divisors , upper_divisors = deque(),deque()
        for i in range(1,int(n**0.5)+1):
            if n % i == 0:
                lower_divisors.append(i)
                if i != n // i:
                    upper_divisors.appendleft(n//i)
            i += 1
        upper_divisors
        return lower_divisors + upper_divisors




    F = deque()
    for a in A:
        F.append(make_divisors(a))
    ans = 0
    Not_Divisible = [False] * (max(A)+1)
    for f in F:
        for d in f:
            if Not_Divisible[d]:
                break
        else:
            Not_Divisible[f[-1]] = True
            ans += 1
    print(ans)
    dbg(F)
    dbg(Not_Divisible)
    
main()

Submission status: Wrong Answer

Solution code:
def d170(n,a):
    count=0
    sa=sorted(list(set(a)))
    print(sa)
    t=set([x for x in set(a) if a.count(x)>1])
    if sa[0]==1:
        if 1 in t:
            return 0
        else:
            return 1
    else:
        for i in range(len(sa)) :
            if i>=len(sa):
                break
            else:
                p=sa[i]
                k=[]
                for j in range(i+1,len(sa)):
                     if sa[j]%p==0:
                        k.append(sa[j])
                sa=sorted(list(set(sa)-set(k)))
        print(sa)
        return len(set(sa)-t)
    
n=int(input())
a= list(map(int, input().split()))    
print(d170(n,a))

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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]


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A.sort()

    aset = list(set(A))

    aset.sort()
    ans = 0
    s = set()
    anss = set()
    for a in aset:
        divs = make_divisors(a)
        for div in divs:
            if div in s:
                break
        else:
            ans += 1
            anss.add(a)
        s.add(a)

    c = collections.Counter(A)
    for x in c.most_common():
        if x[1] > 1 and x[0] in anss:
            ans -= 1
        else:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

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

# ダブリを省くために先に数える
c = Counter(search_list)
original = [x for x in c.keys() if c[x] == 1]

tmp = min(search_list)

while search_list and min(search_list) <= max(search_list)/2:
    tmp = min(search_list)
    if tmp in original:
        ans_list.append(tmp)
    search_list = [i for i in search_list if i % tmp != 0]

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    hurui = [0] * (10**6+1)
    prev = 0
    for a in A:
        hurui[a] = 1
        if prev == a:
            hurui[a] = 0
        prev = a
    for i in range(1010):
        if hurui[i] == 0:
            continue
        j = 2
        while j * i <= 10**6:
            hurui[i*j] = 0
            j += 1

    print(sum(hurui))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
L = list(map(int,input().split()))
L.sort(reverse=True)
count = 0
for n in np.array(range(N)):
    if n != N-1:
        L_s = L[n+1:]
    else:
        L_s = L[n:]
    for l_s in L_s:
        if L[n]%l_s == 0:
            break
    else:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=sorted(map(int,input().split()))
L=[A[0]]
if n==1:
    print(0)
else:
    c=0
    if A[0]!=A[1]:
        c=1
    for i in range(n-1):
        #print(str(A[i+1])+'だよ')
        flag=0
        for l in L:
            #print(l)
            if A[i+1] in L:
                flag=1
                break
            if A[i+1]%l==0:
                #print(str(l)+'でわれちゃったから抜けるね')
                flag=1
                break
            if l>=int(A[i+1]**0.5+1):
                #print(str(l)+'おおきくなっちゃったから抜けるね')
                break
        if flag==0:
            L.append(A[i+1])
            c+=1
    print(c)
    #print(L)

Submission status: Wrong Answer

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

As = sorted(A)

dellist = []
# A[0]は最小なので同じ数字を除いてそれよりも大きい他の数では割り切れない。
i = 0
MAX = int(math.sqrt(As[N-1]))+2
while(i < len(As)):
    if As[i] < MAX:
        break
#     print('i:{}'.format(i))
#     print('As:{}'.format(As))
    # As[i]で、A[i+1]～A[len(As)]で割り切れるものを探し、消す。
    j = i+1
    poplist = []
    while(j < len(As)):
#         print('j:{}'.format(j))
#         print('As[i]:{}'.format(As[i]))
#         print('As[j]:{}'.format(As[j]))
        if As[j]%As[i] == 0: # 割り切れちゃった場合
            # A[j]をあとで消すために控える
            poplist.append(j)
            # A[i]とA[j]が同じ数字なら、最後にA[i]も消す必要があるので、
            # A[i]を削除リストに入れる
            if As[i]  == As[j]:
                dellist.append(A[i])
                
        j += 1
        
    # poplistにあるAs[]を消す
    # 前から消していくと順番が狂うので、後ろから消す。参考↓
    # https://gammasoft.jp/blog/remove-multiple-elements-from-python-list/
    for k in sorted(poplist, reverse=True):
        As.pop(k)
    # As[i]で割り切れるものは探しきって、次のAs[i+1]は割り切れないもの。
    # 次はAs[i+1]について考える
    i += 1

# remove は、指定した要素がlistに含まれていないとエラーを吐くみたいなので、
# 重複を排除する
dellist = list(set(dellist))
    
for i in dellist:
    As.remove(i)

# print(As)
print(len(As))
# print(dellist)

Submission status: Wrong Answer

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


def make_divisors(n):
    if n == 1:
        return [1]
    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)

    divisors.remove(n)
    return divisors


N = int(input())
A = list(map(int, input().split()))
X = [0] * (10**6 + 1)
for a in A:
    X[a] += 1
ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in make_divisors(a):
        if X[d]:
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    hurui = [0] * (10**6+1)
    prev = 0
    for a in A:
        hurui[a] = 1
        if prev == a:
            hurui[a] = 0
        prev = a
    for i in range(1010):
        if hurui[i] == 0:
            continue
        j = 2
        while j * i <= 10**6:
            hurui[i*j] = 0
            j += 1

    for i,h in enumerate(hurui):
        if h:
            print(i)
    print(sum(hurui))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
A=list(map(int,input().split()))
A=np.array(A)
count=0
for a in A:
  if np.sum(A % a == 0)==1:
    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline().rstrip('\n')

def calc(N, S):
    A.sort()
    return A[0]

N = int(input())
A = [int(s) for s in input().split()]
print(calc(N, A))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split(' '))))
ans = 0
L = [1]*(10**6+1)
for i in A:
    if not L[i]:
        continue
    ans += L[i]
    for j in (i,A[-1],i):
        L[j] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=1)
bl=[0]*(10**6+1)
B=[]
while A:
    x=A.pop()
    if A:
        if x!=A[-1]:
            B.append(x)
        else:
            while A:
                y=A.pop()
                if y!=x:
                    A.append(y)
                    break
            xx=x
            while x<10**6:
                bl[x]=1
                x+=xx
    else:
        B.append(x)


ans=0
for x in B:
    ans+=not bl[x]
    xx=x
    while x<10**6:
        bl[x]=1
        x+=xx
print(ans)