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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

#####MakeDivisors######
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

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()
A = Counter(A)
miru = []
for a in A:
  if A[a] == 1:
    miru.append(a)
miru.sort()

if not miru:
  print(0)
  exit()

def make_primes(N):
  max = N
  seachList = miru
  primeNum = []
  while seachList:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

print(len(make_primes(miru[-1])))

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()
    A.sort()

    F = [True] * (A[-1] + 1)
    for i in range(N - 1):
        if F[A[i]] and A[i] == A[i + 1]:
            F[A[i]] = False

    res = 0
    for a in A:
        if not F[a]:
            continue
        
        res += 1
        for b in range(a, len(F), a):
            F[b] = False

    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ma = 2 * 10 ** 6
tab = [False] * (ma)

ans = 0
j = 0
for i in a:
    if not tab[i]:
        if not(n - 1 > j and a[j] == a[j+1]):
            ans += 1
        for j in range(i, ma, i):
            tab[j] = True
    j += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
count = [0]*(max(A)+1)
A.sort()
for a in A:
    for i in range(a,len(count),a):
        if count[i] == 2:
            break
        count[i] += 1
ans = 0
for a in A:
    if count[a] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
ls = [1]*(10**6+1)
ans = 0
for idx,i in enumerate(a):
  if ls[i] == 0:
    continue
  if idx < n-1 and a[idx+1] != i:
    ans += 1
  for j in range(i,10**6+1,i):
    ls[j] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    count=0

    for i in range(n):
        if i == 0 and a[0] not in a[1:]:
            count+=1

        for j in range(i):
            if a[i] % a[j] == 0:
                break
            if j == i-1:
                count+=1
    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
ls = [1]*(10**6+1)
ans = 0
for i in a:
  if ls[i] == 0:
    continue
  ans += 1
  for j in range(i,10**6+1,i):
    ls[j] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    N = 2*10**6
    f = [1]*(N+1)
    a.sort()
    cnt = [0]*(N+1)
    for i in a:
        cnt[i] += 1
    for i in range(N+1):
        if cnt[i] > 1:
            f[i] = 0
    ans = 0
    for i in a:
        if f[i]:
            ans += 1
            x = i
            while x <= N:
                f[x] = 0
                x += i
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    N = 10**6
    f = [1]*(N+1)
    a.sort()
    cnt = [0]*(N+1)
    for i in a:
        cnt[i] += 1
    for i in range(N+1):
        if cnt[i] > 1:
            f[i] = 0
    ans = 0
    for i in a:
        if f[i]:
            ans += 1
            x = i
            while x <= N:
                f[x] = 0
                x += i
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
ls=[int(s) for s in input().split()]
ls.sort()
cand=set()
ans=0
for i in range(N):
  if i<N-1 and ls[i]==ls[i+1]:
    cand.add(ls[i])
    continue
  else:
    for m in cand:
      if ls[i]%m==0:
        break
    else:
      cand.add(ls[i])
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
ls=[int(s) for s in input().split()]
ls.sort()
cand=set()
ans=0
for i in range(N):
  if i<N-1 and ls[i]==ls[i+1]:
    cand.add(ls[i])
    continue
  else:
    for m in cand:
      if ls[i]%m==0:
        break
    else:
      cand.add(ls[i])
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
ans=[True]*n
l.sort()
for i in range(n):
    if ans[i]:
        if i!=n-1:
          if l[i]==l[i+1]:
            ans[i]=False
        for j in range(i+1,n):
            if l[j]%l[i]==0:
                ans[j]=False
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
ans=[-1]*n
l.sort()
for i in range(n):
    if ans[i]==-1:
        ans[i]=1
        if i!=n-1:
          if l[i]==l[i+1]:
            ans[i]=0
        for j in range(i+1,n):
            if l[j]%l[i]==0:
                ans[j]=0
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

def trial_division(n):
    a = []
    f = 2
    while n > 1:
        if n % f == 0:
            a.append(f)
            n /= f
        else:
            f += 1
    return a

INF = inf
MOD = 1000000007

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

tmp = [True for i in range(max(A) + 1)]
res = 0

A = np.array(A)
for i in range(1, len(tmp)):
    cnt = len(np.where(A == i)[0])
    if cnt > 0:
        j = 2 * i
        while j < len(tmp):
            tmp[j] = False
            j += i
    if cnt > 1:
        tmp[i] = False
for i in A:
    if tmp[i]:
        res += 1

print(res)