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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def enum_duplicate_num(L):
        cnt = Counter(L)
        buf = set()
        for num in L:
            if cnt[num] > 1:
                buf.add(num)
        return buf

    def fill_mul_false(num, table):
        for ind in range(num*2, 10**6+1, num):
            table[ind] = False
    
    
    n = ii()
    command = lmi()
    command.sort()
    dup_num_set = enum_duplicate_num(command)
    table = [False] * (10 ** 6 + 1)
    for num in command:
        table[num] = True if num not in dup_num_set else False
    
    for num in command:
        fill_mul_false(num, table)
    
    print(table.count(True))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

input()
a = list(map(int, input().split()))
s = set(a)
t = {k for k, v in Counter(a).items() if v == 1} 
r = int(1 in t)
if 1 not in s:
  for x in t:
    i = 2
    while i * i <= x and (x % i or i not in s and x // i not in s):
      i += 1
    if i * i > x:
      r += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
n = 10**6+1

dp = [0 for _ in range(max(A)+1)]

for i in A:
    dp[i] += 1
    if dp[i]==1:
        for j in range(i*2, max(A)+1, i):
            dp[j] += 2
    # print(dp)
print(dp.count(1))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
not_divisible = [True] * (max(A)+1)

counter = 0
for i in range(N):
    target = A[i]

    if not_divisible[target]:
        for j in range(target, max(A)+1, target):
            not_divisible[j] = False

        if i < N-1 and A[i] == A[i+1]:
            continue


        counter += 1

print(counter)

Submission status: Time Limit Exceeded

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

flags = [True] * (A[-1] + 1)

for a in A:
    if A.count(a) > 1:
        flags[a] = False
    for mul in range(2, A[-1] // a + 1):
        flags[a * mul] = False
print(sum([flags[a] for a in A]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(n):
    b = 0
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            c = c + 1
            break
print(n - c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
n = 10**6+1

dp = [0 for _ in range(max(A)+1)]

for i in A:
    dp[i] += 1
    if dp[i]==1:
        for j in range(i*2, max(A)+1, i):
            dp[j] = 2
    # print(dp)
print(dp.count(1))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

a.sort()
def Eratosthenes(x):
    c = collections.Counter(x)
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in range(1, nmax+1):
        if not is_prime[i]:
            continue
        if i in x:
            for j in range(i*2, nmax+1, i):
                is_prime[j] = False
    for i in x:
        if c[i] > 1:
            continue
        if is_prime[i] == True:
            cnt += 1
    print(cnt)

Eratosthenes(a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

A.sort()

s = 0
for i in range(N):
    if i != N - 1:
        if A[i] == A[i + 1]:
            s += 1
            continue
    if i != 0:
        if A[i] == A[i - 1]:
            s += 1
            continue
    for j in range(i):
        if A[i] % A[j] == 0:
            s += 1
            break
        if A[i] < (A[j])*2:
            break

print(N - s)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
m,ans=max(A)+1,0
li=[0 for _ in range(m)]
li[0]=1

for a in A:
  if not li[a]:
    if A.count(a) == 1:
      ans += 1
    for i in range(a,m,a):
      li[i] = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
MX = 10**6
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    C = [0] * (MX + 1)
    for a in A:
        C[a] += 1
    ans = 0
    for a in A:
        if C[a] >= 2: continue
        for d in dv(a):
            if C[d] > 0:
                break
        else:
            ans += 1
    print(ans)

def dv(x):
    res = []
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            res.append(i)
            res.append(x // i)
    if x != 1:
        res.append(1)
    return res

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

count=0
for i in range(N):
    flag=True
    for j in range(N):
        if i!=j and A[i]%A[j]==0:
            flag=False
    if flag==True:
        count+=1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)

isprime = {a[i]:True for i in range(n)}

for i in range(n): 
    if not isprime[a[i]]: continue
    j = 2
    while a[i]*j < a[-1]+1:
        if a[i]*j in a:
            isprime[a[i]*j] = False
        j += 1

ensem = list(c.values())
key = list(c.keys())
diff = len([i for i in range(len(c)) if ensem[i] != 1 and isprime[key[i]]])
print(list(isprime.values()).count(True)-diff)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
#    C = Counter(A)
    U = [0] * (10**6+1)
    ans = 0
    for e in A:
        U[e] += 1
    for e in A:
        t = e*2
        while t <= 10**6:
            U[t] = 0
            t += e
        if U[e] > 1:
            U[e] = 0
    print(U.count(1))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
not_divisible = [True] * (max(A)+1)

counter = 0
for i in range(N):
    target = A[i]
    qualify = 0

    if not_divisible[target]:
        for j in range(target, max(A)+1, target):
            not_divisible[j] = False

        if i < N-1 and A[i] == A[i+1]:
            continue

        if i > 1 and A[i] == A[i-1]:
            continue

        counter += 1

print(counter)

Submission status: Time Limit Exceeded

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

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

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
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

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

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

#################################################
#################################################
#################################################
#################################################

#31-

n = int(input())

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

a.sort()

#print(a)
li = [0 for i in range(10**6+1)]
ans = 0
co = 0
for i in a:
    t = MakeDivisors(i)
    #print(li[:30])
    #print(i,t,ans)
    ok=1
    if(co!=0):
        if(a[co-1]==i):
            ok=0
    if(co!=n-1):
        if(a[co+1]==i):
            ok=0
    for j in t:
        if(li[j]==1):
            ok=0
    ans+=ok
    li[i]=1
    co+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def func(x):
    l=p[:x+1]
    for j in range(x+1,len(p)):
        if p[j]%p[x]!=0:
            l.append(p[j])
    return l

n=int(input())
p=list(map(int,input().split()))
p.sort()
a=[True]*n
#print(p,a)
for i in range(len(p)):
    if a[i]==None:
        continue
    for j in range(i+1,len(p)):
        if p[j]==p[i]:
            a[i]=None
            a[j]=None
        elif p[j]%p[i]==0:
            a[j]=None

#print(a)
print(a.count(True))

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())

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

a.sort()

dp = [True] * n

for i in range(len(a) - 1):
    if dp[i] == True:
        for j, x in enumerate(a[i+1:], 1):
            if dp[i + j] == True:
                if a[i + j] % a[i] == 0:
                    dp[i + j] = False
        
        if a[i] == a[i + 1]:
            dp[i] = False

print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
MAX = int(1e6)+2


n = int(input())
lis = list(map(int,input().split()))
lis2 = [0]*MAX
# lis.sort()
# m = max(lis)
ans = 0
for num in lis:
    lis2[num] += 1

for num in lis:
    for i in range(num*2, MAX, num):
        if lis2[i] > 0:
            lis2[i] += 1

print(len([i for i in lis if lis2[i] == 1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    n=int(input().rstrip())
    a=sorted([int(i) for i in input().split()])
    maxn=10**6+1
    dp=[True]*(maxn)
    cnt=[0]*(maxn)
    ans=0
    for i in a:
        if dp[i]:
            cnt[i]+=1
            for j in range(i*2,maxn,i):
                dp[j]=False

    for i in a:
        if dp[i] and cnt[i]==1:
            #print(i)
            ans+=1
    print(ans)

if __name__=="__main__":main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = [0] * (10 ** 6 + 1)

    for a in A:
        for i in range(1, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            ans[a * i] += 1

    res = 0
    for a in A:
        if ans[a] == 0 or ans[a] == 1:
            res += 1

    print(res)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import decimal
import math
import collections
import sys
input = sys.stdin.readline

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])
            break

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

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

    return arr

N=int(input())

ListA=list(map(int,input().split()))
ListA.sort()#reverse=True)

Deleted=[0]*N

ans=N
#rootN=int(math.sqrt(N))
for i in range(N):
    if(i < N-1):
        if(ListA[i]==ListA[i+1]):
            ans-=1
            continue

    if(i>=1):
        if(ListA[i]==ListA[i-1]):
            ans-=1
            continue
        
    #rootA=math.sqrt(ListA[i])
    MaxVal=ListA[i]/factorization(ListA[i])[0][0]

    # if(ListA[i]%2==0):
    #     Maxval=ListA[i]/2
    # if(ListA[i]%3==0):
    #     Maxval=ListA[i]/3
    # if(ListA[i]%5==0):
    #     Maxval=ListA[i]/5
    # if(ListA[i]%7==0):
    #     Maxval=ListA[i]/7


    for j in range(i):
        if(Deleted[j]==1):
            continue
        if(ListA[i]%ListA[j]==0):
            ans-=1
            Deleted[i]=1
            break
        if(ListA[j]>MaxVal):
            break

    
# if(N>=2):
#     if(ListA[2]%ListA[1]==0):
#         ans-=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def Sieve(N, AList):
    AList.sort()

    N_NotDivisible = 0
    while( len(AList)>0 ):
        if(len(AList)> 1):
            if(AList[0]!=AList[1]):
                N_NotDivisible+= 1
            value = AList[0]
            AList = [i for i in AList if(i%value!=0) ]
        else:
            N_NotDivisible+= 1
            break
    #print(Mins)
    return N_NotDivisible

if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()

    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)

Submission status: Time Limit Exceeded

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

a.sort()
def Eratosthenes(x):
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in range(1, nmax+1):
        if not is_prime[i]:
            continue
        if i in x:
            for j in range(i*2, nmax+1, i):
                is_prime[j] = False
    for i in x:
        if x.count(i) > 1:
            continue
        if is_prime[i] == True:
            cnt += 1
    print(cnt)

Eratosthenes(a)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
p.sort()
a=[True]*n
#print(p,a)
for i in range(len(p)):
    if a[i]==None:
        continue
    for j in range(i+1,len(p)):
        if p[j]==p[i]:
            a[i]=None
            a[j]=None
        elif p[j]%p[i]==0:
            a[j]=None

#print(a)
print(a.count(True))

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  a_max=max(a)
  dp=[1]*a_max
  a.sort()
  for x in range(1,a_max+1):
    if(dp[x-1]==0):
      continue
    if x in a:
      num=2
      while(x*num<=a_max):
        dp[x*num-1]=0
        num+=1
  ans=0
  i_p=0
  for i in a:
    if i==i_p:
      if dp[i-1]==1:
        ans-=1
        dp[i-1]=0
      else:
        dp[i-1]=0
    if dp[i-1]==1:
      ans+=1
    i_p=i
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
#import random
#import time
from collections import defaultdict, Counter

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 = 20
    #A = [random.randint(1, int(1e6)) for _ in range(int(N))]
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    #t1 = time.time()
    dup_cnt = Counter(A)
    dup = set(x for x in dup_cnt if dup_cnt[x] > 1)
    A_set = set(A)
    if 1 in A_set:
        if 1 in dup:
            print('0')
        else:
            print('1')
        exit()
    A = list(A_set)
    for t in (2,3,5,7):
        if t in A_set:
            A = [x for x in A if x%t != 0 or x==t]
    N = len(A)
    A.sort()
#    B = [factorization(x) for x in A]
#    B.sort()

    d = defaultdict(list)
    B = []
    for x in A:
        x_div = make_divisors(x)
        B.append(x_div)
        for y in x_div:
            d[y].append(x)
    assert len(A)==len(B)
    #print(A)
    #print(B)
    #print(d)
    not_divided = set()
    for i in range(N):
        bi = A[i]
        bi_fac = B[i]
        can_divide = False
        for y in bi_fac:
            for a in d[y]:
                if bi % a == 0 and bi != a:
                    #print(a,bi)
                    can_divide = True
                    break
                elif a > bi:
                    break
            if can_divide:
                break
        if can_divide or bi in dup:
            continue
        else:
            not_divided.add(bi)
    #print(A)
    #print(dup)
    #print(not_divided)
    print(len(not_divided))
    #print(time.time() - t1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 初期入力

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
count =set()
for i in range(N-1):
    for j in range(i+1,N):
        if A[j] %A[i] ==0:
            count.add(A[j])
ans =len(A_set - count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cola = Counter(a)
mult = [True] * (10**6+1)
seta = list(set(a))

for s in seta:
    tmp = s * 2
    while tmp <= 10 ** 6:
        mult[tmp] = False
        tmp += s

ans = 0
for s in seta:
    if cola[s] == 1 and mult[s] == True:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

v = [True] * 1000010
v2 = [False] * 1000010
for i in range(n):
    j = 2
    while a[i]*j < 1000010:
        v[a[i]*j] = False
        j += 1
    if v2[a[i]]:
        v[a[i]] = False
    v2[a[i]] = True

ans = 0

for i in range(n):
    if v[a[i]]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

dp = [True] * (A[-1] + 1)
for a in A:
    if dp[a] == True:
        n = 2
        while n * a <= A[-1]:
            dp[n * a] = False
            n += 1

score = 0
for a in A:
    score += dp[a] * (A.count(a) == 1)
    
print(score)

Submission status: Time Limit Exceeded

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
A=[x for x in set(A) if A.count(x) == 1]
s=set(k) & set(A)
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

count = 0
for i in range(n):
    ans = a[i] % np.array(a)
    if np.count_nonzero(ans == 0) == 1:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)

isprime = {a[i]:True for i in range(n)}

for i in range(n): 
    if not isprime[a[i]]: continue
    j = 2
    while a[i]*j < a[-1]+1:
        if a[i]*j in a:
            isprime[a[i]*j] = False
        j += 1

diff = len([i for i in range(len(c)) if list(c.values())[i] != 1 and isprime[list(c.keys())[i]]])
print(list(isprime.values()).count(True)-diff)

Submission status: Time Limit Exceeded

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

for a in A:
    if not a in memo:
        flag = True
        for div in memo:
            if a % div == 0:
                flag = False
                break
        if flag:
            ans += 1
            memo[a] = 1
    else:
        if memo[a] == 1:
            ans -= 1
            memo[a] += 1
        else:
            continue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    al = [0]*(max(a)+1)
    a.sort()
    ans = 0
    pi = 0
    for i in a:
        if al[i] == 0:
            ans += 1
            na = i
            while na <= max(a):
                al[na] = 1
                na += i
            pi = i
        else:
            if i == pi:
                ans -= 1
                pi = 0


    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())

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

a.sort()

dp = [True] * n

for i in range(len(a)):
    if dp[i] == True:
        for j, x in enumerate(a[i+1:], 1):
            if dp[i + j] == True:
                if a[i + j] % a[i] == 0:
                    dp[i + j] = False

num_dict = dict(collections.Counter(a))

result = [x for x, y in zip(a, dp) if (y == True) and (num_dict[x] == 1)]

print(len(result))

Submission status: Time Limit Exceeded

Solution code:
f=int(input())
a=list(map(int,input().split()))
p=[0]*1000001
for k in range(f):
    p[a[k]]+=1
a_s=set(a)
def cal(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
ans=0
for i in range(f):
    flag=0
    if p[a[i]]!=1:
        flag=1
    else:
        x=cal(a[i])
        for y in range(len(x)-1):
            if x[y] in set(a_s):
                flag=1
                break
        if flag!=1:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
dp = [False] * (max(A) + 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (max(A) // a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
good = 0

for i in range(N):
    Ai = A[i]
    if i == N-1:
        pass
    elif Ai == A[i-1] or Ai == A[i+1]:
        continue

    for Aj in A[:i]:
        if Ai % Aj == 0:
            break
    else:
        good += 1

print(good)

Submission status: Time Limit Exceeded

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

arr = np.array(p)
rev = 1/arr
ans = 0
for i in range(N):
    a = arr[i] % arr
    num = len([k for k in a if k == 0]) - 1
    if num == 0:
        ans = ans + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう

kouho = [x for x in set(A) if A.count(x) == 1]
target = kouho[:]

for i in range(len(A)):
    if target == []:
        break
    maxN = int(max(target)/A[i])
    for n in range(2,maxN+1):
        if A[i]*n in kouho:
            kouho.remove(A[i]*n)
            #print(A[i]*n)
target = kouho[:]

print(len(target))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = [int(hoge) for hoge in input().split()]
C = Counter(A)
A.sort()
dp = [False] * (max(A) + 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (max(A) // a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)

Submission status: Time Limit Exceeded

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

#数列Aを昇順に並べ替えた後、AjがAiの倍数になっていた時Ajをリストから削除する方針です。
for i in range(len(A)):
    if i >= len(A)-1: #数列が小さくなって行くので当初のループ量は必要ないので。
        break
    for j in range(len(A)-1,i,-1): #大きい数字から順番にみていく。
        if A[i] == A[j]:
            onaji = 1
        if A[j] % A[i] == 0:
            del A[j]
            
    if onaji == 1: #同じ数字があった時Aiも削除。
        del A[i]
        onaji = 0

print(len(A))

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


n = int(input())
nlist = sorted(list(map(int, input().split())))
boollist = [True for _ in range(len(nlist))]
check = 0

for num, i in enumerate(nlist):
    for j in make_divisors(i):
        if j in nlist[:num] or j in nlist[num + 1:]:
            boollist[num] = False
            break
print(boollist.count(True))