Problem:

B: 自身の 2 倍

問題

クエリが Q 個与えられます。1 個のクエリにつき、 1 つの正の整数 N が与えられるので、次の 2 つの条件を満たす正の整数 M の個数を求めてください。

2 \leq M \leq N を満たす

M の約数のうち、M を除いたものの総積が M の 2 倍以上になる

入力形式

入力は以下の形式で与えられます。

Q
N_1
N_2
:
N_Q

1 行目では、クエリ数 Q が与えられます。

2 行目から N+1 行目では、各クエリについて与えられる 1 つの正の整数 N が与えられます。

制約

1 \leq Q \leq 10^5

2 \leq N_i \leq 10^5 (1 \leq i \leq Q)

出力形式

上記の 2 つの条件を満たす正の整数の個数を、各 N_i に対して、改行区切りで出力してください。

入力例

3
43
9
24

出力例

11
0
5

 N=24 の時、M として考えられるのは 12, 16, 18, 20, 24 の 5 種類である。



Sample input:
3
43
9
24


Sample output:
11
0
5

Submission status: Accepted

Solution code:
from bisect import*
q,*n=map(int,open(0))
can=[]
for i in range(1,10**5+1):
    p=[]
    for j in range(1,int(i**.5)+1):
        if i%j<1:
            p+=[j,i//j]
    *p,e=sorted(p)
    for j in range(len(p)-1):p[j+1]*=p[j]
    if p[-1]>=e*2:
        can+=i,
for i in n:print(bisect(can,i))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


Fact = [False for _ in range(10**5+1)]

def get_fact(m):
  global Fact
  ans = 1
  for i in range(2,int(m**0.5)+1):
    if m%i==0:
      ans *= i
      if i != m//i:
        ans *= m//i
      if ans >= m*2 or Fact[m//i]:
        return True
  return False

Fact_n = [0 for _ in range(10**5+1)]
for i in range(2,10**5+1):
  Fact[i] = get_fact(i)
  if Fact[i]:
    Fact_n[i] = Fact_n[i-1]+1
  else:
    Fact_n[i] = Fact_n[i-1]

Q = int(input())
ret = [0 for _ in range(Q)]
for q in range(Q):
  ret[q] = Fact_n[int(input())]

for q in ret:
  print(q)

Submission status: Accepted

Solution code:
import math

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    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]

n = int(input())
ma = int(math.sqrt(10**5))
lis = get_sieve_of_eratosthenes(ma)
l_b = [False]*(10**5+1)
for item1 in lis:
    for item2 in lis:
        if item2 < item1:
            continue
        if item1*item2*3 > 10**5:
            break
        i = 0
        while(item1*item2*(3+i) <= 10**5):
            l_b[item1*item2*(3+i)] = True
            i += 1
for item in lis:
    if item**3 < 10**5:
        l_b[item**3] = False
l_count = [0]*(10**5+1)

for i in range(1,10**5+1):
    if l_b[i]:
        l_count[i] = l_count[i-1] + 1
    else:
        l_count[i] = l_count[i-1]

for _ in range(n):
    num = int(input())
    print(l_count[num])

Submission status: Accepted

Solution code:
Q = int(input())
N = list(int(input()) for i in range(Q))
m = [0]*(max(N)+1)
N_max = max(N)
r = 320
for i in range(2,r):
    for j in range(2,r):
        for k in range(2,100000//(i*j)+1):
            if i*j*k < N_max+1 and (i!=j or j!=k or k!=i):
                m[i*j*k] = 1
for i in range(1,len(m)):
    m[i] = m[i]+m[i-1]
for i in N:
    print(m[i])

Submission status: Accepted

Solution code:
import bisect
MAX_N=2*10**5
isdmore5=[1 for i in range(MAX_N+1)]
isprime=[1 for i in range(MAX_N+1)]
i=2
isprime[0]=0;isprime[1]=0
isdmore5[0]=0;isdmore5[1]=0
while(i*i<=MAX_N):
    if isprime[i]!=0:
        for j in range(2*i,MAX_N+1,i):
            isprime[j]=0
    i+=1
prime=[]
for i in range(MAX_N+1):
    if isprime[i]==1:
        prime.append(i)
        isdmore5[i]=0
#print(prime)
for p in prime:
    k=bisect.bisect_left(prime,MAX_N//p)
    #print(p,k,prime[k-1]*p,prime[k]*p,prime[k+1]*p)
    for i in range(k):
        #print(p,prime[i],p*prime[i])
        isdmore5[p*prime[i]]=0
i=2
while(i*i*i<=MAX_N):
    if isprime[i]==1:
        isdmore5[i*i*i]=0
    i+=1
ans=[0 for i in range(MAX_N+1)]
for i in range(3,MAX_N+1):
    if isdmore5[i]==1:
        ans[i]=ans[i-1]+1
    else:
        ans[i]=ans[i-1]
Q=int(input())
for i in range(Q):
    print(ans[int(input())])

Submission status: Accepted

Solution code:
import math
N = 10 ** 5 + 5
lst = [0] * (N)

for i in range(10, N-3):
    count = 0
    for j in range(1, int(math.sqrt(i))+1):
        if i%j == 0:
            count += 1
        if count >= 3:
            lst[i] = lst[i-1] + 1
    if lst[i] == 0:
        lst[i] = lst[i-1]

Q = int(input())
for _ in range(Q):
    print (lst[int(input())])

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
import sys
M = 10**5 + 2
prime = [0]*M

for i in range(2, M):
    if prime[i]:
        continue
    for j in range(i, M, i):
        if not prime[j]:
            prime[j] = i

def pd(x):
    C = Counter()
    while x > 1:
        C[prime[x]] += 1
        x //= prime[x]
    return C

def check(x):
    C = pd(x)
    if len(C) > 2:
        return True
    if len(C) == 1:
        if list(C.values())[0] >= 4:
            return True
        return False
    if all(1 == a for a in C.values()):
        return False
    return True
M -= 1
table = [0, 0] + [check(x) for x in range(2, M)] 
table = list(accumulate(table))

for _ in range(int(input())):
    q = int(sys.stdin.readline())
    print(table[q])

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret
from itertools import accumulate
def main():
    ANS = [1]*100001
    ANS[0] = 0
    ANS[1] = 0
    Primes = eratosthenes(100000)
    for p in Primes:
        ANS[p] = 0
        if p**2 <= 100000:
            ANS[p**2] = 0
        if p**3 <= 100000:
            ANS[p**3] = 0
    for p in Primes:
        for q in Primes:
            if p*q <= 100000:
                ANS[p*q] = 0
            else:
                break
    accANS = list( accumulate(ANS))
    Q = int( input())
    for _ in range(Q):
        print( accANS[ int( input())])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import product, accumulate
from math import gcd
from bisect import bisect
import sys
from sys import setrecursionlimit
setrecursionlimit(10**9)
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = 0
    return P

C = [1]*(10**5+1)
C[0] = 0
C[1] = 0
P = primes(10**5)

for p in P:
    C[p] = 0

for p in P:
    if p**3 > 100000:
        break
    C[p**3] = 0

for i in range(len(P)):
    for j in range(i, bisect(P, 10**5//P[i])):
        C[P[i] * P[j]] = 0

S = list(accumulate(C))
for _ in range(int(input())):
    print(S[int(input())])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    p = LI()
    t = LI()
    dp = [inf] * (10**5)
    dp[0] = 0
    for i in range(10**5):
        for num,ti in enumerate(t):
            if i - ti >= 0:
                dp[i] = min(dp[i], dp[i - ti] + p[num])
    for i in range(10**5-1, 0, -1):
        dp[i - 1] = min(dp[i], dp[i - 1])
    print(dp[n])
    return

#B
def B():
    def yaku(n):
        res = 0
        if n == 0:
            return 0
        for i in range(1, int(math.sqrt(n-1)) + 1):
            if n % i == 0:
                res += 2
        if float.is_integer(math.sqrt(n)):
            res += 1
        return res
    q = II()
    ya = [yaku(i) for i in range(10 ** 5 + 1)]
    ya[0] = 0
    for i in range(1,10 ** 5 + 1):
        if ya[i] >= 5:
            ya[i] = 1
        else:
            ya[i] = 0
        ya[i] += ya[i - 1]
    for i in range(q):
        n = II()
        print(ya[n])
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
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(): return list(sys.stdin.readline())[:-1]
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

#A
def A():
    n = I()
    p = LI()
    t = LI()
    ans = float("inf")
    for i in range(n+1):
        x0 = t[0]*i
        m0 = p[0]*i
        for j in range(n+1):
            x1 = x0+t[1]*j
            m1 = m0+p[1]*j
            for k in range(n+1):
                x2 = x1+t[2]*k
                m2 = m1+p[2]*k
                rest = max(0,math.ceil((n-x2)/t[3]))
                m3 = m2+p[3]*rest
                if m3 < ans:
                    ans = m3
    print(ans)
    return

#B
def B():
    def f(n):
        if n < 4:
            return 1
        m = n
        res = 1
        i = 2
        while i**2 <= n:
            if m%i == 0:
                if m//i != i:
                    res *= m//i
                res *= i
            i += 1
        return res
    MA = 100000
    d = [0]*(MA+1)
    for i in range(12,MA+1):
        if not d[i]:
            if f(i) >= (i<<1):
                j = i
                while j <= MA:
                    d[j] = 1
                    j += i
    for i in range(MA):
        d[i+1] += d[i]
    q = I()
    for i in range(q):
        print(d[I()])
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

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

Submission status: Accepted

Solution code:
Q = int(input())
N = [int(input()) for i in range(Q)]

def divisor_prod(n):
    m = 2
    s = set()
    while m*m <= n:
        if n%m == 0:
            s.add(m)
            s.add(n//m)
        m += 1
    ret = 1
    for a in s:
        ret *= a
    return ret

imos = [0]*(10**5+1)

for m in range(2,10**5+1):
    if divisor_prod(m) >= m*2:
        imos[m] += 1

for i in range(10**5):
    imos[i+1] += imos[i]

for q in N:
    print(imos[q])